• • 2001Sequential and parallel algorithms for mixed packing and covering
  IEEE Symposium on Foundations of Computer Science
  Mixed packing and covering problems are problems that can be formulated as linear programs using only non-negative coefficients. Examples include multicommodity network flow, the Held-Karp lower bound on TSP, fractional relaxations of set cover, bin-packing, knapsack, scheduling problems, minimum-weight triangulation, etc. This paper gives approximation algorithms for the general class of problems. The sequential algorithm can be implemented to find an $(1\pm\epsilon)$-approximate solution in $O(\epsilon^{-2}\log m)$ linear-time iterations.
  
  For $\epsilon = O(1)$, these algorithms are currently the fastest known for the general problem. The results generalize previous work on pure packing and covering (the special case when the constraints are all ``less-than'' or all ``greater-than'') by Michael Luby and Noam Nisan [1993]; and Naveen Garg and Jochen Konemann [1998]; and Lisa Fleischer [1999]

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

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