NDLI: Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing

Please wait, while we are loading the content...

Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Bartal, Yair Leonardi, Stefano Fiat, Amos
Copyright Year	2006
Abstract	We present lower bounds on the competitive ratio of randomized algorithms for a wide class of on-line graph optimization problems, and we apply such results to on-line virtual circuit and optical routing problems. Lund and Yannakakis [The approximation of maximum subgraph problems, in Proceedings of the 20th International Colloquium on Automata, Languages and Programming, 1993, pp. 40-51] give inapproximability results for the problem of finding the largest vertex induced subgraph satisfying any nontrivial, hereditary property pi--e.g., independent set, planar, acyclic, bipartite. We consider the on-line version of this family of problems, where some graph G is fixed and some subgraph H of G is presented on-line, vertex by vertex. The on-line algorithm must choose a subset of the vertices of H, choosing or rejecting a vertex when it is presented, whose vertex induced subgraph satisfies property pi. Furthermore, we study the on-line version of graph coloring whose off-line version has also been shown to be inapproximable [C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, in Proceedings of the 25th ACM Symposium on Theory of Computing, 1993], on-line max edge-disjoint paths, and on-line path coloring problems. Irrespective of the time complexity, we show an Omega(nepsilon ) lower bound on the competitive ratio of randomized on-line algorithms for any of these problems. As a consequence, we obtain an Omega(nepsilon ) lower bound on the competitive ratio of randomized on-line algorithms for virtual circuit routing on general networks, in contrast to the known results for some specific networks. Similar lower bounds are obtained for on-line optical routing as well.
Starting Page	354
Ending Page	393
Page Count	40
File Format	PDF
ISSN	00975397
DOI	10.1137/S009753979833965X
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2
Volume Number	36
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-01-01
Access Restriction	Subscribed
Subject Keyword	graph problems on-line computation randomized algorithms Randomized algorithms network optimization Graph algorithms Communication networks lower bounds 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

Lower bounds for on-line graph problems with application to on-line circuit and optical routing

Lower bounds for on-line graph problems with application to on-line circuit and optical routing (1996).

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems

Distributed Verification and Hardness of Distributed Approximation

Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles

Multiple Communication in Multihop Radio Networks

TimeSpace Lower Bounds for the PolynomialTime Hierarchy on Randomized Machines

Requirements for Deadlock-Free, Adaptive Packet Routing

Lower Bounds for Randomized k-Server and Motion-Planning Algorithms

Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing

Similar Documents

Lower bounds for on-line graph problems with application to on-line circuit and optical routing

Lower bounds for on-line graph problems with application to on-line circuit and optical routing (1996).

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems

Distributed Verification and Hardness of Distributed Approximation

Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles

Multiple Communication in Multihop Radio Networks

TimeSpace Lower Bounds for the PolynomialTime Hierarchy on Randomized Machines

Requirements for Deadlock-Free, Adaptive Packet Routing

Lower Bounds for Randomized k-Server and Motion-Planning Algorithms

Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing