Welcome to Fnd2012 Open Problems, where you can ask questions and receive answers from other members of the community.

Approximating Star Cover Problems

0 votes

(Sorry about the LaTeX symbols)

Given a set of points $S$, a distance function $d$, an integer $k$ and a bound $B$ on maximum load of any facility, the problem is to decide whether we
can select $k$ facilities in $S$ and serve other points by these facilities such
that the maximum load of any facility is $B$. The load on a facility $f$
is the sum of distances to the clients it serves. Alternately, since an open
facility together with the assigned clients, forms a star and its load is exactly
equal to the cost of the star, we can call this the Star Cover Decision Problem
(SCDP). We can consider two optimization versions of the above stated decision problem:

Minimum Load Star Cover or MLSC : Given $S$, $d$ and an integer $k$,
minimize the maximum load on each facility.
 

Minimum Cardinality Star Cover or MCSC : Given $S$, $d$ and a bound $B$ on
maximum load, minimize the number of facilities to be opened, such that the load on each facility is at most $B$.

We can also consider a bicriteria approximation for the decision problem i.e. given
$S$, $d$, $k$ and $B$ find an $(\alpha,\beta)$-approximation, such that at most
$\alpha k$ facilities are opened and maximum load on a facility is at most $\beta
B$.


Known results

Arkin, Hassin and Levin consider the Minimum Cardinality Star Cover problem, where distance $d$ is a metric and give a $(2\alpha+1)$-approximation for the problem, where $\alpha$ is the best approximation ratio of the $k$-median problem.

Even, Garg, Konemann, Ravi and Sinha give a bicriteria approximation of $(4,4)$ for the case when $d$ is a metric i.e. for given $k$ and $B$, their algorithm opens at most $4k$ facilities and the completion time is at most $4B$. This was improved to a $(3+\epsilon,3+\epsilon)$ approximation by Arkin, Hassin and Levin.

The star cover decision problem (SCDP) is NP-complete, even when the distance function $d$ is a line metric or a star metric. Furthermore, the problem remains hard even if the facilities to open are specified. The proofs of hardness for line and star metrics are by reductions from 3-PARTITION and MAKESPAN respectively.

The Minimum Cardinality Star Cover or MCSC problem is $\Omega(\log n)$-hard to approximate if the distance function, $d$, is not a metric, by a reduction from set cover, where $|S|=n$. A similar analysis as that of greedy algorithm for set cover, gives a $\log n$-approximation for the MCSC problem in the general case. There is a $2$-approximation for the case when the distance function is a line metric.

For the Minimum Load Star Cover or MLSC problem, the LP relaxation of a natural IP formulation has a large integrality gap. There is a $3$-approximation when the distance function is a star metric. In the case of distance function being a line metric, it can be shown that if every point is assigned to either the closest facility to the right or closest facility to the left then the maximum load can be a factor $k$ times worse than the optimum.

OPEN PROBLEM

Give a nontrivial approximation for the MLSC problem or show a lower bound for the approximation factor. Even the case when the input is a line metric is open.


References

E. Arkin, R. Hassin and A. Levin. Approximations for minimum and min-max vehicle
routing problems, Journal of Algorithms, 59(1), 2006.

G. Even, N. Garg, J. Koenemann, R.Ravi, A. Sinha. Covering Graphs using Trees and Stars. In Proc of the 6th International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems, 2003.
 

Acknowledgment: Thanks to Vineet Goyal for working out some of the above observations.

asked Aug 1, 2012 by ravi (120 points)
edited Aug 1, 2012 by ravi