Arrow Research search

Author name cluster

Joseph Cheriyan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers
1 author row

Possible papers

14

FOCS Conference 2013 Conference Paper

Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs

  • Joseph Cheriyan
  • László A. Végh

We present a 6-approximation algorithm for the minimum-cost k-node connected spanning sub graph problem, assuming that the number of nodes is at least k3(k-1)+k. We apply a combinatorial preprocessing, based on the Frank-Tardos algorithm for k-out connectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant-factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of k.

Details

SODA Conference 2012 Conference Paper

Approximating rooted Steiner networks

  • Joseph Cheriyan
  • Bundit Laekhanukit
  • Guyslain Naves
  • Adrian Vetta

The Directed Steiner Tree (DST) problem is a cornerstone problem in network design. We focus on the generalization of the problem with higher connectivity requirements. The problem with one root and two sinks is APX-hard. The problem with one root and many sinks is as hard to approximate as the directed Steiner forest problem, and the latter is well known to be as hard to approximate as the label cover problem. Utilizing previous techniques (due to others), we strengthen these results and extend them to undirected graphs. Specifically, we give an Ω( k ∊ ) hardness bound for the rooted k -connectivity problem in undirected graphs; this addresses a recent open question of Khanna. As a consequence, we also obtain the Ω( k ∊ ) hardness of the undirected subset k -connectivity problem. Additionally, we give a result on the integrality ratio of the natural linear programming relaxation of the directed rooted k -connectivity problem.

Details

STOC Conference 2005 Conference Paper

Approximation algorithms for network design with metric costs

  • Joseph Cheriyan
  • Adrian Vetta

We study undirected networks with edge costs that satisfy the triangle inequality. Let n denote the number of nodes. We present an O (1)-approximation algorithm for a generalization of the metric-cost subset k -node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each k =1,2,…, n -1, there exists a k -node connected graph whose cost is within a factor of 24 of the cost of any simple k -edge connected graph. This resolves an open question in the area. Based on our O (1)-approximation algorithm, we present an O (log r max )-approximation algorithm for the node-connectivity survivable network design problem where r max denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of zero or one, where Kortsarz et al. [20]recently proved, assuming NP⊈, quasi-P, a hardness-of-approximation lower bound of 2 log 1-ε n for the subset k -node-connectivity problem, where ε denotes a small positive number.

Details

STOC Conference 2002 Conference Paper

Approximation algorithms for minimum-cost k-vertex connected subgraphs

  • Joseph Cheriyan
  • Santosh S. Vempala
  • Adrian Vetta

(MATH) We present two new algorithms for the problem of finding a minimum-cost k -vertex connected spanning subgraph. The first algorithm works on undirected graphs with at least 6k 2 vertices and achieves an approximation factor of 6 times the k th harmonic number, which is $O(\log k)$. The second algorithm works on directed and undirected graphs. It gives an $O(\sqrt{ n /\keps})$-approximation algorithm for any $\keps > 0$ and $k \le (1-\keps)n$. The latter algorithm also extends to other problems in network design with vertex connectivity requirements. Our main tools are setpair relaxations, a theorem of Mader's (in the undirected case) and iterative rounding (general case).

Details

FOCS Conference 2001 Conference Paper

Approximating Directed Multicuts

  • Joseph Cheriyan
  • Howard J. Karloff
  • Yuval Rabani

The seminal paper of F. T. Leighton and S. Rao (1988) and subsequent papers presented approximate min-max theorems relating multicommodity flow values and cut capacities in undirected networks, developed the divide-and-conquer method for designing approximation algorithms, and generated novel tools for utilizing linear programming relaxations. Yet, despite persistent research efforts, these achievements could not be extended to directed networks, excluding a few cases that are "symmetric" and therefore similar to undirected networks. The paper is an attempt to remedy the situation. We consider the problem of finding a minimum multicut in a directed multicommodity flow network, and give the first nontrivial upper bounds on the maxflow-to-min multicut ratio. Our results are algorithmic, demonstrating nontrivial approximation guarantees.

Details

FOCS Conference 1996 Conference Paper

Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching (extended abstract)

  • Joseph Cheriyan
  • Ramakrishna Thurimella

An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of a given (undirected or directed) graph G=(V, E). There are four versions of the problem, depending on whether G is undirected or directed, and whether the spanning subgraph is required to be k-node connected (k-NCSS) or k-edge connected (k-ECSS). The approximation guarantees are as follows: min-size k-NCSS of an undirected graph 1+[1/k], min-size k-NCSS of a directed graph 1+[1/k], min-size k-ECSS of an undirected graph 1+[7/k], & min-size k-ECSS of a directed graph 1+[4//spl radic/k]. The heuristic is based on a subroutine for the degree-constrained subgraph (b-matching) problem. It is simple, deterministic, and runs in time O(k|E|/sup 2/). For undirected graphs and k=2, a (deterministic) parallel NC version of the heuristic finds a 2-node connected (or a-edge connected) spanning subgraph whose size is within a factor of (1. 5+/spl epsiv/) of minimum, where /spl epsiv/>0 is a constant.

Details

FOCS Conference 1989 Conference Paper

A Randomized Maximum-Flow Algorithm

  • Joseph Cheriyan
  • Torben Hagerup

The authors present a randomized maximum-flow algorithm, called the PLED (prudent linking excess diminishing) algorithm, whose expected running time is O(nm+n/sup 2/(log n)/sup 3/); this is O(nm) for all except relatively sparse networks. The algorithm is always correct, and in the worst case, which occurs with negligible probability, it take O(nm log n) time. The approach taken is to maintain a parameter Delta, which is a measure of the maximum flow excess of a vertex and of the maximum amount of flow sent by a single operation. Initially, Delta is less than or equal to the maximum edge capacity, and Delta =0 at termination. The execution of the PLED algorithm is partitioned into phases so that Delta stays fixed during each phase and decreases between consecutive phases. In order to achieve a bound on the number of phases that is independent of the maximum edge capacity, the algorithm decreases Delta by as large a factor (>or=2) as possible, rather than by a constant factor. The algorithm uses the dynamic trees data structure. >

Details
v2026.09.13