Priority algorithms for graph optimization problems
From MaRDI portal
Publication:1041242
DOI10.1016/j.tcs.2009.09.033zbMath1181.90269MaRDI QIDQ1041242
Kim S. Larsen, Allan Borodin, Joan. Boyar, Nazanin Mirmohammadi
Publication date: 1 December 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.09.033
90C35: Programming involving graphs or networks
Related Items
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds, Greedy matching: guarantees and limitations, Limitations of incremental dynamic programming, On sum coloring and sum multi-coloring for restricted families of graphs, Erratum to: ``Greedy matching: guarantees and limitations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Toward a model for backtracking and dynamic programming
- Models of greedy algorithms for graph problems
- Priority algorithms for the subset-sum problem
- Efficient bounds for the stable set, vertex cover and set packing problems
- Optimization, approximation, and complexity classes
- Approximating maximum independent sets by excluding subgraphs
- A still better performance guarantee for approximate graph coloring
- Approximation algorithms for combinatorial problems
- Zero knowledge and the chromatic number
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- (Incremental) priority algorithms
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- A list heuristic for vertex cover
- Truth revelation in approximately efficient combinatorial auctions
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- The importance of being biased
- On the power of unique 2-prover 1-round games
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- On approximation properties of the Independent set problem for degree 3 graphs
- Matroids and the greedy algorithm
- Approximation and Online Algorithms
- Approximation and Online Algorithms
- On the hardness of approximating the chromatic number
