Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
From MaRDI portal
Publication:1949749
DOI10.1007/S00453-012-9629-3zbMath1285.68215OpenAlexW2174359169MaRDI QIDQ1949749
Christos Koufogiannakis, Neal E. Young
Publication date: 16 May 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9629-3
linear programmingcoveringcompetitive analysisonline algorithmsinteger linear programmingapproximation algorithmsvertex coverpagingcachingset coverprimal-duallocal ratiosubmodular cost
Integer programming (90C10) Linear programming (90C05) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (18)
Primal-Dual Algorithms for Precedence Constrained Covering Problems ⋮ Primal-dual algorithms for precedence constrained covering problems ⋮ Group parking permit problems ⋮ Algorithms for maximizing monotone submodular function minus modular function under noise ⋮ On improved interval cover mechanisms for crowdsourcing markets ⋮ Unnamed Item ⋮ Precedence-constrained covering problems with multiplicity constraints ⋮ Approximation algorithm for the multicovering problem ⋮ A note on submodular function minimization with covering type linear constraints ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ Minimization problems with non-submodular cover constraint ⋮ Online paging with heterogeneous cache slots ⋮ An approximation algorithm for the partial covering 0-1 integer program ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ Precedence-constrained covering problems with multiplicity constraints ⋮ Multi-dimensional vector assignment problems ⋮ Online file caching with rejection penalties ⋮ New approximations and hardness results for submodular partitioning problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximability of sparse integer programs
- Distributed algorithms for covering, packing and maximum weighted matching
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- A strongly competitive randomized paging algorithm
- On the hardness of approximating minimum vertex cover
- A faster strongly polynomial time algorithm for submodular function minimization
- Efficient bounds for the stable set, vertex cover and set packing problems
- A fast approximation algorithm for the multicovering problem
- Competitive snoopy caching
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Rounding algorithms for covering problems
- Connection caching: Model and algorithms.
- On-line file caching
- On generalized connection caching
- One for the price of two: a unified approach for approximating covering problems
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- Approximation algorithms for covering/packing integer programs
- Connection caching
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Online Primal-Dual Algorithms for Covering and Packing
- How well can primal-dual and local-ratio algorithms perform?
- New Ressults on Server Problems
- The price of being near-sighted
- Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
- Approximability of Sparse Integer Programs
- Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
- A Greedy Heuristic for the Set-Covering Problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Competitive paging algorithms
- Improved Approximation Guarantees for Packing and Covering Integer Programs
- Distributed and parallel algorithms for weighted vertex cover and other covering problems
- Submodular Function Minimization under Covering Constraints
- Linear programming without the matrix
- A Primal-Dual Randomized Algorithm for Weighted Paging
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
- Some optimal inapproximability results
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- Algorithms – ESA 2005
- Automata, Languages and Programming
- Efficient algorithms for integer programs with two variables per constraint.
This page was built for publication: Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
