NDLI: Breaking $o(n^{1/2})-approximation$ algorithms for the edge-disjoint paths problem with congestion two

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

The power of simple tabulation hashing

Quantum one-way communication can be exponentially stronger than classical communication

Cover times, blanket times, and majorizing measures

The equivalence of the random oracle model and the ideal cipher model, revisited

On optimal single-item auctions

Towards coding for maximum errors in interactive communication

Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm

Moser and tardos meet Lovász

Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

An algorithm for the graph crossing number problem

The computational complexity of linear optics

Distributed verification and hardness of distributed approximation

An LLL-reduction algorithm with quasi-linear time complexity: extended abstract

Contraction decomposition in h-minor-free graphs and algorithmic applications

On the complexity of powering in finite fields

Mechanisms for (mis)allocating scientific credit

Don't rush into a union: take time to find your roots

Online bipartite matching with unknown distributions

K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance

Schaefer's theorem for graphs

Constant round non-malleable protocols using one way functions

Fast moment estimation in data streams in optimal space

Submodular function maximization via the multilinear relaxation and contention resolution schemes

Tight bounds for parallel randomized load balancing: extended abstract

Strong direct product theorems for quantum communication and query complexity

A general framework for graph sparsification

Separating succinct non-interactive arguments from all falsifiable assumptions

Optimal auctions with correlated bidders are easy

High-rate codes with sublinear-time decoding

Exact algorithms for solving stochastic games: extended abstract

A full derandomization of schöning's k-SAT algorithm

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

Improved algorithms for min cut and max flow in undirected planar graphs

A quasipolynomial-time algorithm for the quantum separability problem

Linearizable implementations do not suffice for randomized distributed computation

NP-hardness of approximately solving linear equations over reals

A simpler algorithm and shorter proof for the graph minor decomposition

Almost settling the hardness of noncommutative determinant

Inner product spaces for MinSum coordination mechanisms

A unified framework for approximating and clustering data

Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs

Breaking the $k^{2}$ barrier for explicit RIP matrices

Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP

Constant-round non-malleable commitments from any one-way function

Subspace embeddings for the $L_{1}-norm$ with applications

Learning submodular functions

Social networks spread rumors in sublogarithmic time

An optimal lower bound on the communication complexity of gap-hamming-distance

Breaking $o(n^{1/2})-approximation$ algorithms for the edge-disjoint paths problem with congestion two

Limits of provable security from standard assumptions

An impossibility result for truthful combinatorial auctions with submodular valuations

From affine to two-source extractors via approximate duality

Dueling algorithms

Pseudorandom generators for combinatorial shapes

Analyzing network coding gossip made easy

Directed spanners via flow-based linear programs

Parallel repetition of entangled games

The topology of wireless communication

Black-box identity testing of depth-4 multilinear circuits

Multicut is FPT

Geometric complexity theory and tensor rank

Mechanism design with uncertain inputs: (to err is human, to forgive divine)

Approximate polytope membership queries

Almost tight bounds for reordering buffer management

Deterministic construction of a high dimensional $l_{p}$ section in $l_{1}^{n}$ for any p<2

Every property of hyperfinite graphs is testable

Secure computation with information leaking to an adversary

Near-optimal distortion bounds for embedding doubling spaces into $L_{1}$

Privately releasing conjunctions and the statistical query barrier

From convex optimization to randomized mechanisms: toward optimal combinatorial auctions

Correlation testing for affine invariant properties on $F_{p}^{n}$ in the high error regime

Pareto optimal solutions for smoothed analysts

Pseudorandom generators for group products: extended abstract

Optimal path search in small worlds: dimension matters

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

Fixed-parameter tractability of multicut parameterized by the size of the cutset

Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes

Santa Claus schedules jobs on unrelated machines

Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs

How to leak on key updates

From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking

Privacy-preserving statistical estimation with optimal convergence rates

Finding topological subgraphs is fixed-parameter tractable

Near-optimal private approximation protocols via a black box transformation

Breaking $o(n^{1/2})-approximation$ algorithms for the edge-disjoint paths problem with congestion two

Content Provider	ACM Digital Library
Author	Kawarabayashi, Ken-ichi Kobayashi, Yusuke
Abstract	In the maximum edge-disjoint paths problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be routed by edge-disjoint paths. An r-approximation algorithm for this problem is a polynomial time algorithm that finds at least OPT / r edge-disjoint paths, where OPT is the maximum possible. Currently, an $O(n^{1/2})-approximation$ algorithm is best known for this problem even if a congestion of two is allowed, i.e., each edge is allowed to be used in at most two of the paths. In this paper, we give a randomized $O(n^{3/7}$ • poly (log n))-approximation algorithm with congestion two. This is the first result that breaks the $O(n^{1/2})-approximation$ algorithm. In particular, we prove the following. 1. If we have a (randomized) polynomial time algorithm for finding $Ω(OPT^{1/p})$ edge-disjoint paths for some p>1, then, for some α >0, we can give a randomized $O(n^{1/2-α})-approximation$ algorithm for the maximum edge-disjoint paths problem by using Rao-Zhou's algorithm. 2. Based on the well-linked set of Chekuri, Khanna, and Shepherd, we show that there is a randomized algorithm for finding $Ω(OPT^{1/4})$ edge-disjoint paths connecting given terminal pairs with congestion two. Our framework for this algorithm is more general. Indeed, the above two ingredients also work for the maximum edge-disjoint paths problem (with congestion one) if the following conjecture is true. Conjecture: There is a (randomized) polynomial time algorithm for finding $Ω(OPT^{1/p}/β(n))$ edge-disjoint paths connecting given terminal pairs, where β is a poly-logarithmic function.
Starting Page	81
Ending Page	88
Page Count	8
File Format	PDF MP4
ISBN	9781450306911
DOI	10.1145/1993636.1993648
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-06-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Chekuri--khanna--shepherd well-linked set Rao--zhou algorithm Disjoint paths
Content Type	Audio 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