A min-edge cost flow framework for capacitated covering problems

Jessica Chang, Samir Khuller

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publication2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, ALENEX 2013
EditorsNorbert Zeh, Peter Sanders
PublisherSociety for Industrial and Applied Mathematics Publications
Pages14-25
Number of pages12
ISBN (Electronic)9781611972535
DOIs
StatePublished - 2013
Event15th Workshop on Algorithm Engineering and Experiments, ALENEX 2013 - New Orleans, United States
Duration: Jan 7 2013 → …

Publication series

NameProceedings of the Workshop on Algorithm Engineering and Experiments
ISSN (Print)2164-0300

Conference

Conference15th Workshop on Algorithm Engineering and Experiments, ALENEX 2013
CountryUnited States
CityNew Orleans
Period1/7/13 → …

ASJC Scopus subject areas

  • Engineering(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A min-edge cost flow framework for capacitated covering problems'. Together they form a unique fingerprint.

Cite this