Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs

No abstract is available for this paper.

• Publication year

  1999

• Venue

  SIAM journal on computing (Print)

• Publication date

  1999-02-15

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/S0097539793260763
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• On the hardness of approximating minimization problems

  1994cited by this paper
• A parallel approximation algorithm for positive linear programming

  1993cited by this paper
• Fast approximation algorithms for fractional packing and covering problems

  1991cited by this paper
• Introduction to parallel algorithms and architectures

  1991cited by this paper
• Efficient NC algorithms for set cover with applications to learning and geometry

  1989influential reference
• Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs

  1988cited by this paper
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

  1982influential reference
• A Greedy Heuristic for the Set-Covering Problem

  1979cited by this paper
• On the ratio of optimal integral and fractional covers

  1975cited by this paper
• Approximation algorithms for combinatorial problems

  1973cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• Reducibility among combinatorial problems" in complexity of computer computations

  1972cited by this paper

• Attaining Equilibria Using Control Sets

  2026cites this paper
• A Hybrid Algorithm Based on a Multiple Randomized Rounding for Set Multicover Problem: Approximation Guarantees and Experiments

  2026cites this paper
• A parallel algorithm for minimum weight set cover with small neighborhood property

  2025cites this paper
• When far is better: The Chamberlin-Courant approach to obnoxious committee selection

  2024cites this paper
• Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling

  2024cites this paper
• Scheduling Splittable Jobs on Configurable Machines

  2023influential citation
• A parallel algorithm for minimum weight set cover with small neighborhood property

  2022cites this paper
• Set Selection under Explorable Stochastic Uncertainty via Covering Techniques

  2022cites this paper
• Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response

  2022cites this paper
• Optimizing strategies for post-disaster reconstruction of school systems

  2021cites this paper
• F-PKI: Enabling Innovation and Trust Flexibility in the HTTPS Public-Key Infrastructure

  2021cites this paper
• A Parallel Algorithm for Minimum Cost Submodular Cover

  2021cites this paper
• A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times

  2021cites this paper
• Relay Node Placement in Wireless Sensor Networks: From Theory to Practice

  2021cites this paper
• Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem

  2021cites this paper
• Repeated randomized algorithm for the Multicovering Problem

  2021cites this paper
• Approximation of set multi-cover via hypergraph matching

  2020cites this paper
• A Primal-Dual Randomized Algorithm for the Online Weighted Set Multi-cover Problem

  2020cites this paper
• Distributed Network Design

  2020cites this paper
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem

  2020cites this paper
• Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings

  2020cites this paper
• PASA: Identifying More Credible Structural Variants of Hedou12

  2020cites this paper
• Tight approximation bounds for maximum multi-coverage

  2019cites this paper
• Relay Node Placement in Wireless Sensor Networks With Respect to Delay and Reliability Requirements

  2019cites this paper
• Scheduling parallel identical machines to minimize makespan: A parallel approximation algorithm

  2019cites this paper
• A Bicriteria Approximation Algorithm for Minimum Submodular Cost Partial Multi-Cover Problem

  2018cites this paper
• Set Cover Problems with Small Neighborhood Covers

  2018influential citation
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation

  2018cites this paper
• The adaptive complexity of maximizing a submodular function

  2018cites this paper
• Algorithme d’approximation pour un problème d’affectation d’une commande multiproduit multifournisseur

  2018cites this paper
• Dynamic cost-effective social network data placement and replication in the cloud

  2018cites this paper
• Robust multicovers with budgeted uncertainty

  2018cites this paper
• Approximation algorithm for partial set multicover versus full set multicover

  2018cites this paper
• Approximation algorithm for the partial set multi-cover problem

  2018cites this paper
• Non-monotone Submodular Maximization in Exponentially Fewer Iterations

  2018cites this paper
• An Approximation Framework for Bounded Facility Location Problems

  2018cites this paper
• Greedy and Local Ratio Algorithms in the MapReduce Model

  2018cites this paper
• Approximation Guarantees for Adaptive Sampling

  2018cites this paper
• Novel geometric approach for virtual coiling

  2018cites this paper
• Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable

  2018cites this paper
• A pr 2 01 8 On Derandomizing Local Distributed Algorithms

  2018cites this paper
• Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs

  2018influential citation
• Distributed Spanner Approximation

  2018influential citation
• On Derandomizing Local Distributed Algorithms

  2017cites this paper
• A Parallel Approximation Algorithm for Scheduling Parallel Identical Machines

  2017cites this paper
• Model and Algorithm: K-extended Constrain Independent Relay Node Placement Solution with Base Stations in Two-tiered Wireless Sensor Network

  2017cites this paper
• Randomized Approximation Algorithm for Minimum Submodular Cost Partial Multi-Cover Problem

  2017cites this paper
