Approximating min sum set cover
From MaRDI portal
Publication:1884768
DOI10.1007/s00453-004-1110-5zbMath1082.68126OpenAlexW2134331592WikidataQ106094567 ScholiaQ106094567MaRDI QIDQ1884768
László Lovász, Uriel Feige, Prasad Tetali
Publication date: 5 November 2004
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-004-1110-5
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Ramsey theory (05D10)
Related Items (35)
Ignorant vs. Anonymous Recommendations ⋮ Approximation and complexity of multi-target graph search and the Canadian traveler problem ⋮ Ranking with submodular functions on a budget ⋮ Network construction/restoration problems: cycles and complexity ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ A General Framework for Approximating Min Sum Ordering Problems ⋮ Chromatic Edge Strength of Some Multigraphs ⋮ A note on the generalized min-sum set cover problem ⋮ A closest vector problem arising in radiation therapy planning ⋮ Minimum sum set coloring of trees and line graphs of trees ⋮ Approximating optimal binary decision trees ⋮ Tight approximation algorithms for ordered covering ⋮ Improved analysis of two algorithms for min-weighted sum bin packing ⋮ Maximum subset intersection ⋮ Decision-theoretic troubleshooting: hardness of approximation ⋮ On the inapproximability of maximum intersection problems ⋮ Tight results on minimum entropy set cover ⋮ Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems ⋮ Preemptive and non-preemptive generalized min sum set cover ⋮ Minimum Entropy Combinatorial Optimization Problems ⋮ Minimum entropy combinatorial optimization problems ⋮ Minimum sum edge colorings of multicycles ⋮ Minimum Weighted Sum Bin Packing ⋮ Tree optimization based heuristics and metaheuristics in network construction problems ⋮ Min-sum bin packing ⋮ Assortment optimization over time ⋮ On competitive recommendations ⋮ On the distributed complexity of the semi-matching problem ⋮ Minimum entropy orientations ⋮ On the minimum sum coloring of \(P_4\)-sparse graphs ⋮ Independent sets in bounded-degree hypergraphs ⋮ Weighted sum coloring in batch scheduling of conflicting jobs ⋮ Minimum Sum Coloring of P4-sparse graphs ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems ⋮ Precedence-Constrained Min Sum Set Cover
This page was built for publication: Approximating min sum set cover
