Some Non-Recent Publications by Joseph Cheriyan

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

• Note for the papers TAP Parts 0,I,II: Our motivation for writing Part I is to give an accessible presentation of the algorithmic ideas and correctness arguments used in Part II, although Part II is essentially self-contained and is "logically independent" of Part I. Part 0 is posted for the sake of archiving/referencing. After reading Part I, readers may be able to reconstruct the results of Parts 0, II.
• ``Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP,'' (with Zhihan Gao).
  Algorithmica (DOI) 10.1007/s00453-016-0270-4, link to Springer Nature SharedIt.
  arXiv: arXiv:1508.07504 [cs.DS] August 2015 (24pages).

• ``Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II,'' (with Zhihan Gao).
  Algorithmica (DOI) 10.1007/s00453-017-0275-7, link to Springer Nature SharedIt.
  arXiv: arXiv:1507.01309 [cs.DS] July 2015 (36pages).

• ``Approximating (Unweighted) Tree Augmentation via Lift-and-Project (Part 0: 1.8 + ... approximation for (Unweighted) TAP) (with Zhihan Gao).
  arXiv: arXiv:1604.00708 [cs.DS] April 2016 (14pages).

• ``On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy,'' (with Zhihan Gao, Costis Georgiou, Sahil Singla).
  Math. Programming (2016) 159:1-29, DOI: 10.1007/s10107-015-0947-5, link to Springer Nature SharedIt.
  arXiv: arXiv:1405.0945v1 [cs.DS] May 2014 (26pages).
  Preliminary version in Proc. ICALP(1) 2013: 340-351, (DOI) 10.1007/978-3-642-39206-1_29, link to Springer LNCS.

• ``Approximating minimum-cost k-node connected subgraphs via independence-free graphs,'' (with Laszlo Vegh).
  pdf Dec. 2012 (20pages).

• ``Approximating minimum-cost connected T-joins,'' (with Zachary Friggstad and Zhihan Gao).
  Preliminary version in Proc. APPROX-RANDOM 2012: 110-121, (DOI) 10.1007/978-3-642-32512-0_10, link to Springer LNCS.
  Full (and improved) paper: arXiv:1207.5722v1 [cs.DS] July 2012 (17pages).

• ``On orienting graphs for connectivity: Projective planes and Halin graphs,'' (with Chenglong Zou), Operations Research Letters 40(5):337-341 (2012), (DOI) 10.1016/j.orl.2012.06.004, link to ORL.
  pdf May 2012 (11pages).

• ``Packing of rigid spanning subgraphs and spanning trees,'' (with Olivier Durand de Gevigney and Zoltan Szigeti)
  pdf Dec. 2011 (8pages).

• ``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), SIAM J.Discrete Math. 27(3):1450-1481 (2013), (DOI) 10.1137/100818728,
  pdf (SIAM copyright!) revised: May, 13,
  pdf initial submission, 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), Discrete Optimization 10(1):25-41 (2013), (DOI) 10.1016/j.disopt.2012.10.002, link to DO.
  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).