{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,28]],"date-time":"2024-08-28T14:40:11Z","timestamp":1724856011869},"reference-count":30,"publisher":"Walter de Gruyter GmbH","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,7,27]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This article gives a short overview of my dissertation, where new algorithms are given for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress.<\/jats:p><jats:p>The first part of the dissertation addresses a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given edge-weighted directed graph. A<jats:italic>\u03c1<\/jats:italic>-approximation algorithm for ATSP is one that runs in polynomial time and always produces a tour at most<jats:italic>\u03c1<\/jats:italic>times longer than the shortest tour. Finding such an algorithm with constant<jats:italic>\u03c1<\/jats:italic>had been a long-standing open problem. Here we give such an algorithm.<\/jats:p><jats:p>The second part of the dissertation addresses the perfect matching problem. We have known since the 1980s that it has efficient parallel algorithms if the use of randomness is allowed. However, we do not know if randomness is necessary \u2013 that is, whether the matching problem is in the class<jats:sans-serif>NC<\/jats:sans-serif>. We show that it is in the class<jats:sans-serif>quasi-NC<\/jats:sans-serif>. That is, we give a deterministic parallel algorithm that runs in poly-logarithmic time on quasi-polynomially many processors.<\/jats:p>","DOI":"10.1515\/itit-2021-0014","type":"journal-article","created":{"date-parts":[[2021,4,16]],"date-time":"2021-04-16T03:23:41Z","timestamp":1618543421000},"page":"177-182","source":"Crossref","is-referenced-by-count":0,"title":["New graph algorithms via polyhedral techniques"],"prefix":"10.1515","volume":"63","author":[{"given":"Jakub","family":"Tarnawski","sequence":"first","affiliation":[{"name":"Microsoft Research , Redmond , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2021,4,15]]},"reference":[{"key":"2023033120153726246_j_itit-2021-0014_ref_001_w2aab3b7c86b1b6b1ab2ab1Aa","doi-asserted-by":"crossref","unstructured":"Nima Anari and Shayan Oveis Gharan. Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 20\u201339, 2015.","DOI":"10.1109\/FOCS.2015.11"},{"key":"2023033120153726246_j_itit-2021-0014_ref_002_w2aab3b7c86b1b6b1ab2ab2Aa","doi-asserted-by":"crossref","unstructured":"Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi. An O(log\u2009n\/log log\u2009n)-approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pages 379\u2013389, 2010.","DOI":"10.1137\/1.9781611973075.32"},{"key":"2023033120153726246_j_itit-2021-0014_ref_003_w2aab3b7c86b1b6b1ab2ab3Aa","doi-asserted-by":"crossref","unstructured":"Stuart J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18(3):147\u2013150, 1984.","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"2023033120153726246_j_itit-2021-0014_ref_004_w2aab3b7c86b1b6b1ab2ab4Aa","doi-asserted-by":"crossref","unstructured":"Markus Bl\u00e4ser. A new approximation algorithm for the asymmetric TSP with triangle inequality. ACM Transactions on Algorithms, 4(4), 2008.","DOI":"10.1145\/1383369.1383378"},{"key":"2023033120153726246_j_itit-2021-0014_ref_005_w2aab3b7c86b1b6b1ab2ab5Aa","doi-asserted-by":"crossref","unstructured":"Moses Charikar, Michel X. Goemans, and Howard J. Karloff. On the integrality ratio for the asymmetric traveling salesman problem. Math. Oper. Res., 31(2):245\u2013252, 2006.","DOI":"10.1287\/moor.1060.0191"},{"key":"2023033120153726246_j_itit-2021-0014_ref_006_w2aab3b7c86b1b6b1ab2ab6Aa","unstructured":"Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Graduate School of Industrial Administration, CMU, 1976."},{"key":"2023033120153726246_j_itit-2021-0014_ref_007_w2aab3b7c86b1b6b1ab2ab7Aa","doi-asserted-by":"crossref","unstructured":"L. Csanky. Fast parallel inversion algorithm. SIAM Journal of Computing, 5:618\u2013623, 1976.","DOI":"10.1137\/0205040"},{"key":"2023033120153726246_j_itit-2021-0014_ref_008_w2aab3b7c86b1b6b1ab2ab8Aa","doi-asserted-by":"crossref","unstructured":"Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449\u2013467, 1965.","DOI":"10.4153\/CJM-1965-045-4"},{"key":"2023033120153726246_j_itit-2021-0014_ref_009_w2aab3b7c86b1b6b1ab2ab9Aa","doi-asserted-by":"crossref","unstructured":"Uriel Feige and Mohit Singh. Improved approximation ratios for traveling salesperson tours and paths in directed graphs. In 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2007, pages 104\u2013118, 2007.","DOI":"10.1007\/978-3-540-74208-1_8"},{"key":"2023033120153726246_j_itit-2021-0014_ref_010_w2aab3b7c86b1b6b1ab2ac10Aa","doi-asserted-by":"crossref","unstructured":"Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 754\u2013763, 2016.","DOI":"10.1145\/2897518.2897564"},{"key":"2023033120153726246_j_itit-2021-0014_ref_011_w2aab3b7c86b1b6b1ab2ac11Aa","doi-asserted-by":"crossref","unstructured":"Alan M. Frieze, Giulia Galbiati, and Francesco Maffioli. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 12(1):23\u201339, 1982.","DOI":"10.1002\/net.3230120103"},{"key":"2023033120153726246_j_itit-2021-0014_ref_012_w2aab3b7c86b1b6b1ab2ac12Aa","doi-asserted-by":"crossref","unstructured":"Shayan Oveis Gharan and Amin Saberi. The asymmetric traveling salesman problem on graphs with bounded genus. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pages 967\u2013975, 2011.","DOI":"10.1137\/1.9781611973082.75"},{"key":"2023033120153726246_j_itit-2021-0014_ref_013_w2aab3b7c86b1b6b1ab2ac13Aa","doi-asserted-by":"crossref","unstructured":"Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. A randomized rounding approach to the traveling salesman problem. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pages 550\u2013559, 2011.","DOI":"10.1109\/FOCS.2011.80"},{"key":"2023033120153726246_j_itit-2021-0014_ref_014_w2aab3b7c86b1b6b1ab2ac14Aa","doi-asserted-by":"crossref","unstructured":"Nicholas J.\u2009A. Harvey. Algebraic algorithms for matching and matroid problems. SIAM J. Comput., 39(2):679\u2013702, 2009.","DOI":"10.1137\/070684008"},{"key":"2023033120153726246_j_itit-2021-0014_ref_015_w2aab3b7c86b1b6b1ab2ac15Aa","doi-asserted-by":"crossref","unstructured":"Haim Kaplan, Moshe Lewenstein, Nira Shafrir, and Maxim Sviridenko. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. J. ACM, 52(4):602\u2013626, 2005.","DOI":"10.1145\/1082036.1082041"},{"key":"2023033120153726246_j_itit-2021-0014_ref_016_w2aab3b7c86b1b6b1ab2ac16Aa","doi-asserted-by":"crossref","unstructured":"Richard M. Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is in random NC. Combinatorica, 6(1):35\u201348, 1986.","DOI":"10.1007\/BF02579407"},{"key":"2023033120153726246_j_itit-2021-0014_ref_017_w2aab3b7c86b1b6b1ab2ac17Aa","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. On determinants, matchings, and random algorithms. In FCT, pages 565\u2013574, 1979."},{"key":"2023033120153726246_j_itit-2021-0014_ref_018_w2aab3b7c86b1b6b1ab2ac18Aa","doi-asserted-by":"crossref","unstructured":"Meena Mahajan and Kasturi R. Varadarajan. A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs. In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC, pages 351\u2013357, 2000.","DOI":"10.1145\/335305.335346"},{"key":"2023033120153726246_j_itit-2021-0014_ref_019_w2aab3b7c86b1b6b1ab2ac19Aa","doi-asserted-by":"crossref","unstructured":"G.\u2009L. Miller and J. Naor. Flow in planar graphs with multiple sources and sinks. In 30th Annual Symposium on Foundations of Computer Science, pages 112\u2013117, 1989.","DOI":"10.1109\/SFCS.1989.63464"},{"key":"2023033120153726246_j_itit-2021-0014_ref_020_w2aab3b7c86b1b6b1ab2ac20Aa","doi-asserted-by":"crossref","unstructured":"Tobias M\u00f6mke and Ola Svensson. Removing and adding edges for the traveling salesman problem. J. ACM, 63(1):2:1\u20132:28, 2016.","DOI":"10.1145\/2739008"},{"key":"2023033120153726246_j_itit-2021-0014_ref_021_w2aab3b7c86b1b6b1ab2ac21Aa","doi-asserted-by":"crossref","unstructured":"Marcin Mucha. 13\/9-approximation for graphic TSP. In 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, pages 30\u201341, 2012.","DOI":"10.1007\/s00224-012-9439-7"},{"key":"2023033120153726246_j_itit-2021-0014_ref_022_w2aab3b7c86b1b6b1ab2ac22Aa","doi-asserted-by":"crossref","unstructured":"Marcin Mucha and Piotr Sankowski. Maximum matchings via Gaussian elimination. In 45th Symposium on Foundations of Computer Science (FOCS), pages 248\u2013255, 2004.","DOI":"10.1007\/978-3-540-30140-0_48"},{"key":"2023033120153726246_j_itit-2021-0014_ref_023_w2aab3b7c86b1b6b1ab2ac23Aa","doi-asserted-by":"crossref","unstructured":"Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105\u2013113, 1987.","DOI":"10.1007\/BF02579206"},{"key":"2023033120153726246_j_itit-2021-0014_ref_024_w2aab3b7c86b1b6b1ab2ac24Aa","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s Seb\u0151 and Jens Vygen. Shorter tours by nicer ears: 7\/5-approximation for the graph-TSP, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica, 34(5):597\u2013629, 2014.","DOI":"10.1007\/s00493-014-2960-3"},{"key":"2023033120153726246_j_itit-2021-0014_ref_025_w2aab3b7c86b1b6b1ab2ac25Aa","doi-asserted-by":"crossref","unstructured":"O. Svensson and J. Tarnawski. The matching problem in general graphs is in Quasi-NC. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 696\u2013707, 2017.","DOI":"10.1109\/FOCS.2017.70"},{"key":"2023033120153726246_j_itit-2021-0014_ref_026_w2aab3b7c86b1b6b1ab2ac26Aa","doi-asserted-by":"crossref","unstructured":"Ola Svensson. Approximating ATSP by relaxing connectivity. In FOCS 2015: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, 2015.","DOI":"10.1109\/FOCS.2015.10"},{"key":"2023033120153726246_j_itit-2021-0014_ref_027_w2aab3b7c86b1b6b1ab2ac27Aa","doi-asserted-by":"crossref","unstructured":"Ola Svensson, Jakub Tarnawski, and L\u00e1szl\u00f3\u2009A. V\u00e9gh. A constant-factor approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 204\u2013213, New York, NY, USA, 2018.","DOI":"10.1145\/3188745.3188824"},{"key":"2023033120153726246_j_itit-2021-0014_ref_028_w2aab3b7c86b1b6b1ab2ac28Aa","doi-asserted-by":"crossref","unstructured":"Ola Svensson, Jakub Tarnawski, and L\u00e1szl\u00f3\u2009A. V\u00e9gh. Constant factor approximation for ATSP with two edge weights. Mathematical Programming, 172(1-2):371\u2013397, 2018.","DOI":"10.1007\/s10107-017-1195-7"},{"key":"2023033120153726246_j_itit-2021-0014_ref_029_w2aab3b7c86b1b6b1ab2ac29Aa","unstructured":"Jakub Tarnawski. New Graph Algorithms via Polyhedral Techniques. EPFL, Lausanne, 2019."},{"key":"2023033120153726246_j_itit-2021-0014_ref_030_w2aab3b7c86b1b6b1ab2ac30Aa","doi-asserted-by":"crossref","unstructured":"W.\u2009T. Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, 22:107\u2013111, 1947.","DOI":"10.1112\/jlms\/s1-22.2.107"}],"container-title":["it - Information Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2021-0014\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2021-0014\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,28]],"date-time":"2024-08-28T13:38:34Z","timestamp":1724852314000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2021-0014\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,15]]},"references-count":30,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,5,13]]},"published-print":{"date-parts":[[2021,7,27]]}},"alternative-id":["10.1515\/itit-2021-0014"],"URL":"https:\/\/doi.org\/10.1515\/itit-2021-0014","relation":{},"ISSN":["2196-7032","1611-2776"],"issn-type":[{"type":"electronic","value":"2196-7032"},{"type":"print","value":"1611-2776"}],"subject":[],"published":{"date-parts":[[2021,4,15]]}}}