ICAR Research Data Repository for Knowledge Management
Upper bounds for MaxSat : further improved
DSpace at IIT Bombay
View Archive Info| Field | Value | |
| Title |
Upper bounds for MaxSat : further improved
|
|
| Creator |
BANSAL, N
RAMAN V |
|
| Subject |
satisfiability
algorithms |
|
| Description |
Given a boolean CNF formula F of length \F\ (sum of the number of variables in each clause) with m clauses on n variables, we prove the following results. The MAXSAT problem, which asks for an assignment satisfying the maximum number of clauses of F, can be solved in O(1.341294(m)\F\) time. The parameterized version of the problem, that is determining whether there exists an assignment satisfying at least k clauses of the formula (for some integer k), can be solved in O(k(2)1.380278(k) + \F\) time. MAXSAT can be solved in O(1.105729(\F\)\F\) time. These bounds improve the recent bounds of respectively O(1.3972(m)\F\), O(k(2)1.3995(k) + \F\) and O(1.12791(\F\)\F\) due to Niedermeier and Rossmanith [11] for these problems. Our last bound comes quite close to the O(1.07578(\F\)\F\) bound of Hirsch[6] for the Satisfiability problem (not MAXSAT).
|
|
| Publisher |
SPRINGER-VERLAG BERLIN
|
|
| Date |
2011-10-23T12:57:03Z
2011-12-15T09:11:10Z 2011-10-23T12:57:03Z 2011-12-15T09:11:10Z 2000 |
|
| Type |
Article; Proceedings Paper
|
|
| Identifier |
ALGORITHMS AND COMPUTATIONS,1741,247-258
3-540-66916-7 0302-9743 http://dspace.library.iitb.ac.in/xmlui/handle/10054/15135 http://hdl.handle.net/100/1890 |
|
| Source |
10th Annual International Symposium on Algorithms and Computation (ISAAC 99),CHENNAI, INDIA,DEC 16-18, 1999
|
|
| Language |
English
|
|