PASS approximation: a framework for analyzing and designing heuristics
type: Item
instance of: scholarly article
title: PASS approximation: a framework for analyzing and designing heuristics
zbMATH Open document ID: 1298.90133
author: Nicole Immorlica
author: Hamid Nazerzadeh
author: Vahab S. Mirrokni
author: Uriel Feige
published in: Algorithmica
publication date: 2013-05-13T00:00:00Z
review text: 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.
reviewed by: Paulo Mbunga
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6162390
zbMATH Keywords: approximation algorithms
zbMATH Keywords: facility location
zbMATH Keywords: sub-modular optimization
zbMATH Keywords: display advertising
describes a project that uses: Outward rotations
MaRDI profile type: Publication
full work available at URL: s00453-012-9646-2
OpenAlex ID: W2180209872
Wikidata QID: Q101126194
cites work: An 0. 828-approximation algorithm for the uncapacitated facility location problem
cites work: Coloring Random and Semi-Random k-Colorable Graphs
cites work: Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
cites work: A threshold of ln n for approximating set cover
cites work: On maximizing welfare when utility functions are subadditive
cites work: PASS Approximation
cites work: Heuristics for semirandom graph problems
cites work: Q4411280
cites work: Geometric algorithms and combinatorial optimization
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Q2941641
cites work: Segmentation problems
cites work: Q3549607
cites work: Smoothed analysis of algorithms
cites work: Q3002782
cites work: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
DOI: 10.1007/S00453-012-9646-2
description: scientific article; zbMATH DE number 6162390