Set cover problems with small neighborhood covers
From MaRDI portal
Publication:2322696
DOI10.1007/s00224-017-9842-1zbMath1430.68432OpenAlexW2786115817MaRDI QIDQ2322696
Anamitra R. Choudhury, Yogish Sabharwal, Sambudha Roy, Venkatesan T. Chakaravarthy, Archita Agarwal
Publication date: 5 September 2019
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-017-9842-1
Analysis of algorithms (68W40) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Distributed algorithms for covering, packing and maximum weighted matching
- Low diameter graph decompositions
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers
- The Design of Approximation Algorithms
- Resource Allocation for Covering Time Varying Demands
- A threshold of ln n for approximating set cover
- Elimination graphs
- Improvements in throughout maximization for real-time scheduling
- On Column-Restricted and Priority Covering Integer Programs
- The price of being near-sighted
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
- A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Covers
- Approximation algorithms for partial covering problems
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Computing and Combinatorics
- A unified approach to approximating resource allocation and scheduling
- Parallel algorithms on circular-arc graphs
This page was built for publication: Set cover problems with small neighborhood covers
