Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 08, 2007, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Dominik Scheder
In Partial Satisfaction, we aim for statements of the following types:
'In every CNF formula obeying certain constraints, we can satisfy at least a fraction r of all clauses'.
For example, in every 3-CNF formula, we can satisfy at least 7/8 of all clauses. A family of formulas intensively studied in this context is the family of k-satisfiable formulas. Call a CNF formula k-satisfiable if every subformula of at most k clauses is satisfiable. What fraction of clauses can one satisfy in every such formula? Call this fraction r_k. The values of r_k are known for small k, e.g. r_1 = 1/2, r_2 = 0.619 and r_3 = 2/3. We know that they converge to 3/4 as k grows. We will sketch the main ideas of the proof of this fact.
One can define the values r_k for weighted as well as for unweighted formulas (this notion will be made precise in the talk). As we will see, this makes a difference. If time allows, I will show some results about the unweighted case.
Automatic MiSe System Software Version 1.4803M | admin login