Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
type: Item
instance of: scholarly article
title: Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
zbMATH Open document ID: 1285.68215
author: Christos Koufogiannakis
author: Neal E. Young
published in: Algorithmica
publication date: 2013-05-16T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 6163653
zbMATH Keywords: covering
zbMATH Keywords: linear programming
zbMATH Keywords: approximation algorithms
zbMATH Keywords: local ratio
zbMATH Keywords: primal-dual
zbMATH Keywords: vertex cover
zbMATH Keywords: set cover
zbMATH Keywords: integer linear programming
zbMATH Keywords: online algorithms
zbMATH Keywords: competitive analysis
zbMATH Keywords: submodular cost
zbMATH Keywords: paging
zbMATH Keywords: caching
MaRDI profile type: Publication
full work available at URL: s00453-012-9629-3
OpenAlex ID: W2174359169
cites work: On generalized connection caching
cites work: A Primal-Dual Randomized Algorithm for Weighted Paging
cites work: Q3549707
cites work: One for the price of two: a unified approach for approximating covering problems
cites work: A linear-time approximation algorithm for the weighted vertex cover problem
cites work: Q3337223
cites work: Efficient algorithms for integer programs with two variables per constraint.
cites work: On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
cites work: Rounding algorithms for covering problems
cites work: Automata, Languages and Programming
cites work: How well can primal-dual and local-ratio algorithms perform?
cites work: Algorithms – ESA 2005
cites work: Online Primal-Dual Algorithms for Covering and Packing
cites work: Q4952606
cites work: New Ressults on Server Problems
cites work: Q2934585
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Connection caching
cites work: Connection caching: Model and algorithms.
cites work: On the hardness of approximating minimum vertex cover
cites work: Competitive paging algorithms
cites work: A fast approximation algorithm for the multicovering problem
cites work: Greed is good: Approximating independent sets in sparse and bounded-degree graphs
cites work: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
cites work: Some optimal inapproximability results
cites work: Network design for information networks
cites work: Approximation Algorithms for the Set Covering and Vertex Cover Problems
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: Q3002852
cites work: Submodular Function Minimization under Covering Constraints
cites work: Q4077442
cites work: Approximation algorithms for combinatorial problems
cites work: Competitive snoopy caching
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Approximation algorithms for covering/packing integer programs
cites work: Distributed and parallel algorithms for weighted vertex cover and other covering problems
cites work: Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
cites work: Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
cites work: Distributed algorithms for covering, packing and maximum weighted matching
cites work: The price of being near-sighted
cites work: Q4910746
cites work: On the ratio of optimal integral and fractional covers
cites work: A strongly competitive randomized paging algorithm
cites work: Ramsey numbers and an approximation algorithm for the vertex cover problem
cites work: A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
cites work: A faster strongly polynomial time algorithm for submodular function minimization
cites work: Linear programming without the matrix
cites work: Approximability of Sparse Integer Programs
cites work: Approximability of sparse integer programs
cites work: Hedging uncertainty: approximation algorithms for stochastic optimization problems
cites work: Improved Approximation Guarantees for Packing and Covering Integer Programs

Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost (cites work)
cites work: New approaches to covering and packing problems

Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost (cites work)
cites work: Q4782696

Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost (cites work)
cites work: Q3138959

Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost (cites work)
cites work: Q4250168

Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost (cites work)
cites work: On-line file caching

Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost (DOI)
DOI: 10.1007/S00453-012-9629-3