• Algorithmica 66(1):113-152(2013); ICALP'09

  With Christos Koufogiannakis^*
  This paper describes a simple greedy Δ-approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be expressed as the intersection of arbitrary (closed upwards) covering constraints, each of which constrains at most Δ variables. (A simple example is Vertex Cover, with Δ = 2.) The algorithm generalizes previous approximation algorithms for fundamental covering problems and online paging and caching problems.
  
  (For distributed implementations of these algorithms, see Distributed algorithms for covering, packing and maximum weighted matching .)

  Journal version of [2009].

  • more...
  •   full text
    
  •   slides
    
  •   bibtex
    
  •   google scholar
    
  •   doi
    

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.