Optimizing misdirection

ABSTRACT

In this paper we consider the following problem. Given a (d + 1)-claw free graph G = (V, E, w) where w : V → R+, maximize w(A) where A is an independent set in G. Our focus is to minimize the approximation ratio (optimum/obtained) in polynomial time that does not depend on d. Our approach is to apply local improvements of size 2, using a "misdirected" criterion, i.e. w^α(A) rather than w(A). We find the optimal value of α for every d, and the resulting ratio is roughly 0.667d for d = 3, 0.651d for d = 4 and 0.646d for d > 4.

REFERENCES

• 1: Paola Alimonti , Viggo Kann, Some APX-completeness results for cubic graphs, Theoretical Computer Science, v.237 n.1-2, p.123-134, April 28, 2000 [doi>10.1016/S0304-3975(98)00158-3]
• 2: Noga Alon , Uriel Feige , Avi Wigderson , David Zuckerman, Derandomized graph products, Computational Complexity, v.5 n.1, p.60-75, Jan. 1995 [doi>10.1007/BF01277956]
• 3: Esther M. Arkin , Refael Hassin, On Local Search for Weighted k-Set Packing, Proceedings of the 5th Annual European Symposium on Algorithms, p.13-22, September 15-17, 1997
• 4: Vineet Bafna , Babu Narayanan , R. Ravi, Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles), Discrete Applied Mathematics, v.71 n.1-3, p.41-53, Dec. 5, 1996 [doi>10.1016/S0166-218X(96)00063-7]
• 5: Piotr Berman, A d/2 approximation for maximum weight independent set in d-claw free graphs, Nordic Journal of Computing, v.7 n.3, p.178-184, Fall 2000
• 6: Barun Chandra , Magnús Halldórsson, Greedy local improvement and weighted set packing approximation, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.169-176, January 17-19, 1999, Baltimore, Maryland, United States
• 7: S. de Vries and R. Vohra, Combinatorial Auctions: A Survey. Manuscript, January 12th, 2001. Available at http://citeseer.nj.nec.com
• 8: Magnús M. Halldórsson, Approximations of Independent Sets in Graphs, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.1-13, July 18-19, 1998
• 9: M. M. Halldórsson and H. C. Lau, Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and 3-coloring, J. Graph Algorithms & Applications 1(3): 1--13, 1997.
• 10: J. Håstad, Clique is hard to approximate within n1-e, FOCS '96, pp. 627--363, 1996.
• 11: D. S. Hochbaum, Efficient bounds for the stable set, vertex cover, and set packing problems, Discrete Applied Mathematics 6: 243--254, 1983.
• 12: C. A. J. Hurkens , A. Schrijver, On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM Journal on Discrete Mathematics, v.2 n.1, p.68-72, February 1989 [doi>10.1137/0402008]
• 13: D. Nakamura and A. Tamura, A revision of Minty's algorithm for finding a maximum weight stable set of a claw-free graph, Manuscript, 1999. Available at http://citeseer.nj.nec.com
• 14: Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, v.135 n.1-2, p.1-54, 02/01/2002 [doi>10.1016/S0004-3702(01)00159-X]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Theory