Optimizing misdirection. (English) Zbl 1094.68604

Berman, Piotr; Krysta, Piotr

Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Baltimore, MD, USA, January 12–14, 2003. New York, NY: Association for Computing Machinery; Philadelphia, PA: Society for Industrial and Applied Mathematics (ISBN 0-89871-538-5/pbk). 192-201 (2003).

Summary: We consider the following problem. Given a \((d+1)\)-claw free graph \(G=(V,E,w)\) where \(w:V\to\mathbb{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^\alpha(A)\) rather than \(w(A)\). We find the optimal value of \(\alpha\) 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\).
For the entire collection see [Zbl 1006.00017].

MSC:

68R10

Graph theory (including graph drawing) in computer science