An analysis of the greedy algorithm for the submodular set covering problem
From MaRDI portal
Publication:1838034
DOI10.1007/BF02579435zbMath0508.68021OpenAlexW2029828838MaRDI QIDQ1838034
Publication date: 1982
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579435
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35) Algorithms in computer science (68W99)
Related Items (98)
Approximating Bounded Degree Deletion via Matroid Matching ⋮ Maximizing the smallest eigenvalue of a symmetric matrix: a submodular optimization approach ⋮ Capacitated Arc Stabbing ⋮ Greedy approximations for minimum submodular cover with submodular cost ⋮ Structural identifiability in low-rank matrix factorization ⋮ Adaptive Test Allocation for Outbreak Detection and Tracking in Social Contact Networks ⋮ Inadequacy of linear methods for minimal sensor placement and feature selection in nonlinear systems: a new approach using secants ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ Decision tree classification with bounded number of errors ⋮ On some network design problems with degree constraints ⋮ Unnamed Item ⋮ AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS ⋮ Approximating activation edge-cover and facility location problems ⋮ Submodular learning and covering with response-dependent costs ⋮ Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem ⋮ A general greedy approximation algorithm for finding minimum positive influence dominating sets in social networks ⋮ Structured Robust Submodular Maximization: Offline and Online Algorithms ⋮ New dominating sets in social networks ⋮ Approximation algorithm for the 2-stage stochastic matroid base problem ⋮ Domination parameters with number 2: interrelations and algorithmic consequences ⋮ Approximating power node-deletion problems ⋮ Capacitated covering problems in geometric spaces ⋮ Toward a sparsity theory on weighted lattices ⋮ Uncertainty in Study of Social Networks: Robust Optimization and Machine Learning ⋮ On positive influence dominating sets in social networks ⋮ A unified greedy approximation for several dominating set problems ⋮ Improved bounds for metric capacitated covering problems ⋮ A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities ⋮ Unnamed Item ⋮ Pervasive domination ⋮ An exact solution approach for the mobile multi‐agent sensing problem ⋮ Approximability of sparse integer programs ⋮ Few cuts meet many point sets ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ Combination algorithms for Steiner tree variants ⋮ A logarithmic approximation for polymatroid congestion games ⋮ Adaptive Submodular Ranking and Routing ⋮ Improved approximation algorithms for low-density instances of the minimum entropy set cover problem ⋮ Input matrix construction and approximation using a graphic approach ⋮ Augmenting edge-connectivity between vertex subsets ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ On approximation of the submodular set cover problem ⋮ Bounding the payment of approximate truthful mechanisms ⋮ Tight approximation algorithm for connectivity augmentation problems ⋮ A model for minimizing active processor time ⋮ Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization ⋮ \(O(f)\) bi-criteria approximation for capacitated covering with hard capacities ⋮ Admission control with advance reservations in simple networks ⋮ Submodular Function Minimization under a Submodular Set Covering Constraint ⋮ Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm ⋮ Randomized approximation of bounded multicovering problems ⋮ Parallel approximation for partial set cover ⋮ Minimum non-submodular cover problem with applications ⋮ On positive-influence target-domination ⋮ Approximating source location and star survivable network problems ⋮ Network construction with subgraph connectivity constraints ⋮ Minimum cost source location problems with flow requirements ⋮ On minimum submodular cover with submodular cost ⋮ Parametric monotone function maximization with matroid constraints ⋮ Approximability and inapproximability of the minimum certificate dispersal problem ⋮ Unnamed Item ⋮ Disjoint bases in a polymatroid ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Mixed fault tolerance in server assignment: combining reinforcement and backup ⋮ A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem ⋮ Sparsity in max-plus algebra and systems ⋮ Approximation algorithms for minimum weight partial connected set cover problem ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Capacitated discrete unit disk cover ⋮ Network-Design with Degree Constraints ⋮ Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs ⋮ Sparse approximate solutions to max-plus equations ⋮ Independent sets in bounded-degree hypergraphs ⋮ Approximations for subset interconnection designs ⋮ Approximating Source Location and Star Survivable Network Problems ⋮ Set function optimization ⋮ Approximation algorithm for vertex cover with multiple covering constraints ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ An ex-post bound on the greedy heuristic for the uncapacitated facility location problem ⋮ Minimizing ratio of monotone non-submodular functions ⋮ Nearly tight approximation algorithm for (connected) Roman dominating set ⋮ A note on submodular set cover on matroids ⋮ Approximating the weight of shallow Steiner trees ⋮ Capacitated Covering Problems in Geometric Spaces ⋮ The polymatroid Steiner problems ⋮ Generalized submodular cover problems and applications ⋮ A Tight Bound for Stochastic Submodular Cover ⋮ Steiner trees in uniformly quasi-bipartite graphs. ⋮ Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem ⋮ An improved approximation algorithm for vertex cover with hard capacities ⋮ On capacitated covering with unit balls ⋮ On approximability of the independent/connected edge dominating set problems ⋮ Local majorities, coalitions and monopolies in graphs: A review ⋮ On fixed cost \(k\)-flow problems ⋮ Degree-constrained graph orientation: maximum satisfaction and minimum violation ⋮ Tight bounds on subexponential time approximation of set cover and related problems
Cites Work
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Note on Independence Functions
- A Greedy Heuristic for the Set-Covering Problem
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- A Canonical Representation of Simple Plant Location Problems and Its Applications
- An analysis of approximations for maximizing submodular set functions—I
- On the Greedy Heuristic for Continuous Covering and Packing Problems
This page was built for publication: An analysis of the greedy algorithm for the submodular set covering problem
