A unified approach to approximating partial covering problems
type: Item
instance of: scholarly article
title: A unified approach to approximating partial covering problems
zbMATH Open document ID: 1211.68511
author: Jochen Könemann
author: Ojas Parekh
author: Danny Segev
published in: Algorithmica
publication date: 2011-03-30T00:00:00Z
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5871670
zbMATH Keywords: partial cover
zbMATH Keywords: approximation algorithms
zbMATH Keywords: Lagrangian relaxation
MaRDI profile type: Publication
full work available at URL: s00453-009-9317-0
OpenAlex ID: W2175530190
cites work: Q5501312
cites work: Set Partitioning: A survey
cites work: Using homogeneous weights for approximating the partial cover problem
cites work: A linear-time approximation algorithm for the weighted vertex cover problem
cites work: Algorithms for facility location problems with outliers. (Extended abstract)
cites work: On the hardness of approximating Multicut and Sparsest-Cut
cites work: Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
cites work: Q5675543
cites work: Q4780785
cites work: A threshold of ln n for approximating set cover
cites work: On approximation of the submodular set cover problem
cites work: Approximation algorithms for partial covering problems
cites work: Saving an epsilon
cites work: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
cites work: Primal-dual approximation algorithms for integral flow and multicut in trees
cites work: Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
cites work: Approximating the k-multicut problem
cites work: The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
cites work: Q4400849
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
cites work: Approximation algorithms for combinatorial problems
cites work: On the power of unique 2-prover 1-round games
cites work: Partial multicuts in trees
cites work: On the ratio of optimal integral and fractional covers
cites work: Q4910703
cites work: A 1-matching blossom-type algorithm for edge covering problems
cites work: An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
cites work: Q4040221
cites work: Covering, Packing and Knapsack Problems
cites work: Path hitting in acyclic graphs
cites work: Constrained weighted matchings and edge coverings in graphs
cites work: A Tight Analysis of the Greedy Algorithm for Set Cover
DOI: 10.1007/S00453-009-9317-0
description: scientific article; zbMATH DE number 5871670