NDLI: Hardness of routing with congestion in directed graphs

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

Statistically-hiding commitment from any one-way function

Voronoi diagrams in n · 2o(√lg lg n) time

Faster integer multiplication

Smooth sensitivity and sampling in private data analysis

How to rank with few errors

On the submodularity of influence in social networks

Hardness of routing with congestion in directed graphs

Iteratively constructing preconditioners via the conjugate gradient method

Distributed computing theory: algorithms, impossibility results, models, and proofs

The condition number of a randomly perturbed matrix

Circuit lower bounds for Merlin-Arthur classes

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

Linear probing with constant independence

Limitations of VCG-based mechanisms

Interval completion with few edges

Parallel repetition: simplifications and the no-signaling case

Randomly coloring planar graphs with fewer colors than the maximum degree

Property testing in hypergraphs and the removal lemma

Exponential separations for one-way quantum communication complexity, with applications to cryptography

Playing games with approximation algorithms

Toward a general theory of quantum games

All-pairs bottleneck paths for general graphs in truly sub-cubic time

Uncertainty principles, extractors, and explicit embeddings of l2 into l1

Survivable network design with degree or order constraints

Lower bounds for randomized read/write stream algorithms

On achieving the "best of both worlds" in secure multiparty computation

Lower bounds for 2-dimensional range counting

Fourier meets möbius: fast subset convolution

The price of privacy and the limits of LP decoding

Approximation algorithms for budgeted learning problems

First to market is not everything: an analysis of preferential attachment with fitness

Polynomial flow-cut gaps and hardness of directed cut problems

On the convergence of Newton's method for monotone systems of polynomial equations

Balanced allocations: the weighted case

Interpolation of depth-3 arithmetic circuits with two multiplication gates

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems

Optimal suffix selection

The communication complexity of uncoupled nash equilibrium procedures

Computing crossing number in linear time

An efficient parallel repetition theorem for Arthur-Merlin games

Inapproximability of the Tutte polynomial

Testing k-wise and almost k-wise independence

Negative weights make adversaries stronger

Reordering buffers for general metric spaces

Search via quantum walk

More algorithms for all-pairs shortest paths in weighted graphs

Vertex cuts, random walks, and dimension reduction in series-parallel graphs

Approximating minimum bounded degree spanning trees to within one of optimal

Lower bounds in communication complexity based on factorization norms

Zero-knowledge from secure multiparty computation

Combinatorial complexity in O-minimal geometry

An approximation algorithm for max-min fair allocation of indivisible goods

Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads

Balanced max 2-sat might not be the hardest

A combinatorial, primal-dual approach to semidefinite programs

Towards 3-query locally decodable codes of subexponential length

Separating $AC^{0}$ from depth-2 majority circuits

Proportional response dynamics leads to market equilibrium

Terminal backup, 3D matching, and covering cubic graphs

Low-end uniform hardness vs. randomness tradeoffs for AM

Tensor-based hardness of the shortest vector problem to within almost polynomial factors

Low-degree tests at large distances

On the impossibility of a quantum sieve algorithm for graph isomorphism

Some new results on node-capacitated packing of A-paths

Local embeddings of metric spaces

Improved approximation for directed cut problems

Constructing non-computable Julia sets

Simple deterministic approximation algorithms for counting matchings

Tight bounds for asynchronous randomized consensus

A 3-query PCP over integers

One sketch for all: fast algorithms for compressed sensing

Eisenberg-Gale markets: algorithms and structural properties

Holographic algorithms: from art to science

Verifying and decoding in constant depth

Lattices that admit logarithmic worst-case to average-case connection factors

An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs

Sampling-based dimension reduction for subspace approximation

Degree-constrained network flows

Hardness of routing with congestion in directed graphs

Content Provider	ACM Digital Library
Author	Khanna, Sanjeev Chuzhoy, Julia Talwar, Kunal Guruswami, Venkatesan
Abstract	Given as input a directed graph on n vertices and a set ofsource-destination pairs, we study the problem of routing themaximum possible number of source-destination pairs on paths, suchthat at most c(N) paths go through any edge. We show that theproblem is hard to approximate within an $N^{Ω(1/c(N))}$ factoreven when we compare to the optimal solution that routes pairs onedge-disjoint paths, assuming NP doesn't have NO(log logN)-time randomized algorithms. Here the congestion c(N) can beany function in the range 1 ≤ c(N) ≤ α log N/log log N for some absolute constant α > 0. The hardness result is in the right ballpark since a factor $N^{O(1/c(N))}$ approximation algorithm is known for this problem, viarounding a natural multicommodity-flow relaxation. We also give asimple integrality gap construction that shows that themulticommodity-flow relaxation has an integrality gap of $N^{Ω(1/c)}$ for c ranging from 1 to Θ((log n)/(log log n)). A solution to the routing problem involves selecting which pairs tobe routed and what paths to assign to each routed pair. Two naturalrestrictions can be placed on input instances to eliminate one ofthese aspects of the problem complexity. The first restriction is toconsider instances with perfect completeness; an optimalsolution is able to route all pairs with congestion 1 in suchinstances. The second restriction to consider is the uniquepaths property where each source-destination pair has a unique pathconnecting it in the instance. An important aspect of our result isthat it holds on instances with any one of these tworestrictions. Our hardness construction with the perfectcompleteness restriction allows us to conclude that the directedcongestion minimization problem, where the goal is to route allpairs with minimum congestion, is hard to approximate to within afactor of Ω(log N/log log N). On the other hand, thehardness construction with unique paths property allows us toconclude an $N^{Ω(1/c)}$ inapproximability bound also for theall-or-nothing flow problem. This is in a sharp contrast to theundirected setting where the all-or-nothing flow problem is known tobe approximable to within a poly-logarithmic factor.
Starting Page	165
Ending Page	178
Page Count	14
File Format	PDF
ISBN	9781595936318
DOI	10.1145/1250790.1250816
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-06-11
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Congestion minimization All-or-nothing flow Edge-disjoint paths Hardness of approximation Multicommodity flow Integrality gap
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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