Differential approximation algorithms for some combinatorial optimization problems
type: Item
instance of: scholarly article
title: Differential approximation algorithms for some combinatorial optimization problems
zbMATH Open document ID: 0912.68061
DOI: 10.1016/S0304-3975(97)00099-6
author: Marc Demange
author: Pascal Grisoni
author: Vangelis Th. Paschos
published in: Theoretical Computer Science
publication date: 1999-01-12T00:00:00Z
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 1238688
zbMATH Keywords: NP-complete problem
zbMATH Keywords: polynomial time approximation algorithm
zbMATH Keywords: set covering
zbMATH Keywords: coloring
zbMATH Keywords: bin-packing
MaRDI profile type: Publication
cites work: Q4230322
cites work: Structure preserving reductions among convex optimization problems
cites work: New approximation algorithms for graph coloring
cites work: Q5782525
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Approximation results for the minimum graph coloring problem
cites work: On an approximation measure founded on the links between optimization and polynomial approximation theory
cites work: Bin packing can be solved within 1+epsilon in linear time
cites work: Q4198056
cites work: A still better performance guarantee for approximate graph coloring
cites work: Q4886045
cites work: Maximizing the number of unused colors in the vertex coloring problem
cites work: Approximation algorithms for combinatorial problems
cites work: Covering edges by cliques with regard to keyword conflicts and intersection graphs
cites work: Three short proofs in graph theory
cites work: On the ratio of optimal integral and fractional covers
cites work: On the hardness of approximating minimization problems
cites work: On Approximate Solutions for Combinatorial Optimization Problems
cites work: Approximation algorithms for indefinite quadratic programming
full work available at URL: s0304-3975(97)00099-6
OpenAlex ID: W2089061537
description: scientific article; zbMATH DE number 1238688