PASS approximation: a framework for analyzing and designing heuristics
The authors introduce a new framework for designing and analyzing algorithms. Their framework applies best to problems that are inapproximable according to the standard worst-case analysis. They circumvent such negative results by designing guarantees for classes of instances, parameterized according to properties of the optimal solution. Given their parameterized approximation, called parametrized by the signature of the solution (PASS) approximation, the authors design algorithms with optimal approximation ratios for problems with additive and submodular objective functions such as the capacitated maximum facility location problems. The authors consider two types of algorithms for these problems. For Greedy algorithms, their framework provides a justification for preferring a certain natural greedy rule over some alternative Greedy rules that have been used in similar contexts. For LP-based algorithms, they show that the natural LP relaxation for these problems is not optimal in our framework. We design a new LP relaxation and show that this LP relaxation coupled with a new randomized rounding technique is optimal in our framework.
- A threshold of ln n for approximating set cover
- An 0. 828-approximation algorithm for the uncapacitated facility location problem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Coloring Random and Semi-Random k-Colorable Graphs
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- Geometric algorithms and combinatorial optimization
- Heuristics for semirandom graph problems
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- scientific article; zbMATH DE number 5485445 (Why is no real title available?)
- scientific article; zbMATH DE number 1947050 (Why is no real title available?)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- On maximizing welfare when utility functions are subadditive
- Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
- PASS Approximation
- Segmentation problems
- Smoothed analysis of algorithms
- Gross substitutability: an algorithmic survey
- Fully polynomial time (,)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
- PASS Approximation
- Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions
- Revisiting non-monotone regularized submodular maximization: bi-criteria and pass approximations
- A streaming algorithm for non-monotone regularized submodular maximization
This page was built for publication: PASS approximation: a framework for analyzing and designing heuristics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1950388)
