Title: Transitive reductions, Horn formula optimizations and Parallel repetition theorem
Speaker: Bhaskar DasGupta, University of Illinois at Chicago (UIC).
Date: Wednesday, December 3, 2008 11:00-12:00pm
Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk, I will discuss our ongoing investigations of approximability issues of a few somewhat-related optimization problems.
We first consider the Minimum Equivalent Digraph problem (also known as the
Strong Transitive Reduction problem) and its maximum objective function
variant, with two types of extensions. For both problems we establish the
following:
* a polynomial time algorithm for the minimization version within ratio 1.5
* an algorithm for the maximization version within ratio 2, and
* MAX-SNP hardness for both versions, even if the length of simple cycles
is limited to 5.
Very roughly speaking, the Horn formula optimization problem asks, for a given Horn formula, if there is another equivalent Horn formula optimizing certain objective criteria. We will discuss approximability of a special case of this problem via transitive reductions, and inapproximability for a slightly more general case using Raz's parallel repetition theorem.
(Ongoing work with Piotr Berman, Marek Karpinspki, Gyorgy Turan and others. None of the results have been published yet.)