| Home | Organizers | Proceedings Editors | Proceedings Contributors | Search | | ||
|
|
|||
|
||||
|
|
||||
| Title: | EFFICIENT BRANCH-AND-BOUND ALGORITHMS FOR WEIGHTED MAX-2-SAT | |
| DOI No: | 10.1142/9781860948534_0018 | |
| Source: | INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD (pp 120-124) | |
| Author(s): | Y. KOGA
Kyoto University, Yoshidahonmachi, Sakyo-ku, Kyoto, 606–8501, Japan M. YAGIURA Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464–8603, Japan K. NONOBE Hosei University, 3–7–2 Kajino-cho, Koganei-shi, Tokyo, 184–8584, Japan T. IMAMICHI Kyoto University, Yoshidahonmachi, Sakyo-ku, Kyoto, 606–8501, Japan H. NAGAMOCHI Kyoto University, Yoshidahonmachi, Sakyo-ku, Kyoto, 606–8501, Japan T. IBARAKI Kwansei Gakuin University, 2–1 Gakuen, Sanda-shi, Hyogo, 669–1337, Japan |
|
| Abstract: | Given a set of m clauses on n propositional variables, where each clause contains at most two literals and is weighted by a positive real, MAX-2-SAT asks to find a truth assignment that maximizes the total weight of satisfied clauses. In this paper, we propose two branch-and-bound algorithms for solving MAX-2-SAT exactly. Our algorithms feature two new transformation rules and two efficient algorithms for computing lower bounds. 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 of branch-and-bound algorithms. | |
| Full Text: | View full text in PDF format (288KB) | |
| TOC: | Back to Table of Contents | |
|
||