PASS approximation: a framework for analyzing and designing heuristics
From MaRDI portal
Publication:1950388
DOI10.1007/s00453-012-9646-2zbMath1298.90133WikidataQ101126194 ScholiaQ101126194MaRDI QIDQ1950388
Nicole Immorlica, Uriel Feige, Hamid Nazerzadeh, Vahab S. Mirrokni
Publication date: 13 May 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9646-2
90C59: Approximation methods and heuristics in mathematical programming
Related Items
Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions, Gross substitutability: an algorithmic survey, Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs, Recoverable Values for Independent Sets
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Geometric algorithms and combinatorial optimization
- An 0. 828-approximation algorithm for the uncapacitated facility location problem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Heuristics for semirandom graph problems
- Outward rotations
- On maximizing welfare when utility functions are subadditive
- A threshold of ln n for approximating set cover
- Smoothed analysis of algorithms
- PASS Approximation
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- Coloring Random and Semi-Random k-Colorable Graphs
- Segmentation problems