Berman, Piotr; Krysta, Piotr Optimizing misdirection. (English) Zbl 1094.68604 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]. Cited in 3 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science PDF BibTeX XML Cite \textit{P. Berman} and \textit{P. Krysta}, in: Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2003, Baltimore, MD, USA, January 12--14, 2003. New York, NY: Association for Computing Machinery; Philadelphia, PA: Society for Industrial and Applied Mathematics. 192--201 (2003; Zbl 1094.68604)