• ACM Symposium on Principles of Distributed Computing

  With Christos Koufogiannakis^*
  The paper presents distributed and parallel δ-approximation algorithms for covering problems, where δ is the maximum number of variables on which any constraint depends (for example, δ=2 for vertex cover).
  
  Specific results include the following.

  • For weighted vertex cover, the first distributed 2-approximation algorithm taking O(log n) rounds and the first parallel 2-approximation algorithm in RNC. The algorithms generalize to covering mixed integer linear programs (CMIP) with two variables per constraint (δ=2).
  • For any covering problem with monotone constraints and submodular cost, a distributed \(\delta\)-approximation algorithm taking O(log² |C|) rounds, where |C| is the number of constraints. (Special cases include CMIP, facility location, and probabilistic (two-stage) variants of these problems.)

  
  
  (This paper gives distributed implementations of algorithms from Greedy δ-approximation algorithm for covering with arbitrary constraints and submodular cost .)

  Conference version of part of Distributed algorithms for covering, packing and maximum weighted matching.

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

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