Perturbation Resilience

Konstantin Makarychev; Yury Makarychev

doi:10.1017/9781108637435.008

Perturbation Resilience

Konstantin Makarychev, Yury Makarychev

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Chapter

3 Scopus citations

Abstract

This chapter introduces perturbation resilience (also known as Bilu-Linial stability). Loosely speaking, an instance is perturbation resilient if the optimal solution remains the same when we perturb the instance.We present algorithmic and hardness results for perturbation-resilient instances. In particular, we describe certified algorithms that attempt to bridge the gap between the worst-case and structured instances: on one hand, they always find an approximate solution; on the other hand, they exactly solve perturbation-resilient instances.

Original language	English (US)
Title of host publication	Beyond the Worst-Case Analysis of Algorithms
Publisher	Cambridge University Press
Pages	95-119
Number of pages	25
ISBN (Electronic)	9781108637435
ISBN (Print)	9781108494311
DOIs	https://doi.org/10.1017/9781108637435.008
State	Published - Jan 1 2021

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1017/9781108637435.008

Cite this

@inbook{ddba886eab3d492e9f78e8dd4a1aeb2e,

title = "Perturbation Resilience",

abstract = "This chapter introduces perturbation resilience (also known as Bilu-Linial stability). Loosely speaking, an instance is perturbation resilient if the optimal solution remains the same when we perturb the instance.We present algorithmic and hardness results for perturbation-resilient instances. In particular, we describe certified algorithms that attempt to bridge the gap between the worst-case and structured instances: on one hand, they always find an approximate solution; on the other hand, they exactly solve perturbation-resilient instances.",

author = "Konstantin Makarychev and Yury Makarychev",

note = "Publisher Copyright: {\textcopyright} Cambridge University Press 2021.",

year = "2021",

month = jan,

day = "1",

doi = "10.1017/9781108637435.008",

language = "English (US)",

isbn = "9781108494311",

pages = "95--119",

booktitle = "Beyond the Worst-Case Analysis of Algorithms",

publisher = "Cambridge University Press",

}

TY - CHAP

T1 - Perturbation Resilience

AU - Makarychev, Konstantin

AU - Makarychev, Yury

PY - 2021/1/1

Y1 - 2021/1/1

N2 - This chapter introduces perturbation resilience (also known as Bilu-Linial stability). Loosely speaking, an instance is perturbation resilient if the optimal solution remains the same when we perturb the instance.We present algorithmic and hardness results for perturbation-resilient instances. In particular, we describe certified algorithms that attempt to bridge the gap between the worst-case and structured instances: on one hand, they always find an approximate solution; on the other hand, they exactly solve perturbation-resilient instances.

AB - This chapter introduces perturbation resilience (also known as Bilu-Linial stability). Loosely speaking, an instance is perturbation resilient if the optimal solution remains the same when we perturb the instance.We present algorithmic and hardness results for perturbation-resilient instances. In particular, we describe certified algorithms that attempt to bridge the gap between the worst-case and structured instances: on one hand, they always find an approximate solution; on the other hand, they exactly solve perturbation-resilient instances.

UR - http://www.scopus.com/inward/record.url?scp=85134642749&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85134642749&partnerID=8YFLogxK

U2 - 10.1017/9781108637435.008

DO - 10.1017/9781108637435.008

M3 - Chapter

AN - SCOPUS:85134642749

SN - 9781108494311

SP - 95

EP - 119

BT - Beyond the Worst-Case Analysis of Algorithms

PB - Cambridge University Press

ER -

Perturbation Resilience

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this