Some Recent Publications by Joseph Cheriyan

(In case of published papers, the publisher has the copyright.)

• ``Approximating rooted Steiner networks,'' (with Bundit Laekhanukit, Guyslain Naves, and Adrian Vetta), Proc. ACM-SIAM SODA, 2012.
  pdf (13pages).

• ``Approximation algorithms for minimum-cost k-(S,T) connected digraphs,'' (with Bundit Laekhanukit),
  pdf revised: Nov, 10 (39pages).

• ``Combinatorial optimization on k-connected graphs,''
  pdf ICRTGC - ICM 2010 satellite conference, Aug. 2010, revised: May, 10 (4pages).

• ``A bad example for the iterative rounding method for mincost $k$-connected spanning subgraphs,'' (with Ashkan Aazami and Bundit Laekhanukit),
  pdf revised: June, 10 (22pages).

• ``Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs,'' (with Ashkan Aazami and K.Raju Jampani).
  Preliminary version in Proc. APPROX-RANDOM 2009: 1-14, link to Springer LNCS.
  Algorithmica (DOI) 10.1007/s00453-011-9540-3, link to Springer. Authors' copy pdf (29pages).

• ``On the maximum size of a minimal $k$-edge connected augmentation,'' (with A.V.Kotlov), JCTB 102(1):206-211 (2012)
  pdf (10pages).

• ``On the Integrality Ratio For Tree Augmentation,'' (with H.J.Karloff, R.Khandekar, J.Konemann), Operations Research Letters 36(4):399-401 (2008),
  pdf (4pages).

• ``Packing Element-Disjoint Steiner Trees,'' (with Mohammad Salavatipour), ACM Trans. On Algorithms 3(4):10pages, 2007.
  Preliminary version in Proc. APPROX, 2005 pdf (10pages). link to Springer LNCS.

• ``Approximation Algorithms for Network Design with Metric Costs,'' (with Adrian Vetta), SIDMA (SIAM J. Discr. Math.) 21(3): 612--636, 2007, pdf (25pages).
  Preliminary version in Proc. ACM STOC, 2005. pdf (9pages).

• ``An O(VE) algorithm for ear decompositions of matching-covered graphs,'' (with Marcelo Carvalho), ACM Trans. On Algorithms 1:324--337, 2005, pdf (12pages).
  (Preliminary version in Proc. ACM-SIAM SODA, 2005.)

• ``Hardness and approximation results for packing Steiner trees,'' (with Mohammad Salavatipour), Algorithmica 45(1): 21--43, 2006, pdf (22pages).
  (Preliminary version in Proc. ESA, 2004 pdf (12pages).)

• ``Approximating directed multicuts,'' (with Howard Karloff and Yuval Rabani), Combinatorica 25(3): 251-269, 2005, pdf (14pages).
  (Preliminary version in the Proc. 42nd IEEE FOCS, 2001.)

• ``Network design via iterative rounding of setpair relaxations,'' (with Santosh Vempala and Adrian Vetta), Combinatorica 26(3): 255--275, 2006, pdf (21pages).

• ``Edge covers of setpairs and the iterative rounding method,'' (with Santosh Vempala). pdf (18pages).
  (Preliminary version in the Proc. Integer Programming and Combinatorial Optimization, 8th International IPCO Conference, Utrecht, The Netherlands, pp.30-44, June 2001.)

• ``An approximation algorithm for the minimum-cost k-vertex connected subgraph,'' (with Santosh Vempala and Adrian Vetta), SICOMP (SIAM J. Comput.) 32: 1050--1055, 2003, pdf (6pages).

• ``On rooted node-connectivity problems,'' (with T.Jordan and Z.Nutov), Algorithmica 30: 353--375, 2001, pdf (21pages).
  (Preliminary version in 1st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, University of Aalborg, Denmark, July 1998.)

• ``Improving on the 1.5-approximation of a smallest 2-edge connected spanning subgraph," (with A.Sebo and Z.Szigeti), Sept. 1999, SIAM J. Discrete Math. 14:170--180, 2001, pdf (13pages).
  (Preliminary version in 6th International IPCO (Integer Programming and Combinatorial Optimization) Conference, Houston, Texas, June 1998. Proceedings LNCS 1412.)

• ``Approximating minimum-size k-connected spanning subgraphs via matching,'' (with Ramki Thurimella), SIAM J. Computing 30: 528--560, 2000, pdf (36pages).
  (Previous versions in Electronic Colloquium on Computational Complexity, TR98-025, and Proc. 37th IEEE FOCS (1996), pp.292-301.)

• ``Fast algorithms for k-shredders and k-node connectivity augmentation,'' (with Ramki Thurimella), J.Algorithms 33 (1999) pp.15-50, pdf (25pages).
  (Preliminary version in Proc. 28th ACM STOC (1996).)

• ``An analysis of the highest-level selection rule in the preflow-push max-flow algorithm,'' (with K.Mehlhorn), Information Processing Letters 69 (1999) pp.239-242, pdf (5pages).

• ``On 2-coverings and 2-packings of laminar families,'' (with T.Jordan and R.Ravi), Jan. 1999, pdf (17pages).
  (Preliminary version in Proc. European Sympos. Algorithms '99.)

• ``Randomized $\SOFT{O} (M(|V|))$ algorithms for problems in matching theory,'' SIAM J. Computing 26 (1997), pp.1635-1655, pdf (25pages).

• ``Approximation algorithms for feasible cut and multicut problems,'' (with Bo Yu) European Sympos. Algorithms '95, Proceedings: LNCS 979, Springer-Verlag, (1995), pp.394-408. Detailed version, Nov. 1995. pdf (19pages).