0
$\begingroup$

Suppose I have a facility location problem with all service costs 0 (or infinity (in particular service costs are not metric)) such that the edges $ij$ for which facility $i$ can service client $j$ with cost 0 (together with the facilities and clients) forms a planar graph.

What is the maximum integrality gap of such an LP?

This is exactly set cover with the additional constraint that the set element incidence graph ( that is a graph with nodes $v_S$ for every set $S$ and nodes $v_e$ for every element $e$ and the edges $v_S v_e$ for elements $e$ and sets $S$ for which $e \in S$) is planar.

What is the LP gap if the graph is not planar but say fixed genus/minor free etc?

Also, does this problem have a name like planar/bounded genus set cover or something?

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.