On the public citation graph

Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost

https://doi.org/10.1007/s00453-012-9629-3
0 signed · 111 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/11561071_61openalex-snapshot
Online Primal-Dual Algorithms for Covering and Packing Problems
inferredcites →https://doi.org/10.1007/978-3-540-72792-7_19openalex-snapshot
A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
inferredcites →https://doi.org/10.1007/978-3-642-02927-1_53openalex-snapshot
Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
inferredcites →https://doi.org/10.1007/978-3-642-04128-0_8openalex-snapshot
Approximability of Sparse Integer Programs
inferredcites →https://doi.org/10.1007/978-3-642-04355-0_23openalex-snapshot
Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
inferredcites →https://doi.org/10.1007/978-3-662-21708-5_16openalex-snapshot
Approximation Algorithms
inferredcites →https://doi.org/10.1007/bf00290149openalex-snapshot
Ramsey numbers and an approximation algorithm for the vertex cover problem
inferredcites →https://doi.org/10.1007/bf01189992openalex-snapshot
Thek-server dual and loose competitiveness for paging
inferredcites →https://doi.org/10.1007/bf01582131openalex-snapshot
Rounding algorithms for covering problems
inferredcites →https://doi.org/10.1007/bf01759073openalex-snapshot
A strongly competitive randomized paging algorithm
inferredcites →https://doi.org/10.1007/bf01762111openalex-snapshot
Competitive snoopy caching
inferredcites →https://doi.org/10.1007/bf02523693openalex-snapshot
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
inferredcites →https://doi.org/10.1007/s00224-002-1053-7openalex-snapshot
On Generalized Connection Caching
inferredcites →https://doi.org/10.1007/s00446-011-0127-7openalex-snapshot
Distributed algorithms for covering, packing and maximum weighted matching
inferredcites →https://doi.org/10.1007/s00453-001-0124-5openalex-snapshot
On-Line File Caching
inferredcites →https://doi.org/10.1007/s00453-010-9431-zopenalex-snapshot
Approximability of Sparse Integer Programs
inferredcites →https://doi.org/10.1007/s004530010009openalex-snapshot
One for the Price of Two: a Unified Approach for Approximating Covering Problems
inferredcites →https://doi.org/10.1007/s004530010075openalex-snapshot
Efficient Algorithms for Integer Programs with Two Variables per Constraint1
inferredcites →https://doi.org/10.1007/s10107-005-0673-5openalex-snapshot
Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems
inferredcites →https://doi.org/10.1007/s10107-007-0189-2openalex-snapshot
A faster strongly polynomial time algorithm for submodular function minimization
inferredcites →https://doi.org/10.1007/springerreference_57547openalex-snapshot
Approximation Algorithms
inferredcites →https://doi.org/10.1016/0012-365x(75)90058-8openalex-snapshot
On the ratio of optimal integral and fractional covers
inferredcites →https://doi.org/10.1016/0166-218x(83)90080-xopenalex-snapshot
Efficient bounds for the stable set, vertex cover and set packing problems
inferredcites →https://doi.org/10.1016/0166-218x(86)90016-8openalex-snapshot
A fast approximation algorithm for the multicovering problem
inferredcites →https://doi.org/10.1016/0196-6774(81)90020-1openalex-snapshot
A linear-time approximation algorithm for the weighted vertex cover problem
inferredcites →https://doi.org/10.1016/0196-6774(91)90041-vopenalex-snapshot
Competitive paging algorithms
inferredcites →https://doi.org/10.1016/j.jcss.2005.05.002openalex-snapshot
Approximation algorithms for covering/packing integer programs
inferredcites →https://doi.org/10.1016/j.jcss.2007.06.019openalex-snapshot
Vertex cover might be hard to approximate to within 2−ε
inferredcites →https://doi.org/10.1016/s0022-0000(03)00041-2openalex-snapshot
Connection caching: model and algorithms
inferredcites →https://doi.org/10.1016/s0022-0000(74)80044-9openalex-snapshot
Approximation algorithms for combinatorial problems
inferredcites →https://doi.org/10.1016/s0304-0208(08)73101-3openalex-snapshot
A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem
inferredcites →https://doi.org/10.1109/focs.2004.62openalex-snapshot
Stochastic Optimization is (Almost) as easy as Deterministic Optimization
inferredcites →https://doi.org/10.1109/focs.2007.7openalex-snapshot
Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments
inferredcites →https://doi.org/10.1109/focs.2009.31openalex-snapshot
Submodular Function Minimization under Covering Constraints
inferredcites →https://doi.org/10.1137/0211045openalex-snapshot
Approximation Algorithms for the Set Covering and Vertex Cover Problems
inferredcites →https://doi.org/10.1137/0404017openalex-snapshot
New Ressults on Server Problems
inferredcites →https://doi.org/10.1137/050625382openalex-snapshot
On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
inferredcites →https://doi.org/10.1137/0603059openalex-snapshot
On the Greedy Heuristic for Continuous Covering and Packing Problems
inferredcites →https://doi.org/10.1137/s0097539700381097openalex-snapshot
Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
inferredcites →https://doi.org/10.1137/s0097539796314240openalex-snapshot
Improved Approximation Guarantees for Packing and Covering Integer Programs
inferredcites →https://doi.org/10.1145/1041680.1041683openalex-snapshot
Local ratio
inferredcites →https://doi.org/10.1145/1109557.1109666openalex-snapshot
The price of being near-sighted
inferredcites →https://doi.org/10.1145/1374376.1374412openalex-snapshot
Randomized competitive algorithms for generalized caching
inferredcites →https://doi.org/10.1145/1582716.1582746openalex-snapshot
Distributed and parallel algorithms for weighted vertex cover and other covering problems
inferredcites →https://doi.org/10.1145/167088.167127openalex-snapshot
Linear programming without the matrix
inferredcites →https://doi.org/10.1145/1978782.1978784openalex-snapshot
How well can primal-dual and local-ratio algorithms perform?
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/261342.571216openalex-snapshot
Approximation Algorithms for NP-Hard Problems
inferredcites →https://doi.org/10.1145/2786.2793openalex-snapshot
Amortized efficiency of list update and paging rules
inferredcites →https://doi.org/10.1145/288079.1041951openalex-snapshot
Book review: Approximation Algorithms for NP-hard Problems. Edited by Dorit S. Hochbaum (PWS, 1997)
inferredcites →https://doi.org/10.1145/301250.301416openalex-snapshot
Connection caching
inferredcites →https://doi.org/10.1145/341800.341808openalex-snapshot
Connection caching under various models of communication
inferredcites →https://doi.org/10.1147/rd.386.0683openalex-snapshot
Memory versus randomization in on-line algorithms
inferredcites →https://doi.org/10.1287/moor.1080.0363openalex-snapshot
Online Primal-Dual Algorithms for Covering and Packing
inferredcites →https://doi.org/10.1287/moor.4.3.233openalex-snapshot
A Greedy Heuristic for the Set-Covering Problem
inferredcites →https://doi.org/10.1287/moor.7.4.515openalex-snapshot
Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
inferredcites →https://doi.org/10.4007/annals.2005.162.439openalex-snapshot
On the hardness of approximating vertex cover
inferredcites →https://doi.org/10.5555/1070432.1070567openalex-snapshot
Network design for information networks
inferredcites →https://doi.org/10.5555/127787.127832openalex-snapshot
On-line caching as cache size varies
inferredcites →https://doi.org/10.5555/365411.365535openalex-snapshot
New approaches to covering and packing problems

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.2139/ssrn.2381949openalex-extracted
Approximation Algorithms for Multi-Dimensional Vector Assignment Problems
inferred← citeshttps://doi.org/10.1007/978-1-4614-6624-6_105-1openalex-snapshot
Efficient Relaxation and Rounding Techniques for Submodular Optimization
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_267openalex-snapshot
Online Paging and Caching
inferred← citeshttps://doi.org/10.1007/978-3-030-04618-7_6openalex-snapshot
A Bicriteria Approximation Algorithm for Minimum Submodular Cost Partial Multi-Cover Problem
inferred← citeshttps://doi.org/10.1007/978-3-030-14094-6_3openalex-snapshot
On the Approximability and Hardness of the Minimum Connected Dominating Set with Routing Cost Constraint
inferred← citeshttps://doi.org/10.1007/978-3-030-79987-8_36openalex-snapshot
New Approximations and Hardness Results for Submodular Partitioning Problems
inferred← citeshttps://doi.org/10.1007/978-3-030-92702-8_15openalex-snapshot
Precedence-Constrained Covering Problems with Multiplicity Constraints
inferred← citeshttps://doi.org/10.1007/978-3-031-15714-1_6openalex-snapshot
On Improved Interval Cover Mechanisms for Crowdsourcing Markets
inferred← citeshttps://doi.org/10.1007/978-3-319-18263-6_22openalex-snapshot
Primal-Dual Algorithms for Precedence Constrained Covering Problems
inferred← citeshttps://doi.org/10.1007/978-3-319-89441-6_8openalex-snapshot
Submodular Function Minimization with Submodular Set Covering Constraints and Precedence Constraints
inferred← citeshttps://doi.org/10.1007/978-3-642-04128-0_8openalex-snapshot
Approximability of Sparse Integer Programs
inferred← citeshttps://doi.org/10.1007/978-3-642-04355-0_23openalex-snapshot
Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality
inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_267-2openalex-snapshot
Online Paging and Caching
inferred← citeshttps://doi.org/10.1007/978-3-642-28209-6_8openalex-snapshot
Evader Interdiction and Collateral Damage
inferred← citeshttps://doi.org/10.1007/978-3-642-31594-7_37openalex-snapshot
Approximating Sparse Covering Integer Programs Online
inferred← citeshttps://doi.org/10.1007/978-3-642-35311-6_14openalex-snapshot
LP-Based Covering Games with Low Price of Anarchy
inferred← citeshttps://doi.org/10.1007/s00446-011-0127-7openalex-snapshot
Distributed algorithms for covering, packing and maximum weighted matching
inferred← citeshttps://doi.org/10.1007/s00453-010-9431-zopenalex-snapshot
Approximability of Sparse Integer Programs
inferred← citeshttps://doi.org/10.1007/s00453-013-9793-0openalex-snapshot
Online File Caching with Rejection Penalties
inferred← citeshttps://doi.org/10.1007/s00453-016-0174-3openalex-snapshot
Primal–Dual Algorithms for Precedence Constrained Covering Problems
inferred← citeshttps://doi.org/10.1007/s00453-017-0363-8openalex-snapshot
A Note on Submodular Function Minimization with Covering Type Linear Constraints
inferred← citeshttps://doi.org/10.1007/s00453-024-01270-zopenalex-snapshot
Online Paging with Heterogeneous Cache Slots
inferred← citeshttps://doi.org/10.1007/s10479-013-1372-xopenalex-snapshot
Evader interdiction: algorithms, complexity and collateral damage
inferred← citeshttps://doi.org/10.1007/s10878-020-00688-9openalex-snapshot
Approximation algorithm for the multicovering problem
inferred← citeshttps://doi.org/10.1007/s10878-023-01026-5openalex-snapshot
Algorithms for maximizing monotone submodular function minus modular function under noise
inferred← citeshttps://doi.org/10.1007/s10878-023-01027-4openalex-snapshot
Precedence-constrained covering problems with multiplicity constraints
inferred← citeshttps://doi.org/10.1016/j.adhoc.2018.10.012openalex-snapshot
Flexible SDN control in tactical ad hoc networks
inferred← citeshttps://doi.org/10.1016/j.dam.2017.08.024openalex-snapshot
An approximation algorithm for the partial covering 0–1 integer program
inferred← citeshttps://doi.org/10.1016/j.dam.2019.05.013openalex-snapshot
Group parking permit problems
inferred← citeshttps://doi.org/10.1016/j.disopt.2014.08.005openalex-snapshot
Multi-dimensional vector assignment problems
inferred← citeshttps://doi.org/10.1016/j.tcs.2019.03.004openalex-snapshot
A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
inferred← citeshttps://doi.org/10.1016/j.tcs.2019.06.019openalex-snapshot
On the approximability and hardness of the minimum connected dominating set with routing cost constraint
inferred← citeshttps://doi.org/10.1016/j.tcs.2025.115654openalex-snapshot
On generalizations of partial scenario set cover
inferred← citeshttps://doi.org/10.1016/j.tcs.2026.115849openalex-snapshot
A hybrid algorithm based on a multiple randomized rounding for set multicover problem: Approximation guarantees and experiments
inferred← citeshttps://doi.org/10.1109/access.2020.3019537openalex-snapshot
Optimal Data Collection for Mobile Crowdsensing Over Integrated Cellular and Opportunistic Networks
inferred← citeshttps://doi.org/10.1109/focs.2009.31openalex-snapshot
Submodular Function Minimization under Covering Constraints
inferred← citeshttps://doi.org/10.1109/icnp.2016.7784408openalex-snapshot
Deadline-sensitive User Recruitment for mobile crowdsensing with probabilistic collaboration
inferred← citeshttps://doi.org/10.1109/infocom.2015.7218612openalex-snapshot
User recruitment for mobile crowdsensing over opportunistic networks
inferred← citeshttps://doi.org/10.1142/s0217595923400122openalex-snapshot
Minimization Problems with Non-Submodular Cover Constraint
inferred← citeshttps://doi.org/10.1145/1582716.1582746openalex-snapshot
Distributed and parallel algorithms for weighted vertex cover and other covering problems
inferred← citeshttps://doi.org/10.1145/1989284.1989304openalex-snapshot
On the complexity of privacy-preserving complex event processing
inferred← citeshttps://doi.org/10.1145/2983323.2983817openalex-snapshot
Multiple Infection Sources Identification with Provable Guarantees
inferred← citeshttps://doi.org/10.15807/jorsj.60.15openalex-snapshot
A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH
inferred← citeshttps://doi.org/10.22028/d291-26583openalex-snapshot
Scalable optimization algorithms for recommender systems
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2018.23openalex-snapshot
Multi-Agent Submodular Optimization
inferred← citeshttps://doi.org/10.48550/arxiv.1010.1945openalex-snapshot
Submodular problems - approximations and algorithms
inferred← citeshttps://doi.org/10.48550/arxiv.1203.0050openalex-snapshot
LP-based Covering Games with Low Price of Anarchy
inferred← citeshttps://doi.org/10.48550/arxiv.1208.2724openalex-snapshot
Caching with rental cost and zapping
inferred← citeshttps://doi.org/10.48550/arxiv.1402.0240openalex-snapshot
Graph Cuts with Interacting Edge Costs - Examples, Approximations, and Algorithms
inferred← citeshttps://doi.org/10.48550/arxiv.1608.06492openalex-snapshot
Multiple Infection Sources Identification with Provable Guarantees
inferred← citeshttps://doi.org/10.48550/arxiv.1711.10680openalex-snapshot
On the Approximability and Hardness of the Minimum Connected Dominating Set with Routing Cost Constraint
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.