| Presentation | 1997/10/31 Improvement of the MAX SAT Approximation Algorithm with Perturbation Takao Ono, Tomio Hirata, Takao Asano, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | MAX SAT (the maximum satisfiability problem) is: given a set of clauses with positive weight, find the truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we show that the perturbation is effective to improve the approximation algorithm for MAX SAT, in particular, we can obtain the 0.7685-approximation algorithm with perturbation. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | approximation algorithm / MAX SAT / perturbation / ramdomized algorithm |
| Paper # | COMP97-48 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1997/10/31(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) | Improvement of the MAX SAT Approximation Algorithm with Perturbation |
| Sub Title (in English) | |
| Keyword(1) | approximation algorithm |
| Keyword(2) | MAX SAT |
| Keyword(3) | perturbation |
| Keyword(4) | ramdomized algorithm |
| 1st Author's Name | Takao Ono |
| 1st Author's Affiliation | Department of Electronics, Faculty of Engineering, Nagoya University() |
| 2nd Author's Name | Tomio Hirata |
| 2nd Author's Affiliation | Department of Electronics, Faculty of Engineering, Nagoya University |
| 3rd Author's Name | Takao Asano |
| 3rd Author's Affiliation | Department of Information and System Engineering, Chuo University |
| Date | 1997/10/31 |
| Paper # | COMP97-48 |
| Volume (vol) | vol.97 |
| Number (no) | 356 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |