Some Recent Publications by Joseph Cheriyan
(In case of published papers, the publisher has the copyright.)

``Approximation algorithms for the Matching Augmentation Problem''
(slides of talk, based on work with R.Cummings, J.Dippel, J.Zhu).
pdf
Oct. 2020.

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 selfcontained 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 LiftandProject, Part I: Stemless TAP,''
(with Zhihan Gao).
Algorithmica
(DOI) 10.1007/s0045301602704,
link to Springer Nature SharedIt.
arXiv:
arXiv:1508.07504 [cs.DS]
August 2015 (24pages).

``Approximating (Unweighted) Tree Augmentation via LiftandProject, Part II,''
(with Zhihan Gao).
Algorithmica
(DOI) 10.1007/s0045301702757,
link to Springer Nature SharedIt.
arXiv:
arXiv:1507.01309 [cs.DS]
July 2015 (36pages).

``Approximating (Unweighted) Tree Augmentation via LiftandProject
(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 SheraliAdams Hierarchy,''
(with Zhihan Gao, Costis Georgiou, Sahil Singla).
Math. Programming (2016) 159:129,
DOI: 10.1007/s1010701509475,
link to Springer Nature SharedIt.
arXiv:
arXiv:1405.0945v1 [cs.DS]
May 2014 (26pages).
Preliminary version in Proc. ICALP(1) 2013: 340351,
(DOI) 10.1007/9783642392061_29,
link to Springer LNCS.

``Approximating minimumcost knode connected subgraphs via
independencefree graphs,''
(with Laszlo Vegh).
pdf
Dec. 2012 (20pages).

``Approximating minimumcost connected Tjoins,''
(with Zachary Friggstad and Zhihan Gao).
Preliminary version in Proc. APPROXRANDOM 2012: 110121,
(DOI) 10.1007/9783642325120_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):337341 (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. ACMSIAM SODA, 2012.
pdf
(13pages).

``Approximation algorithms for minimumcost
k(S,T) connected digraphs,''
(with Bundit Laekhanukit),
SIAM J.Discrete Math. 27(3):14501481 (2013),
(DOI) 10.1137/100818728,
pdf (SIAM copyright!)
revised: May, 13,
pdf
initial submission, Nov, 10 (39pages).

``Combinatorial optimization on kconnected 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):2541 (2013),
(DOI) 10.1016/j.disopt.2012.10.002,
link to DO.
pdf
revised: June, 10 (22pages).

``Approximation Algorithms and Hardness Results for Packing
ElementDisjoint Steiner Trees in Planar Graphs,''
(with Ashkan Aazami and K.Raju Jampani).
Preliminary version in Proc. APPROXRANDOM 2009: 114,
link to Springer LNCS.
Algorithmica (DOI) 10.1007/s0045301195403,
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):206211 (2012)
pdf (10pages).

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

``Packing ElementDisjoint 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): 612636, 2007,
pdf (25pages).
Preliminary version in Proc. ACM STOC, 2005.
pdf (9pages).

``An O(VE) algorithm for ear decompositions of matchingcovered graphs,''
(with Marcelo Carvalho),
ACM Trans. On Algorithms 1:324337, 2005,
pdf (12pages).
(Preliminary version in Proc. ACMSIAM SODA, 2005.)

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

``Approximating directed multicuts,''
(with Howard Karloff and Yuval Rabani),
Combinatorica 25(3): 251269, 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): 255275, 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.3044, June 2001.)

``An approximation algorithm for the minimumcost
kvertex connected subgraph,''
(with Santosh Vempala and Adrian Vetta),
SICOMP (SIAM J. Comput.) 32: 10501055, 2003,
pdf (6pages).

``On rooted nodeconnectivity problems,''
(with T.Jordan and Z.Nutov),
Algorithmica 30: 353375, 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.5approximation of
a smallest 2edge connected spanning subgraph,"
(with A.Sebo and Z.Szigeti), Sept. 1999,
SIAM J. Discrete Math. 14:170180, 2001,
pdf (13pages).
(Preliminary version in
6th International IPCO
(Integer Programming and Combinatorial Optimization) Conference,
Houston, Texas, June 1998. Proceedings LNCS 1412.)

``Approximating minimumsize kconnected spanning subgraphs
via matching,'' (with Ramki Thurimella),
SIAM J. Computing 30: 528560, 2000,
pdf (36pages).
(Previous versions in
Electronic Colloquium on Computational Complexity,
TR98025, and
Proc. 37th IEEE FOCS (1996), pp.292301.)

``Fast algorithms for kshredders and knode connectivity
augmentation,'' (with Ramki Thurimella),
J.Algorithms 33 (1999) pp.1550,
pdf (25pages).
(Preliminary version in
Proc. 28th ACM STOC (1996).)

``An analysis of the highestlevel selection rule in
the preflowpush maxflow algorithm,''
(with K.Mehlhorn),
Information Processing Letters 69 (1999) pp.239242,
pdf (5pages).

``On 2coverings and 2packings 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.16351655,
pdf (25pages).

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