Continuous facility location on graphs
研究在无向图上用最少设施覆盖整个图的问题，设施可放在顶点或边上。发现当覆盖半径为单位分数时多项式可解，否则NP难。
Abstract We study a continuous facility location problem on undirected graphs where all edges have unit length and where the facilities may be positioned on the vertices as well as on interior points of the edges. The goal is to cover the entire graph with a minimum number of facilities with covering range $$\delta >0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> . In other words, we want to position as few facilities as possible subject to the condition that every point on every edge is at distance at most $$\delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> </mml:math> from one of these facilities. We investigate this covering problem in terms of the rational parameter $$\delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> </mml:math> . We prove that the problem is polynomially solvable whenever $$\delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> </mml:math> is a unit fraction, and that the problem is NP-hard for all non unit fractions $$\delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>δ</mml:mi> </mml:math> . We also analyze the parametrized complexity with the solution size as parameter: The resulting problem is fixed parameter tractable for $$\delta <3/2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo><</mml:mo> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , and it is W [2]-hard for $$\delta \ge 3/2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> .