Set cover problems with small neighborhood covers

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

zbMATH Keywords

primal-dual methodparallel algorithmsapproximation algorithmsdistributed algorithms

Mathematics Subject Classification ID

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