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?


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.