• Randomized Bicriteria Approximation Algorithm for Minimum Submodular Cost Partial Multi-Cover Problem

  2017cites this paper
• Mixed Integer Programming with Convex/Concave Constraints: Fixed-Parameter Tractability and Applications to Multicovering and Voting

  2017cites this paper
• Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing

  2017cites this paper
• Multiple Transversals Greedily

  2016cites this paper
• Approximating set multi-covers

  2016cites this paper
• b-Disjunctive Total Domination in Graphs: Algorithm and Hardness Results

  2016cites this paper
• A New 3/2-Approximation Algorithm for the b-Edge Cover Problem

  2016cites this paper
• Handbook of Computational Social Choice

  2016cites this paper
• Algorithmic aspects of manipulation and anonymization in social choice and social networks

  2016cites this paper
• Design frequency synthesizer chip for wearable RFID and biomedical applications

  2016cites this paper
• Minimum Cost Spatial-Temporal Task Allocation in Mobile Crowdsensing

  2016cites this paper
• Inapproximability of H-Transversal/Packing

  2015cites this paper
• Algorithmic aspects of b-disjunctive domination in graphs

  2015cites this paper
• Large-Scale Election Campaigns: Combinatorial Shift Bribery

  2015cites this paper
• A suite of greedy methods for set cover computation

  2015cites this paper
• Submodular Optimization and Machine Learning: Theoretical Results, Unifying and Scalable Algorithms, and Applications

  2015cites this paper
• K-Extended Constrain Independent Relay Node Placement with Base Stations in Two-Tiered Wireless Sensor Network

  2014cites this paper
• Monotone Closure of Relaxed Constraints in Submodular Optimization: Connections Between Minimization and Maximization

  2014cites this paper
• Declarative cartography: In-database map generalization of geospatial datasets

  2014influential citation
• A novel approach for ECG data compression in healthcare monitoring system

  2014cites this paper
• Wireless Multimedia Sensor Networks: Correlation-Based Communications

  2013cites this paper
• Efficient methods of feature selection based on combinatorial optimization motivated by the analysis of large biological datasets

  2013cites this paper
• Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers

  2013cites this paper
• A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks

  2013cites this paper
• A New Self-stabilizing Algorithm for Maximal-packing

  2012cites this paper
• A self-stabilizing algorithm to maximal 2-packing with improved complexity

  2012cites this paper
• Chapter 11 Mining Chains of Relations

  2012cites this paper
• Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks: Computational Complexity and Efficient Approximations

  2012influential citation
• Parallel and I/O efficient set covering algorithms

  2012influential citation
• Correlation-based communication in wireless multimedia sensor networks

  2012cites this paper
• An Updated Self-stabilizing Algorithm to Maximal 2-packing and A Linear Variation under Synchronous Daemon

  2011cites this paper
• On positive influence dominating sets in social networks

  2011cites this paper
• Linear-work greedy parallel approximate set cover and variants

  2011cites this paper
• A Distributed Approximation Algorithm for the Metric Uncapacitated Facility Location Problem in the Congest Model

  2011cites this paper
• A Spatial Correlation-Based Image Compression Framework for Wireless Multimedia Sensor Networks

  2011cites this paper
• DARP: Distance-aware relay placement in WiMAX mesh networks

  2011cites this paper
• Geometric Hitting Sets and Their Variants

  2011cites this paper
• Distributed optimization algorithms for multihop wireless networks

  2010cites this paper
• Collaborative Data Compression Using Clustered Source Coding for Wireless Multimedia Sensor Networks

  2010cites this paper
• Title Dynamic programming based algorithms for set multicover andmultiset multicover problems

  2010cites this paper
• A New Self-stabilizing Algorithm for Maximal 2-packing

  2010cites this paper
• Hybrid approximation for minimum-cost target coverage in wireless sensor networks

  2010cites this paper
• Dynamic programming based algorithms for set multicover and multiset multicover problems

  2010cites this paper
• SUPPORTING MULTI-MISSIONS IN WIRELESS SENSOR

  2010cites this paper
• Parallel approximation algorithms for facility-location problems

  2010influential citation
• An adaptive updating protocol for reducing moving object database workload

  2010cites this paper
• Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks: Efficient Approximations

  2010cites this paper
• Local Computation

  2010cites this paper
• Robust Localization Using Identifying Codes

  2009cites this paper
• Efficient Sensor Placement for Surveillance Problems

  2009cites this paper
• Scheduling wireless links with SINR constraints

  2009cites this paper
• A Self-stabilizing Algorithm for Maximum Popular Matching of Strictly Ordered Preference Lists

  2009cites this paper
• Approximation Algorithms for Covering Problems

  2009cites this paper