Priority algorithms for graph optimization problems
type: Item
instance of: scholarly article
title: Priority algorithms for graph optimization problems
zbMATH Open document ID: 1181.90269
author: Allan Borodin
author: Kim S. Larsen
author: Nazanin Mirmohammadi
author: Joan Boyar
published in: Theoretical Computer Science
publication date: 2009-12-01T00:00:00Z
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 5641363
zbMATH Keywords: approximation algorithms
zbMATH Keywords: greedy algorithms
zbMATH Keywords: vertex cover
zbMATH Keywords: independent set
zbMATH Keywords: vertex coloring
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.09.033
OpenAlex ID: W2136026170
cites work: Toward a model for backtracking and dynamic programming
cites work: Approximation and Online Algorithms
cites work: Q4411275
cites work: Q3002764
cites work: A list heuristic for vertex cover
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: On approximation properties of the Independent set problem for degree 3 graphs
cites work: Approximating maximum independent sets by excluding subgraphs
cites work: (Incremental) priority algorithms
cites work: Models of greedy algorithms for graph problems
cites work: The importance of being biased
cites work: Matroids and the greedy algorithm
cites work: Zero knowledge and the chromatic number
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Q2766829
cites work: A still better performance guarantee for approximate graph coloring
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: Approximation algorithms for combinatorial problems
cites work: On the hardness of approximating the chromatic number
cites work: On the power of unique 2-prover 1-round games
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Truth revelation in approximately efficient combinatorial auctions
cites work: Optimization, approximation, and complexity classes
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
cites work: Priority algorithms for the subset-sum problem
DOI: 10.1016/J.TCS.2009.09.033
description: scientific article; zbMATH DE number 5641363