NDLI: Smoothed performance guarantees for local search

Content Provider	Springer Nature Link
Author	Rutten, Cyriel Röglin, Heiko Vredeveld, Tjark Brunsch, Tobias
Copyright Year	2013
Abstract	We study popular local search and greedy algorithms for standard machine scheduling problems. The performance guarantee of these algorithms is well understood, but the worst-case lower bounds seem somewhat contrived and it is questionable whether they arise in practical applications. To find out how robust these bounds are, we study the algorithms in the framework of smoothed analysis, in which instances are subject to some degree of random noise. While the lower bounds for all scheduling variants with restricted machines are rather robust, we find out that the bounds are fragile for unrestricted machines. In particular, we show that the smoothed performance guarantee of the jump and the lex-jump algorithm are (in contrast to the worst case) independent of the number of machines. They are $$\Theta (\phi )$$ and $$\Theta (\log \phi )$$ , respectively, where $$1/\phi $$ is a parameter measuring the magnitude of the perturbation. The latter immediately implies that also the smoothed price of anarchy is $$\Theta (\log \phi )$$ for routing games on parallel links. Additionally, we show that for unrestricted machines also the greedy list scheduling algorithm has an approximation guarantee of $$\Theta (\log \phi )$$ .
Ending Page	218
Page Count	34
Starting Page	185
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	1-2
Volume Number	146
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2013-05-09
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Analysis of algorithms and problem complexity Mathematical Methods in Physics Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) Calculus of Variations and Optimal Control; Optimization Mathematics of Computing Numerical Analysis Theoretical, Mathematical and Computational Physics Approximation algorithms Scheduling theory, deterministic Analysis of algorithms Combinatorics
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Strong LP formulations for scheduling splittable jobs on unrelated machines

Approximability of average completion time scheduling on unrelated machines

Machine scheduling with resource dependent processing times

Truthful mechanism design via correlated tree rounding

Scheduling and fixed-parameter tractability

A 3-approximation algorithm for the facility location problem with uniform capacities

Smoothed analysis of integer programming

Analysis of multi-stage open shop processing systems

An efficient polynomial time approximation scheme for load balancing on uniformly related machines

Smoothed performance guarantees for local search

Similar Documents

Strong LP formulations for scheduling splittable jobs on unrelated machines

Approximability of average completion time scheduling on unrelated machines

Machine scheduling with resource dependent processing times

Truthful mechanism design via correlated tree rounding

Scheduling and fixed-parameter tractability

A 3-approximation algorithm for the facility location problem with uniform capacities

Smoothed analysis of integer programming

Analysis of multi-stage open shop processing systems

An efficient polynomial time approximation scheme for load balancing on uniformly related machines

Smoothed performance guarantees for local search