NDLI: Randomization Helps Computing a Minimum Spanning Tree under Uncertainty

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Skutella, Martin Meiner, Julie Megow, Nicole
Copyright Year	2017
Abstract	Given a graph with uncertainty intervals on the edges, we want to identify a minimum spanning tree by querying some edges for their exact edge weights which lie in the given uncertainty intervals. Our objective is to minimize the number of edge queries. It is known that there is a deterministic algorithm with best possible competitive ratio 2 [T. Erlebach, et al., in Proceedings of STACS, Schloss Dagstuhl, Dagstuhl, Germany, 2008, pp. 277--288]. Our main result is a randomized algorithm with expected competitive ratio $1+1/\sqrt{2}\approx 1.707$, solving the long-standing open problem of whether an expected competitive ratio strictly less than 2 can be achieved [T. Erlebach and M. Hoffmann, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 116 (2015)]. We also present novel results for various extensions, including arbitrary matroids and more general querying models.
Sponsorship	Deutsche Forschungsgemeinschaft. Einstein Stiftung Berlin
Starting Page	1217
Ending Page	1240
Page Count	24
File Format	PDF
ISSN	00975397
DOI	10.1137/16M1088375
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	4
Volume Number	46
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2017-07-18
Access Restriction	Subscribed
Subject Keyword	Online algorithms minimum spanning tree randomized algorithms Randomized algorithms Graph theory online algorithms competitive analysis
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

Approximating the Minimum Spanning Tree Weight in Sublinear Time

A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest

Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds

Randomized Competitive Algorithms for Generalized Caching

Online Scheduling of EqualLength Jobs: Randomization and Restarts Help

Maintaining Minimum Spanning Forests in Dynamic Graphs

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time

Quantum Query Complexity of Some Graph Problems

Study Morphology of Minimum Spanning Tree Problem and Generalized Algorithms

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty

Similar Documents

Approximating the Minimum Spanning Tree Weight in Sublinear Time

A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest

Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds

Randomized Competitive Algorithms for Generalized Caching

Online Scheduling of EqualLength Jobs: Randomization and Restarts Help

Maintaining Minimum Spanning Forests in Dynamic Graphs

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time

Quantum Query Complexity of Some Graph Problems

Study Morphology of Minimum Spanning Tree Problem and Generalized Algorithms

Randomization Helps Computing a Minimum Spanning Tree under Uncertainty