PASS approximation: a framework for analyzing and designing heuristics

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

zbMATH Keywords

facility location; approximation algorithms; display advertising; sub-modular optimization

Mathematics Subject Classification ID

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

• 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