Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1046.90070
Brüggemann, Tobias; Monnot, Jérôme; Woeginger, Gerhard J.
Local search for the minimum label spanning tree problem with bounded color classes. (English)
[J] Oper. Res. Lett. 31, No. 3, 195-201 (2003). ISSN 0167-6377

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$.\par 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.

MSC 2000:: *90C27 Combinatorial programming
90C59 Approximation methods and heuristics
90C40 Markov decision processes, etc.
05C85 Graphic algorithms

Keywords: Graph algorithms; Approximation algorithms; Combinatorial optimization; Local search; Complexity; APX-completeness

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]