Approximating covering integer programs with multiplicity constraints
type: Item
instance of: scholarly article
title: Approximating covering integer programs with multiplicity constraints
zbMATH Open document ID: 1030.90062
DOI: 10.1016/S0166-218X(02)00598-X
author: Stavros G. Kolliopoulos
published in: Discrete Applied Mathematics
publication date: 2003-09-09T00:00:00Z
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 1977911
zbMATH Keywords: Approximation algorithms
zbMATH Keywords: Covering integer programs
zbMATH Keywords: Integrality gap
zbMATH Keywords: Set multicover
MaRDI profile type: Publication
cites work: Approximating low-congestion routing and column-restricted packing problems
cites work: Approximation algorithms for disjoint paths and related routing and packing problems
cites work: Efficient probabilistically checkable proofs and applications to approximations
cites work: Rounding algorithms for covering problems
cites work: Q4952606
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
cites work: Q4228484
cites work: On the Greedy Heuristic for Continuous Covering and Packing Problems
cites work: Q3128880
cites work: Approximation algorithms for combinatorial problems
cites work: Q3840354
cites work: Approximation algorithms for single-source unsplittable flow
cites work: On the ratio of optimal integral and fractional covers
cites work: On the hardness of approximating minimization problems
cites work: Fast Approximation Algorithms for Fractional Packing and Covering Problems
cites work: Randomized rounding: A technique for provably good algorithms and algorithmic proofs
cites work: Q4527015
cites work: Q4875163
cites work: Improved Approximation Guarantees for Packing and Covering Integer Programs
cites work: A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
cites work: Q4886046
full work available at URL: s0166-218x(02)00598-x
OpenAlex ID: W2093259407
description: scientific article; zbMATH DE number 1977911