| Presentation | 2005-04-18 Branch-and-Bound Algorithms for MAX-2-SAT Yuichi KOGA, Koji NONOBE, Mutsunori YAGIURA, Hiroshi NAGAMOCHI, Toshihide IBARAKI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | MAX-2-SAT is one of the representative combinatorial problems and it is known to be NP-hard. It is stated as follows : Given a set of m clauses involving n propositional variables, where each clause contains at most two literals, find a truth assignment that maximizes the total weight of satisfied clauses. For MAX-2-SAT, exact algorithms such as branch-and-bound method have been receieving much attention recently. However, to the best of our knowledge, there is no effective method for computing lower bounds on the total weight of unsatisfied clauses, resulting in a large number of nodes in the branch-and-bound search tree. In this paper, we propose two algorithms that compute lower bounds of high quality. Both are based on a directed graph that represents conflicts among clauses, and one of them uses a set covering representation of MAX-2-SAT. Computational comparisons on benchmark instances disclose that these algorithms are highly effective in reducing the number of search tree nodes as well as computation time. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Branch-and-Bound / MAX-2-SAT / set covering problem |
| Paper # | COMP2005-3 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2005/4/11(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Branch-and-Bound Algorithms for MAX-2-SAT |
| Sub Title (in English) | |
| Keyword(1) | Branch-and-Bound |
| Keyword(2) | MAX-2-SAT |
| Keyword(3) | set covering problem |
| 1st Author's Name | Yuichi KOGA |
| 1st Author's Affiliation | Graduate School of Informatics, Kyoto University() |
| 2nd Author's Name | Koji NONOBE |
| 2nd Author's Affiliation | Graduate School of Informatics, Kyoto University |
| 3rd Author's Name | Mutsunori YAGIURA |
| 3rd Author's Affiliation | Graduate School of Informatics, Kyoto University |
| 4th Author's Name | Hiroshi NAGAMOCHI |
| 4th Author's Affiliation | Graduate School of Informatics, Kyoto University |
| 5th Author's Name | Toshihide IBARAKI |
| 5th Author's Affiliation | Department of Informatics, School of Science and Technology, Kwansei Gakuin University |
| Date | 2005-04-18 |
| Paper # | COMP2005-3 |
| Volume (vol) | vol.105 |
| Number (no) | 7 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |