@inproceedings{9199fa3a5d0240b28b711b180131eb47,

title = "A min-edge cost flow framework for capacitated covering problems",

abstract = "In this work, we introduce the Cov-MECF framework, a special case of minimum-edge cost flow in which the input graph is bipartite. We observe that several important covering (and multi-covering) problems are captured in this unifying model and introduce a new heuristic LPO for any problem in this framework. The essence of LPO harnesses as an oracle the fractional solution in deciding how to greedily modify the partial solution. We empirically establish that this heuristic returns solutions that are higher in quality than those of Wolsey's algorithm. We also apply the analogs of Leskovec et. al.'s [25] optimization to LPO and introduce a further freezing optimization to both algorithms. We observe that the former optimization generally benefits LPO more than Wolsey's algorithm, and that the additional freezing step often corrects suboptimalities while further reducing the number of subroutine calls. We tested these implementations on randomly generated testbeds, several instances from the Second DIMACS Implementation Challenge and a couple networks modeling realworld dynamics.",

author = "Jessica Chang and Samir Khuller",

note = "Publisher Copyright: Copyright {\textcopyright} SIAM. Copyright: Copyright 2015 Elsevier B.V., All rights reserved.; 15th Workshop on Algorithm Engineering and Experiments, ALENEX 2013 ; Conference date: 07-01-2013",

year = "2013",

doi = "10.1137/1.9781611972931.2",

language = "English (US)",

series = "Proceedings of the Workshop on Algorithm Engineering and Experiments",

publisher = "Society for Industrial and Applied Mathematics Publications",

pages = "14--25",

editor = "Norbert Zeh and Peter Sanders",

booktitle = "2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, ALENEX 2013",

address = "United States",

}