# zbMATH — the first resource for mathematics

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].

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science