It is known that the problem of fractional set cover
can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows how to do so.
The running time depends on the "width" of the problem, which equals to the number of sets in the unweighted case. However, in the weighted case, the width of the problem depends on the weight function, hence the running time is exponential with respect to the representation of the problem. Is there a way to overcome this issue? Either a way to reduce it to polynomial running time or proof that it's impossible (under plausible complexity assumptions)?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, fractional weighted set cover and, indeed, all explicitly given packing/covering LP's can be solved using multiplicative-weights algorithms in poly time independent of the width. There are many papers in this line of work. The earliest are probably due to Garg and Konemann. See e.g. https://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers/14388#14388 .
