NDLI: Smoothed Analysis of the Successive Shortest Path Algorithm

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Cornelissen, Kamiel Röglin, Heiko Manthey, Bodo Rösner, Clemens Brunsch, Tobias
Copyright Year	2015
Abstract	The minimum-cost flow problem is a classic problem in combinatorial optimization with various applications. Several pseudopolynomial, polynomial, and strongly polynomial algorithms have been developed in the past decades, and it seems that both the problem and the algorithms are well understood. However, some of the algorithms' running times observed in empirical studies contrast the running times obtained by worst-case analysis not only in the order of magnitude but also in the ranking when compared to each other. For example, the successive shortest path (SSP) algorithm, which has an exponential worst-case running time, seems to outperform the strongly polynomial minimum-mean cycle canceling algorithm. To explain this discrepancy, we study the SSP algorithm in the framework of smoothed analysis and establish a bound of $O(mn\phi)$ for the number of iterations, which implies a smoothed running time of $O(mn\phi (m + n\log n))$, where $n$ and $m$ denote the number of nodes and edges, respectively, and $\phi$ is a measure for the amount of random noise. This shows that worst-case instances for the SSP algorithm are not robust and unlikely to be encountered in practice. Furthermore, we prove a smoothed lower bound of $\Omega(m \cdot \min \{ n, \phi \} \cdot \phi)$ for the number of iterations of the SSP algorithm, showing that the upper bound cannot be improved for $\phi = \Omega(n)$.
Starting Page	1798
Ending Page	1819
Page Count	22
File Format	PDF
ISSN	00975397
DOI	10.1137/140989893
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	6
Volume Number	44
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2015-12-10
Access Restriction	Subscribed
Subject Keyword	Analysis of algorithms and problem complexity successive shortest path algorithm minimum-cost flows smoothed analysis Flows in graphs Graph algorithms
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

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

Smoothed analysis of the successive shortest path algorithm (2013).

On the k Shortest Simple Paths Problem in Weighted Directed Graphs

A near linear shortest path algorithm for weighted undirected graphs

An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications

An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$

A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs

Minimum Cost Paths in Periodic Graphs

Smoothed Analysis of the Successive Shortest Path Algorithm

Maintaining Minimum Spanning Forests in Dynamic Graphs

Smoothed Analysis of the Successive Shortest Path Algorithm

Similar Documents

Smoothed analysis of the successive shortest path algorithm (2013).

On the k Shortest Simple Paths Problem in Weighted Directed Graphs

A near linear shortest path algorithm for weighted undirected graphs

An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications

An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$

A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs

Minimum Cost Paths in Periodic Graphs

Smoothed Analysis of the Successive Shortest Path Algorithm

Maintaining Minimum Spanning Forests in Dynamic Graphs

Smoothed Analysis of the Successive Shortest Path Algorithm