A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances

Wahlström, Magnus

doi:10.1007/978-3-540-79723-4_19

Datensatz

DATENSATZ AKTIONENEXPORT

Zur Ablage hinzufügen

Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben

Konferenzbeitrag

A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances

MPG-Autoren

/persons/resource/persons45687

Wahlström, Magnus
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen

Es sind keine externen Ressourcen hinterlegt

Volltexte (beschränkter Zugriff)

Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.

Volltexte (frei zugänglich)

Es sind keine frei zugänglichen Volltexte in PuRe verfügbar

Ergänzendes Material (frei zugänglich)

Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Zitation

Wahlström, M. (2008). A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances. In M. Grohe, & R. Niedermeier (Eds.), Parameterized and Exact Computation (pp. 202-213). Berlin: Springer. doi:10.1007/978-3-540-79723-4_19.

Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000F-1B18-E

Zusammenfassung

We give an algorithm for counting the number of max-weight solutions to a 2SAT formula, and improve the bound on its running time to $O(1.2377^n)$. The main source of the improvement is a refinement of the method of analysis, where we extend the concept of compound (piecewise linear) measures to multivariate measures, also allowing the optimal parameters for the measure to be found automatically. This method extension should be of independent interest.