PASS approximation: a framework for analyzing and designing heuristics

DOI10.1007/s00453-012-9646-2zbMath1298.90133OpenAlexW2180209872WikidataQ101126194 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

zbMATH Keywords

facility locationapproximation algorithmsdisplay advertisingsub-modular optimization

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59)

Related Items (4)

Gross substitutability: an algorithmic survey ⋮ Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions ⋮ Recoverable Values for Independent Sets ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs

Uses Software

• Outward rotations

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

This page was built for publication: PASS approximation: a framework for analyzing and designing heuristics