Porschen, Stefan
(2007).
On variable-weighted exact satisfiability problems.
Annals of mathematics and artificial intelligence, 51 (1).
pp. 27-54.
|
PDF
zaik2006-526.pdf - Submitted Version Download (369kB) | Preview |
Abstract
We show that the NP-hard optimization problems minimum and maximum weight exact satisfiability (XSAT) for a CNF formula C over n propositional variables equipped with arbitrary real-valued weights can be solved in O(|C|2^{0.2441n}) time. To the best of our knowledge, the algorithms presented here are the first handling weighted XSAT optimization versions in non-trivial worst case time. We also investigate the corresponding weighted counting problems, namely we show that the number of all minimum, resp. maximum, weight exact satisfiability solutions of an arbitrarily weighted formula can be determined in O(n^2cdot |C|+2^{0.40567n}) time. In recent years only the unweighted counterparts of these problems have been studied cite{dahl,dahl2,porschen}.
| Item Type: | Journal Article | ||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-549028 | ||||||||
| Journal or Publication Title: | Annals of mathematics and artificial intelligence | ||||||||
| Volume: | 51 | ||||||||
| Number: | 1 | ||||||||
| Page Range: | pp. 27-54 | ||||||||
| Date: | 2007 | ||||||||
| Language: | English | ||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||
| Subjects: | Data processing Computer science | ||||||||
| Refereed: | No | ||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54902 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |