| Presentation | 2010-03-12 On the standard local search for the independent set problem in d-claw free graphs Kazuyuki KITAYAMA, Toshihiro FUJITO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The independent set problem in graphs is such an NP-hard problem that is known to be hard even to approximate effectively in polynomial time. When graphs are restricted to be d-claw free, while the standard local search heuristic can approximate it within a factor of (d-1+ε)/2(ε>0) in the unweighted case, its performance deteriorates down close to that of the greedy heuristic in case of general weights. The best performance guarantee known today for such instances is due to the Ω(n^d) time d/2-approximation algorithm, or the 2(d-1)/3-approximation algorithm running in polynomial time for any d. Either algorithm is based on the non-standard local search using "incorrect" objective functions. This paper studies the effectiveness of the standard local search for d-claw free instances under constrained weight distributions. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | independent set / approximation algorithm / local search |
| Paper # | COMP2009-54 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/3/5(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) | On the standard local search for the independent set problem in d-claw free graphs |
| Sub Title (in English) | |
| Keyword(1) | independent set |
| Keyword(2) | approximation algorithm |
| Keyword(3) | local search |
| 1st Author's Name | Kazuyuki KITAYAMA |
| 1st Author's Affiliation | Department of Information and Computer Sciences, Toyohashi University of Technology() |
| 2nd Author's Name | Toshihiro FUJITO |
| 2nd Author's Affiliation | Department of Information and Computer Sciences, Toyohashi University of Technology |
| Date | 2010-03-12 |
| Paper # | COMP2009-54 |
| Volume (vol) | vol.109 |
| Number (no) | 465 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |