zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Local search for the minimum label spanning tree problem with bounded color classes. (English) Zbl 1046.90070
Summary: In the minimum label spanning tree problem, the input consists of an edge-colored undirected graph, and the goal is to find a spanning tree with the minimum number of different colors. We investigate the special case where every color appears at most $r$ times in the input graph. This special case is polynomially solvable for $r=2$, and NP- and APX-complete for any fixed $r\geqslant 3$. We analyze local search algorithms that are allowed to switch up to $k$ of the colors used in a feasible solution. We show that for $k=2$ any local optimum yields an $(r+1)/2$-approximation of the global optimum, and that this bound is tight. For every $k\geqslant 3$, there exist instances for which some local optima are a factor of $r/2$ away from the global optimum.

90C27Combinatorial optimization
90C59Approximation methods and heuristics
90C40Markov and semi-Markov decision processes
05C85Graph algorithms (graph theory)
Full Text: DOI
[1] Alimonti, P.; Kann, V.: Some APX-completeness results for cubic graphs. Theoret. comput. Sci. 237, 123-134 (2000) · Zbl 0939.68052
[2] Arkin, E. M.; Hassin, R.: On local search for weighted k-set packing. Math. oper. Res. 23, 640-648 (1998) · Zbl 0977.90038
[3] Ausiello, G.; Protasi, M.: Local search, reducibility and approximability of NP-optimization problems. Inform. process. Lett. 54, 73-79 (1995) · Zbl 1022.68561
[4] Chang, R. -S.; Leu, S. -J.: The minimum labeling spanning trees. Inform. process. Lett. 63, 277-282 (1997) · Zbl 0938.90063
[5] Erdo?s, P.; Sachs, H.: Reguläre graphen gegebener taillenweite mit minimaler knotenzahl. Wiss. Z. Martin-luther-univ. Halle-Wittenberg 12, 251-257 (1963)
[6] Finn, G.; Horowitz, E.: A linear time approximation algorithm for multiprocessor scheduling. Bit 19, 312-320 (1979) · Zbl 0413.68038
[7] H.N. Gabow, M. Stallman, Efficient algorithms for graphic matroid intersection and parity, Proceedings of the 12th International Colloquium on Automata, Languages, and Programming (ICALP’1985), Springer, Lecture Notes in Computer Science 194, Springer, Berlin, 1985, pp. 210--220.
[8] Hurkens, C. A. J.; Schrijver, A.: 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 J. Discrete math. 2, 68-72 (1989) · Zbl 0733.05003
[9] Krumke, S. O.; Wirth, H. -C.: On the minimum label spanning tree problem. Inform. process. Lett. 66, 81-85 (1998) · Zbl 0938.90064
[10] Lovász, L.; Plummer, M. D.: Matching theory. (1986) · Zbl 0618.05001
[11] H. Lu, R. Ravi, The power of local optimization: approximation algorithms for maximum-leaf spanning tree. Proceedings of the 13th Annual Allerton Conference on Communication, Control, and Computing, 1992, pp. 533--542.
[12] Mohar, B.: Face covers and the genus problem for apex graphs. J. combin. Theory B 82, 102-117 (2001) · Zbl 1025.05019
[13] Papadimitriou, C. H.; Yannakakis, M.: Optimization, approximation, and complexity classes. J. comput. System sci. 43, 425-440 (1991) · Zbl 0765.68036
[14] P. Schuurman, T. Vredeveld, Performance guarantees of local search for multiprocessor scheduling. Proceedings of the Eighth Conference on Integer Programming and Combinatorial Optimization (IPCO’2001), Springer, Lecture Notes in Computer Science 2081, Springer, Berlin, 2001, pp. 370--382. · Zbl 0987.68004
[15] T. Vredeveld, Combinatorial approximation algorithms: guaranteed versus experimental performance, Ph.D. Thesis, TU Eindhoven, The Netherlands, 2002. · Zbl 1140.90310
[16] Wan, Y.; Chen, G.; Xu, Y.: A note on the minimum label spanning tree. Inform. process. Lett. 84, 99-101 (2002) · Zbl 1042.68055