Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-26T12:16:51.052Z Has data issue: false hasContentIssue false

Bibliography

Published online by Cambridge University Press:  14 November 2024

Vera Traub  and
Jens Vygen
Vera Traub
Affiliation:
University of Bonn
Jens Vygen
Affiliation:
University of Bonn
Get access
Type
Chapter
Information
Approximation Algorithms for Traveling Salesman Problems , pp. 407 - 422
Publisher: Cambridge University Press
Print publication year: 2024

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ageev, A.A., and Sviridenko, M.I. [2004]: Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal on Combinatorial Optimization 8 (2004), 307–328CrossRefGoogle Scholar
Agrawal, A., Klein, P.N., and Ravi, R. [1995]: When trees collide: An approximation algorithm for the generalized Steiner tree problem in networks. SIAM Journal on Computing 24 (1995), 440–456CrossRefGoogle Scholar
Alexander, A., Boyd, S., and Elliott-Magwood, P. [2006]: On the integrality gap of the 2-edge connected subgraph problem. Technical Report TR-2006-04, SITE, University of Ottawa 2006Google Scholar
Altinkemer, K., and Gavish, B. [1987]: Heuristics for unequal weight delivery problems with a fixed error guarantee. Operations Research Letters 6 (1987), 149–158CrossRefGoogle Scholar
An, H.-C., Kleinberg, R., and Shmoys, D.B. [2015]: Improving Christofides’ algorithm for the s-t path TSP. Journal of the ACM 62 (2015), Article 34CrossRefGoogle Scholar
An, H.-C., Kleinberg, R., and Shmoys, D.B. [2021]: Approximation algorithms for the bottleneck asymmetric traveling salesman problem. ACM Transactions on Algorithms 17 (2021), 1–12CrossRefGoogle Scholar
Anari, N., Liu, K., Oveis Gharan, S., Vinzant, C., and Vuong, T.-D. [2021]: Log-concave polynomials IV: Approximate exchange, tight mixing times, and near-optimal sampling of forests. Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021), 408–420CrossRefGoogle Scholar
Anari, N., and Oveis Gharan, S. [2015]: Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP. Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), 20–39CrossRefGoogle Scholar
Applegate, D.L., Bixby, R., Chvátal, V., and Cook, W.J. [2006]: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton 2006Google Scholar
Archer, A., Bateni, M., Hajiaghayi, M., and Karloff, H. [2011]: Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM Journal on Computing 30 (2011), 309–332CrossRefGoogle Scholar
Arora, S. [1998]: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM 45 (1998), 753–782CrossRefGoogle Scholar
Arora, S., and Karakostas, G. [2006]: A 2 + ε approximation algorithm for the k-MST problem. Mathematical Programming 107 (2006), 491–504CrossRefGoogle Scholar
Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. [1998]: Proof verification and hardness of approximation problems. Journal of the ACM 45 (1998), 501–555CrossRefGoogle Scholar
Asadpour, A., Goemans, M.X., Mądry, A., Oveis Gharan, S., and Saberi, A. [2017]: An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem. Operations Research 65 (2017), 1043–1061CrossRefGoogle Scholar
Balas, E. [1989]: The prize collecting traveling salesman problem. Networks 19 (1989), 621–636CrossRefGoogle Scholar
Bang-Jensen, J., Gabow, H.N., Jordán, T., and Szigeti, Z. [1999]: Edge-connectivity augmentation with partition constraints. SIAM Journal on Discrete Mathematics 12 (1999), 160–207CrossRefGoogle Scholar
Bansal, N., Blum, A., Chawla, S., and Meyerson, A. [2004]: Approximation algorithms for deadline-TSP and vehicle routing with time-windows. Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), 166–174CrossRefGoogle Scholar
Barahona, F., and Conforti, M. [1987]: A construction for binary matroids. Discrete Mathematics 66 (1987), 213–218CrossRefGoogle Scholar
Bartal, Y., and Gottlieb, L.-A. [2013]: A linear time approximation scheme for Euclidean TSP. Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), 698–706CrossRefGoogle Scholar
Bartal, Y., Gottlieb, L.-A., and Krauthgamer, R. [2016]: The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme. SIAM Journal on Computing 45 (2016), 1563–1581CrossRefGoogle Scholar
Bateni, M., and Chuzhoy, J. [2013]: Approximation algorithms for the directed k-tour and k-stroll problems. Algorithmica 65 (2013), 545–561CrossRefGoogle Scholar
Beideman, C., Chandrasekaran, K., and Wang, W. [2023]: Approximate minimum cuts and their enumeration. Proceedings of the 6th Symposium on Simplicity in Algorithms (SOSA 2023), 36–41CrossRefGoogle Scholar
Bellman, R. [1962]: Dynamic programming treatment of the travelling salesman problem. Journal of the ACM 9 (1962), 61–63CrossRefGoogle Scholar
Benczúr, A.A. [1995]: A representation of cuts within 6/5 times the edge connectivity with applications. Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1995), 92–102CrossRefGoogle Scholar
Benczúr, A.A., and Goemans, M.X. [2008]: Deformable polygon representation and near-mincuts. In: Building Bridges: Between Mathematics and Computer Science (Grötschel, M. and Katona, G.O.H., eds.), Bolyai Society Mathematical Studies 19, Budapest, and Springer, Berlin 2008, pp. 103–135CrossRefGoogle Scholar
Bender, M.A., and Chekuri, C. [2000]: Performance guarantees for the TSP with a parameterized triangle inequality. Information Processing Letters 73 (2000), 17–21CrossRefGoogle Scholar
Benoit, G., and Boyd, S. [2008]: Finding the exact integrality gap for small traveling salesman problems. Mathematics of Operations Research 33 (2008), 921–931CrossRefGoogle Scholar
Bérczi, K., Mnich, M., and Vincze, R. [2022]: A 3/2-approximation for the metric many-visits path TSP. SIAM Journal on Discrete Mathematics 36 (2022), 2995–3030CrossRefGoogle Scholar
Berman, P., and Karpinski, M. [2006]: 8/7-approximation algorithm for (1,2)-TSP. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), 641–648CrossRefGoogle Scholar
van Bevern, R., and Slugina, V.A. [2020]: A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem. Historia Mathematica 53 (2020), 118–127CrossRefGoogle Scholar
Bienstock, D., Goemans, M.X., Simchi-Levi, D., and Williamson, D. [1993]: A note on the prize collecting traveling salesman problem. Mathematical Programming 39 (1993), 413–420CrossRefGoogle Scholar
Bläser, M. [2008]: A new approximation algorithm for the asymmetric TSP with triangle inequality. ACM Transactions on Algorithms 4 (2008), Article 47CrossRefGoogle Scholar
Blauth, J., Held, S., Müller, D., Schlomberg, N., Traub, V., Tröbst, T., and Vygen, J. [2022]: Vehicle routing with time-dependent travel times: theory, practice, and benchmarks. arXiv:2205.00889Google Scholar
Blauth, J., Klein, N., and Nägele, M. [2023]: A better-than-1.6-approximation for Prize-Collecting TSP. arXiv:2308.06254. To appear in IPCO 2024CrossRefGoogle Scholar
Blauth, J., and Nägele, M. [2023]: An improved approximation guarantee for Prize-Collecting TSP. Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), 1848–1861CrossRefGoogle Scholar
Blauth, J., Neuwohner, M., Puhlmann, L., and Vygen, J. [2023]: Improved guarantees for the a priori TSP. Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), Article 14Google Scholar
Blauth, J., Traub, V., and Vygen, J. [2023]: Improving the approximation ratio for capacitated vehicle routing. Mathematical Programming 197 (2023), 451–497CrossRefGoogle Scholar
Blum, A., Chawla, S., Karger, D.R., Lane, T., Meyerson, A., and Minkoff, M. [2007]: Approximation algorithms for orienteering and discounted-reward TSP. SIAM Journal on Computing 37 (2007), 653–670CrossRefGoogle Scholar
Blum, A., Ravi, R., and Vempala, S. [1999]: A constant-factor approximation for the k-MST problem. Journal of Computer and System Sciences 58 (1999), 101–108CrossRefGoogle Scholar
Bock, F.C. [1971]: An algorithm to construct a minimum directed spanning tree in a directed network. In: Developments in Operations Research, Volume I (Avi-Itzhak, B., ed.), Gordon and Breach, New York 1971, pp. 29–44Google Scholar
Borcea, J., Brändén, P., and Liggett, T. [2009]: Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society 22 (2009), 521–567CrossRefGoogle Scholar
Borradaile, G., Le, H., and Wulff-Nilsen, C. [2017]: Minor-free graphs have light spanners. Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), 767–778CrossRefGoogle Scholar
Borůvka, O. [1926]: O jistém problému minimálním. Práca Moravské Pr̆írodovĕdecké Spolec̆nosti 3 (1926), 37–58 [in Czech]Google Scholar
Bosch-Calvo, M., Grandoni, F., and Jabal Ameli, A. [2023]: A 4/3 approximation for 2-vertex-connectivity. Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), Article 29Google Scholar
Boyd, S., and Carr, R. [2011]: Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. Discrete Optimization 8 (2011), 525–539CrossRefGoogle Scholar
Boyd, S., and Elliott-Magwood, P. [2005]: Computing the integrality gap of the asymmetric traveling salesman problem. Electronic Notes in Discrete Mathematics 19 (2005), 241–247CrossRefGoogle Scholar
Boyd, S., and Elliott-Magwood, P. [2010]: Structure of the extreme points of the subtour elimination polytope of the STSP. RIMS Kôkyûroku Bessatsu B23 (2010), 33–47Google Scholar
Boyd, S., Fu, Y., and Sun, Y. [2016]: A -approximation for subcubic 2EC using circulations and obliged edges. Discrete Applied Mathematics 209 (2016), 48–58CrossRefGoogle Scholar
Boyd, S.C., and Pulleyblank, W.R. [1991]: Optimizing over the subtour polytope of the travelling salesman problem. Mathematical Programming 49 (1991), 163–187CrossRefGoogle Scholar
Boyd, S., and Sebő, A. [2021]: The salesman’s improved tours for fundamental classes. Mathematical Programming 186 (2021), 289–307CrossRefGoogle Scholar
Boyd, S., Sitters, R., van der Ster, S., and Stougie, L. [2014]: The traveling salesman problem on cubic and subcubic graphs. Mathematical Programming 144 (2014), 227–245CrossRefGoogle Scholar
van den Brand, J., Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., Sachdeva, S., and Sidford, A. [2023]: A deterministic almost-linear time algorithm for minimum-cost flow. Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023), 503–514CrossRefGoogle Scholar
Brooks, R.L., Smith, C.A.B., Stone, A.H., and Tutte, W.T. [1940]: The dissection of rectangles into squares. Duke Mathematical Journal 7 (1940), 312–340CrossRefGoogle Scholar
Calinescu, G., Chekuri, C., Pál, M., and Vondrák, J. [2011]: Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing 40 (2011), 1740–1766CrossRefGoogle Scholar
Carathéodory, C. [1911]: Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen. Rendiconto del Circolo Matematico di Palermo 32 (1911), 193–217 [in German]CrossRefGoogle Scholar
Carr, R., and Ravi, R. [1998]: A new bound for the 2-edge connected subgraph problem. Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization (IPCO 1998), 112–125CrossRefGoogle Scholar
Carr, R., and Vempala, S. [2004]: On the Held–Karp relaxation for the asymmetric and symmetric traveling salesman problems. Mathematical Programming 100 (2004), 569–587CrossRefGoogle Scholar
Cen, R., Li, J., and Panigrahi, D. [2022]: Edge connectivity augmentation in near-linear time. Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022), 137–150CrossRefGoogle Scholar
Chalasani, P., Motwani, R., and Rao, A. [1997]: Algorithms for robot grasp and delivery. Proceedings of the 2nd International Workshop on Algorithmic Foundations of Robotics (WAFR 1997), 347–362Google Scholar
Charikar, M., Goemans, M.X., and Karloff, H. [2006]: On the integrality ratio for the asymmetric traveling salesman problem. Mathematics of Operations Research 31 (2006), 245–252CrossRefGoogle Scholar
Chaudhuri, K., Godfrey, B., Rao, S., and Talwar, K. [2003]: Paths, trees, and minimum latency tours. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), 36–45CrossRefGoogle Scholar
Chekuri, C., Korula, N., and Pál, M. [2012]: Improved algorithms for orienteering and related problems. ACM Transactions on Algorithms 8 (2012), Article 23CrossRefGoogle Scholar
Chekuri, C., and Pál, M. [2007]: An O (log n) approximation ratio for the asymmetric traveling salesman path problem. Theory of Computing 3 (2007), 197–209CrossRefGoogle Scholar
Chekuri, C., and Quanrud, K. [2017]: Approximating the Held–Karp bound for metric TSP in nearly-linear time. Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), 789–800CrossRefGoogle Scholar
Chekuri, C., and Quanrud, K. [2018]: Faster approximations for Metric-TSP via linear programming. arXiv:1802.01242Google Scholar
Chekuri, C., Quanrud, K., and Torres, M.R. [2021]: Fast approximation algorithms for bounded degree and crossing spanning tree problems. Proceedings of the 24th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2021), Article 24Google Scholar
Chekuri, C., Quanrud, K., and Xu, C. [2020]: LP relaxation and tree packing for minimum k-cut. SIAM Journal on Discrete Mathematics 34 (2020), 1334–1353CrossRefGoogle Scholar
Chekuri, C., Vondrák, J., and Zenklusen, R. [2010]: Dependent randomized rounding via exchange properties of combinatorial structures. Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), 575–584CrossRefGoogle Scholar
Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., and Sachdeva, S. [2022]: Maximum flow and minimum-cost flow in almost-linear time. Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022), 612–623CrossRefGoogle Scholar
Cheriyan, J., Friggstad, Z., and Gao, Z. [2015]: Approximating minimum-cost connected T-joins. Algorithmica 72 (2015), 126–147CrossRefGoogle Scholar
Cheriyan, J., Karloff, H., Khandekar, R., and Könemann, J. [2008]: On the integrality ratio for tree augmentation. Operations Research Letters 36 (2008), 399–401CrossRefGoogle Scholar
Cheriyan, J., Sebő, A., and Szigeti, Z. [2001]: Improving on the 1.5-approximation of a smallest 2-edge connected spanning subgraph. SIAM Journal on Discrete Mathematics 14 (2001), 170–180CrossRefGoogle Scholar
Chernoff, H. [1952]: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics 23 (1952), 493–507CrossRefGoogle Scholar
Chiplunkar, A., and Vishwanathan, S. [2015]: Approximating the regular graphic TSP in near linear time. Proceedings of the 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015), 125–135Google Scholar
Christofides, N. [1976]: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh 1976 [reprinted in Operations Research Forum 3 (2022), Article 20]CrossRefGoogle Scholar
Cook, W.J. [2012]: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton 2012Google Scholar
Cornuéjols, G., Fonlupt, J., and Naddef, D. [1985]: The traveling salesman problem on a graph and some related integer polyhedra. Mathematical Programming 33 (1985), 1–27CrossRefGoogle Scholar
Correa, J., Larré, O., and Soto, J.A. [2015]: TSP tours in cubic graphs: Beyond 4/3. SIAM Journal on Discrete Mathematics 29 (2015), 915–939CrossRefGoogle Scholar
Cunningham, W.H. [1984]: Testing membership in matroid polyhedra. Journal of Combinatorial Theory B 36 (1984), 161–188CrossRefGoogle Scholar
Czeller, I., and Pap, G. [2014]: A note on bounded weighted graphic metric TSP. Technical Report No. 2014-03, EGRES, Budapest 2014Google Scholar
Dadush, D., Végh, L.A., and Zambelli, G. [2021]: Geometric rescaling algorithms for submodular function minimization. Mathematics of Operations Research 46 (2021), 1081–1108CrossRefGoogle Scholar
Dantzig, G.B., and Fulkerson, D.R. [1956]: On the max-flow min-cut theorem of networks. In: Linear Inequalities and Related Systems (Kuhn, H.W. and Tucker, A.W., eds.), Princeton University Press, Princeton 1956, pp. 215–221Google Scholar
Dantzig, G.B., Fulkerson, D.R., and Johnson, S.M. [1954]: Solution of a large scale traveling salesman problem. Operations Research 2 (1954), 393–410Google Scholar
Demaine, E.D., Hajiaghayi, M., and Kawarabayashi, K. [2011]: Contraction decomposition in H-minor free graphs and algorithmic applications. Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011), 441 – 450CrossRefGoogle Scholar
Demaine, E.D., Hajiaghayi, M., and Mohar, B. [2010]: Approximation algorithms via contraction decomposition. Combinatorica 30 (2010), 533–552CrossRefGoogle Scholar
Dijkstra, E.W. [1959]: A note on two problems in connexion with graphs. Numerische Mathematik 1 (1959), 269–271CrossRefGoogle Scholar
Dinits, E., Karzanov, A.V., and Lomonosov, M.V. [1976]: On the structure of a family of minimal weighed cuts in a graph. In: Studies in Discrete Optimization (Fridman, A.A., ed.), Nauka, Moscow 1976, pp. 290–306 [in Russian]Google Scholar
Disser, Y., Feldmann, A.E., Klimm, M., and Könemann, J. [2021]: Travelling on graphs with small highway dimension. Algorithmica 83 (2021), 1352–1370CrossRefGoogle Scholar
Drees, M. [2022]: Simplifying the Karlin–Klein–Oveis Gharan analysis for -approximating TSP. Master’s thesis, University of Bonn, 2022Google Scholar
Duník, B., and Lukot’ka, R. [2018]: Cubic TSP: A 1.3-approximation. SIAM Journal on Discrete Mathematics 32 (2018), 2094–2114CrossRefGoogle Scholar
Dvor̆ák, Z., Král’, D., and Mohar, B. [2017]: Graphic TSP in cubic graphs. Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Article 27Google Scholar
Edmonds, J. [1965a]: Paths, trees, and flowers. Canadian Journal of Mathematics 17 (1965), 449–467CrossRefGoogle Scholar
Edmonds, J. [1965b]: Maximum matching and a polyhedron with (0,1) vertices. Journal of Research of the National Bureau of Standards B 69 (1965), 125–130CrossRefGoogle Scholar
Edmonds, J. [1967a]: Optimum branchings. Journal of Research of the National Bureau of Standards B 71 (1967), 233–240CrossRefGoogle Scholar
Edmonds, J. [1967b]: Systems of distinct representatives and linear algebra. Journal of Research of the National Bureau of Standards B 71 (1967), 241–245CrossRefGoogle Scholar
Edmonds, J. [1970]: Submodular functions, matroids and certain polyhedra. In: Combinatorial Structures and Their Applications; Proceedings of the Calgary International Conference on Combinatorial Structures and Their Applications 1969 (R. Guy, H. Hanani, N. Sauer, and Schönheim, J., eds.), Gordon and Breach, New York 1970, pp. 69–87Google Scholar
Edmonds, J. [1973]: Edge-disjoint branchings. In: Combinatorial Algorithms (Rustin, R., ed.), Algorithmic Press, New York 1973, pp. 91–96Google Scholar
Edmonds, J. [1975]: Some well-solved problems in combinatorial optimization. In: Combinatorial Programming: Methods and Applications (Roy, B., ed.), Reidel, Dordrecht 1975, pp. 285–301CrossRefGoogle Scholar
Edmonds, J., and Johnson, E.L. [1973]: Matching, Euler tours and the Chinese postman. Mathematical Programming 5 (1973), 88–124CrossRefGoogle Scholar
Edmonds, J., and Karp, R.M. [1972]: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19 (1972), 248–264CrossRefGoogle Scholar
van Ee, M., and Sitters, R. [2018]: The a priori traveling repairman problem. Algorithmica 80 (2018), 2818–2833CrossRefGoogle Scholar
Euler, L. [1736]: Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Petropolitanae 8 (1736), 128–140 [in Latin]Google Scholar
Feder, T., and Mihail, M. [1992]: Balanced matroids. Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC 1992), 26–38CrossRefGoogle Scholar
Feige, U., Ravi, R., and Singh, M. [2014]: Short tours through large linear forests. Proceedings of the 17th Conference on Integer Programming and Combinatorial Optimization (IPCO 2014), 273–284CrossRefGoogle Scholar
Feige, U., and Singh, M. [2007]: Improved approximation algorithms for traveling salesperson tours and paths in directed graphs. Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2007), 104–118CrossRefGoogle Scholar
Fernandes, C.G. [1998]: A better approximation ratio for the minimum size k-edge-connected spanning subgraph problem. Journal of Algorithms 28 (1998), 105–124CrossRefGoogle Scholar
Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., and de Wolf, R. [2015]: Exponential lower bounds for polytopes in combinatorial optimization. Journal of the ACM 62 (2015), Article 17Google Scholar
Fleiner, T., and Frank, A. [2009]: A quick proof for the cactus representation of mincuts. EGRES Quick Proof No. 2009-03, Budapest 2009Google Scholar
Ford, L.R. Jr., and Fulkerson, D.R. [1956]: Maximal flow through a network. Canadian Journal of Mathematics 8 (1956) 399–404CrossRefGoogle Scholar
Frank, A. [1989]: On connectivity properties of Eulerian digraphs. Annals of Discrete Mathematics 41 (1989), 179–194CrossRefGoogle Scholar
Frank, A. [1993]: Conservative weightings and ear-decompositions of graphs. Combinatorica 13 (1993), 65–81CrossRefGoogle Scholar
Frank, A. [1994]: On the edge-connectivity algorithm of Nagamochi and Ibaraki. Laboratoire Artemis, IMAG, Université J. Fourier, Grenoble 1994Google Scholar
Frank, A. [2011]: Connections in Combinatorial Optimization. Oxford University Press 2011Google Scholar
Frank, A., and Tardos, É. [1987]: An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7 (1987), 49–65CrossRefGoogle Scholar
Frank, A., Triesch, E., Korte, B., and Vygen, J. [1998]: On the bipartite travelling salesman problem. Report No. 98866, Research Institute for Discrete Mathematics, University of Bonn, 1998Google Scholar
Frederickson, G.N. [1979]: Approximation algorithms for some postman problems. Journal of the ACM 26 (1979), 538–554CrossRefGoogle Scholar
Frederickson, G.N., and Ja’ja’, J. [1982]: On the relationship between the biconnectivity augmentation and travelling salesman problems. Theoretical Computer Science 19 (1982), 189–201CrossRefGoogle Scholar
Frieze, A.M., Galbiati, G., and Maffioli, F. [1982]: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12 (1982), 23–39CrossRefGoogle Scholar
Friggstad, Z., Gupta, A., and Singh, M. [2016]: An improved integrality gap for asymmetric TSP paths. Mathematics of Operations Research 41 (2016), 745–757CrossRefGoogle Scholar
Friggstad, Z., Mousavi, R., Rahgoshay, M., and Salavatipour, M.R. [2022]: Improved approximations for capacitated vehicle routing with unsplittable client demands. Proceedings of the 23rd Conference on Integer Programming and Combinatorial Optimization (IPCO 2022), 251–261CrossRefGoogle Scholar
Friggstad, Z., Salavatipour, M.R., and Svitkina, Z. [2013]: Asymmetric traveling salesman path and directed latency problems. SIAM Journal on Computing 42 (2013), 1596–1619CrossRefGoogle Scholar
Friggstad, Z., and Swamy, C. [2022]: A constant-factor approximation for directed latency in quasi-polynomial time. Journal of Computer and System Sciences 126 (2022), 44–58CrossRefGoogle Scholar
Fulkerson, D.R. [1974]: Packing rooted directed cuts in a weighted directed graph. Mathematical Programming 6 (1974), 1–13CrossRefGoogle Scholar
Gabow, H.N. [1973]: Implementations of algorithms for maximum matching on nonbipartite graphs. Ph.D. thesis, Stanford University, 1973Google Scholar
Gale, D., Kuhn, H.W., and Tucker, A.W. [1951]: Linear programming and the theory of games. In: Activity Analysis of Production and Allocation (Koopmans, T.C., ed.), Wiley, New York 1951, pp. 317–329Google Scholar
Gallai, T. [1964]: Maximale Systeme unabhängiger Kanten. Magyar Tudományos Akadémia; Matematikai Kutató Intézetének Közleményei 9 (1964), 401–413Google Scholar
Gamarnik, D., Lewenstein, M., and Sviridenko, M. [2005]: An improved upper bound for the TSP in cubic 3-edge-connected graphs. Operations Research Letters 33 (2005), 467–474CrossRefGoogle Scholar
Ganesh, A., Maggs, B.M., and Panigrahi, D. [2023]: Robust algorithms for TSP and Steiner tree. ACM Transactions on Algorithms 19 (2023), Article 12CrossRefGoogle Scholar
Gao, Z. [2013]: An LP-based -approximation algorithm for the s-t path graph traveling salesman problem. Operations Research Letters 41 (2013), 615–617CrossRefGoogle Scholar
Gao, Z. [2015]: On the metric s-t path traveling salesman problem. SIAM Journal on Discrete Mathematics 29 (2015), 1133–1149CrossRefGoogle Scholar
Garg, M., Grandoni, F., and Jabal Ameli, A. [2023]: Improved approximation for two-edge-connectivity. Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), 2368–2410CrossRefGoogle Scholar
Garg, N. [2005]: Saving an epsilon: A 2-approximation for the k-MST problem in graphs. Proceedings of the 37th Annual ACM Symposium on the Theory of Computing (STOC 2005), 396–402CrossRefGoogle Scholar
Gendreau, M., Laporte, G., and Hertz, A. [1997]: An approximation algorithm for the traveling salesman problem with backhauls. Operations Research 45 (1997), 639–641CrossRefGoogle Scholar
Genova, K., and Williamson, D.P. [2017]: An experimental evaluation of the Best-of-Many Christofides’ algorithm for the traveling salesman problem. Algorithmica 78 (2017), 1109–1130CrossRefGoogle Scholar
Goddyn, L.A. [undated]: Some open problems I like. https://www.sfu.ca/~goddyn/Problems/problems.html (last checked on November 6, 2023)Google Scholar
Goemans, M.X. [1995]: Worst-case comparison of valid inequalities for the TSP. Mathematical Programming 69 (1995), 335–349CrossRefGoogle Scholar
Goemans, M.X. [2006]: Minimum bounded-degree spanning trees. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 273–282CrossRefGoogle Scholar
Goemans, M.X. [2009]: Combining approximation algorithms for the prize-collecting TSP. arXiv:0910.0553Google Scholar
Goemans, M.X. [2012]: Thinness spurs progress. OPTIMA 90 (2012), 12–14Google Scholar
Goemans, M.X., and Bertsimas, D.J. [1993]: Survivable networks, linear programming relaxations and the parsimonious property. Mathematical Programming 60 (1993), 145–166CrossRefGoogle Scholar
Goemans, M.X., Harvey, N.J.A., Jain, K., and Singh, M. [2009]: A randomized rounding algorithm for the asymmetric traveling salesman problem. arXiv:0909.0941Google Scholar
Goemans, M.X., and Ramakrishnan, V.S. [1995]: Minimizing submodular functions over families of sets. Combinatorica 15 (1995), 499–513CrossRefGoogle Scholar
Goemans, M.X., and Williamson, D.P. [1995]: A general approximation technique for constrained forest problems. SIAM Journal on Computing 24 (1995), 296–317CrossRefGoogle Scholar
Gottschalk, C. [2013]: Approximation algorithms for the traveling salesman problem in graphs and digraphs. Master’s thesis, University of Bonn, 2013Google Scholar
Gottschalk, C., and Vygen, J. [2018]: Better s-t-tours by Gao trees. Mathematical Programming 172 (2018), 191–207CrossRefGoogle Scholar
Grötschel, M., Lovász, L., and Schrijver, A. [1981]: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 (1981), 169–197CrossRefGoogle Scholar
Grötschel, M., Lovász, L., and Schrijver, A. [1988]: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin 1988CrossRefGoogle Scholar
Guan, M. [1962]: Graphic programming using odd or even points. Chinese Mathematics 1 (1962), 273–277Google Scholar
Gupta, A., Lee, E., Li, J., Mucha, M., Newman, H., and Sarkar, S. [2022]: Matroid-based TSP rounding for half-integral solutions. Proceedings of the 23rd Conference on Integer Programming and Combinatorial Optimization (IPCO 2022), 305–318CrossRefGoogle Scholar
Gurvits, L., Klein, N., and Leake, J. [2023]: From trees to polynomials and back again: New capacity bounds with applications to TSP. arXiv:2311.09072Google Scholar
Gutin, G., and Punnen, A.P., eds. [2002]: The Traveling Salesman Problem and Its Variations. Kluwer, Dordrecht 2002Google Scholar
Guttmann-Beck, N., Knaan, E., and Stern, M. [2018]: Approximation algorithms for not necessarily disjoint clustered TSP. Journal on Graph Algorithms and Applications 22 (2018), 555–575CrossRefGoogle Scholar
Haddadan, A., and Newman, A. [2023]: Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours. Mathematical Programming 198 (2023), 595–620CrossRefGoogle Scholar
Haddadan, A., Newman, A., and Ravi, R. [2021]: Shorter tours and longer detours: Uniform covers and a bit beyond. Mathematical Programming 185 (2021), 245–273CrossRefGoogle Scholar
Haimovich, M., and Rinnooy Kan, A.H.G. [1985]: Bounds and heuristics for capacitated routing problems. Mathematics of Operations Research 10 (1985), 527–542CrossRefGoogle Scholar
Hall, P. [1935]: On representatives of subsets. Journal of the London Mathematical Society 10 (1935), 26–30CrossRefGoogle Scholar
Heeger, K., and Vygen, J. [2017]: Two-connected spanning subgraphs with at most OPT edges. SIAM Journal on Discrete Mathematics 31 (2017), 1820–1835CrossRefGoogle Scholar
Held, M., and Karp, R.M. [1962]: A dynamic programming approach to sequencing problems. Journal of the Society of Industrial and Applied Mathematics 10 (1962), 196–210CrossRefGoogle Scholar
Held, M., and Karp, R.M. [1970]: The traveling-salesman problem and minimum spanning trees. Operations Research 18 (1970), 1138–1162CrossRefGoogle Scholar
Henke, D. [2018]: A linear programming relaxation with cycles for the asymmetric traveling salesman problem. Master’s thesis, University of Bonn, 2018Google Scholar
Henzinger, M., and Williamson, D.P. [1996]: On the number of small cuts in a graph. Information Processing Letters 59 (1996), 41–44CrossRefGoogle Scholar
Hierholzer, C. [1873]: Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen 6 (1873), 30–32 [in German]CrossRefGoogle Scholar
Hirai, H. [2016]: On uncrossing games for skew-supermodular functions. Journal of the Operations Research Society of Japan 59 (2016), 218–223CrossRefGoogle Scholar
Hoeffding, W. [1956]: On the distribution of the number of successes in independent trials. The Annals of Mathematical Statistics 27 (1956), 713–721CrossRefGoogle Scholar
Hoffman, A.J. [1960]: Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In: Combinatorial Analysis (Bellman, R.E. and Hall, M., eds.), AMS, Providence 1960, pp. 113–128CrossRefGoogle Scholar
Hoffman, A.J., and Kruskal, J.B. [1956]: Integral boundary points of convex polyhedra. In: Linear Inequalities and Related Systems; Annals of Mathematical Study 38 (Kuhn, H.W. and Tucker, A.W., eds.), Princeton University Press, Princeton 1956, pp. 223–246Google Scholar
Hoogeveen, J.A. [1991]: Analysis of Christofides’ heuristic: some paths are more difficult than cycles. Operations Research Letters 10 (1991), 291–295CrossRefGoogle Scholar
Hougardy, S. [2014]: On the integrality ratio of the subtour LP for Euclidean TSP. Operations Research Letters 42 (2014), 495–499CrossRefGoogle Scholar
Hougardy, S., and Vygen, J. [2016]: Algorithmic Mathematics. Springer, Cham 2016CrossRefGoogle Scholar
Hunkenschröder, C., Vempala, S., and Vetta, A. [2019]: A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem. ACM Transactions on Algorithms 15 (2019), Article 55CrossRefGoogle Scholar
Hurkens, C.A.J., Lovász, L., Schrijver, A., and Tardos, É. [1988]: How to tidy up your set-system? In: Combinatorics (A. Hajnal, L. Lovász, and Sós, V.T., eds.), North-Holland, Amsterdam 1988, pp. 309–314Google Scholar
Iwata, S., Fleischer, L., and Fujishige, S. [2001]: A combinatorial strongly polynomial algorithm for minimizing submodular functions. Journal of the ACM 48 (2001), 761–777CrossRefGoogle Scholar
Iwata, S., and Ravi, R. [2013]: Approximating max–min weighted T-joins. Operations Research Letters 41 (2013) 321–324CrossRefGoogle Scholar
Jackson, B. [1988]: Some remarks on arc-connectivity, vertex splitting, and orientation in digraphs. Journal of Graph Theory 12 (1988), 429–436CrossRefGoogle Scholar
Jain, K. [2001]: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21 (2001), 39–60CrossRefGoogle Scholar
Jarník, V. [1930]: O jistém problému minimálním. Práca Moravské Pr̆írodovĕdecké Spolec̆nosti 6 (1930), 57–63 [in Czech]Google Scholar
Jin, B., Klein, N., and Williamson, D. [2023a]: A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP. Proceedings of the 24th Conference on Integer Programming and Combinatorial Optimization (IPCO 2023), 217–230CrossRefGoogle Scholar
Jin, B., Klein, N., and Williamson, D. [2023b]: A lower bound for the max entropy algorithm for TSP. arXiv:2311.01950. To appear in IPCO 2024CrossRefGoogle Scholar
Kaplan, H., Lewenstein, M., Shafrir, N., and Sviridenko, M. [2005]: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. Journal of the ACM 52 (2005), 602–626CrossRefGoogle Scholar
Karger, D.R. [2000]: Minimum cuts in near-linear time. Journal of the ACM 47 (2000), 46–76CrossRefGoogle Scholar
Karger, D.R., and Stein, C. [1996]: A new approach to the minimum cut problem. Journal of the ACM 43 (1996), 601–640CrossRefGoogle Scholar
Karlin, A.R., Klein, N., and Oveis Gharan, S. [2020]: An improved approximation algorithm for TSP in the half integral case. Proceedings of the 52nd Annual ACM Symposium on the Theory of Computing (STOC 2020), 28–39CrossRefGoogle Scholar
Karlin, A.R., Klein, N., and Oveis Gharan, S. [2021]: A (slightly) improved approximation algorithm for metric TSP. Proceedings of the 53rd Annual ACM Symposium on the Theory of Computing (STOC 2021), 32–45. Operations Research, to appearCrossRefGoogle Scholar
Karlin, A.R., Klein, N., and Oveis Gharan, S. [2022]: A (slightly) improved bound on the integrality gap of the subtour LP for TSP. Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022), 832–843CrossRefGoogle Scholar
Karlin, A.R., Klein, N., and Oveis Gharan, S. [2023]: A deterministic better-than-3/2 approximation algorithm for metric TSP. Proceedings of the 24th Conference on Integer Programming and Combinatorial Optimization (IPCO 2023), 261–274CrossRefGoogle Scholar
Karp, R.M. [1972]: Reducibility among combinatorial problems. In: Complexity of Computer Computations (Miller, R.E. and Thatcher, J.W., eds.), Plenum Press, New York 1972, pp. 85–103CrossRefGoogle Scholar
Karp, R.M. [1978]: A characterization of the minimum cycle mean in a digraph. Discrete Mathematics 23 (1978), 309–311CrossRefGoogle Scholar
Karpinski, M., and Schmied, R. [2015]: Approximation hardness of graphic TSP on cubic graphs. RAIRO Operations Research 49 (2015), 651–668CrossRefGoogle Scholar
Karpinski, M., Lampis, M., and Schmied, R. [2015]: New inapproximability bounds for TSP. Journal of Computer and System Sciences 81 (2015), 1665–1677CrossRefGoogle Scholar
Karzanov, A.V. [1974]: Determining a maximal flow in a network by the method of preflows. Soviet Mathematics Doklady 15 (1974), 434–437Google Scholar
Karzanov, A.V. [1996]: How to tidy up a symmetric set-system by use of uncrossing operations. Theoretical Computer Science 157 (1996), 215–225CrossRefGoogle Scholar
Khachiyan, L.G. [1979]: A polynomial algorithm in linear programming. Doklady Akademii Nauk SSSR 244 (1979) 1093–1096 [in Russian]Google Scholar
Khuller, S., and Vishkin, U. [1994]: Biconnectivity approximations and graph carvings. Journal of the ACM 41 (1994), 214–235CrossRefGoogle Scholar
Kirchhoff, G. [1847]: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. Annalen der Physik und Chemie 72 (1847), 497–508 [in German]CrossRefGoogle Scholar
Kisfaludi-Bak, S., Nederlof, J., and Węgrzycki, K. [2021]: A Gap-ETH-tight approximation scheme for Euclidean TSP. Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021), 351–362CrossRefGoogle Scholar
Klein, P.N. [2008]: A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM Journal on Computing 37 (2008), 1926–1952CrossRefGoogle Scholar
Klein, N., and Olver, N. [2023]: Thin trees for laminar families. Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023), 50–59CrossRefGoogle Scholar
Kobayashi, Y., and Noguchi, T. [2023]: An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover. arXiv:2304.13228Google Scholar
Köhne, A., Traub, V., and Vygen, J. [2020]: The asymmetric traveling salesman path LP has constant integrality ratio. Mathematical Programming 183 (2020), 379–395CrossRefGoogle Scholar
Korte, B., and Vygen, J. [2018]: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin, Sixth Edition 2018CrossRefGoogle Scholar
Kruskal, J.B. [1956]: On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the AMS 7 (1956), 48–50CrossRefGoogle Scholar
Laekhanukit, B., Oveis Gharan, S., and Singh, M. [2012]: A rounding by sampling approach to the minimum size k-arc connected subgraph problem. Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP 2012), 606–612CrossRefGoogle Scholar
Lam, F., and Newman, A. [2008]: Traveling salesman path problems. Mathematical Programming 113 (2008), 39–59CrossRefGoogle Scholar
Lampis, M. [2014]: Improved inapproximability for TSP. Theory of Computing 10 (2014), 217–236CrossRefGoogle Scholar
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. [1985]: The Traveling Salesman Problem. Wiley, Chichester 1985Google Scholar
Lee, Y.T., Sidford, A., and Wong, S.C. [2015]: A faster cutting plane method and its implications for combinatorial and convex optimization. Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), 1049–1065CrossRefGoogle Scholar
Lempel, A., Even, S., and Cederbaum, I. [1967]: An algorithm for planarity testing of graphs. In: Théorie des Graphes. Theory of Graphs (Rosenstiehl, P., ed.), Dunod, Paris 1967Google Scholar
Lin, S., and Kernighan, B.W. [1973]: An effective heuristic algorithm for the traveling-salesman problem. Operations Research 21 (1973), 498–516CrossRefGoogle Scholar
Lovász, L. [1972]: A note on factor-critical graphs. Studia Scientiarum Mathematicarum Hungarica 7 (1972), 279–280Google Scholar
Lovász, L. [1976]: On some connectivity properties of Eulerian graphs. Acta Mathematica Academiae Scientiarum Hungaricae 28 (1976), 129–138CrossRefGoogle Scholar
Lovász, L., and Plummer, M.D. [1986]: Matching Theory. Akadémiai Kiadó, Budapest, and North-Holland, Amsterdam 1986Google Scholar
Mader, W. [1982]: Konstruktion aller n-fach kantenzusammenhängenden Digraphen. European Journal of Combinatorics 3 (1982), 63–67 [in German]CrossRefGoogle Scholar
Matula, D.W., and Shahrokhi, F. [1990]: Sparsest cuts and bottlenecks in graphs. Discrete Applied Mathematics 27 (1990), 113–123CrossRefGoogle Scholar
Menger, K. [1927]: Zur allgemeinen Kurventheorie. Fundamenta Mathematicae 10 (1927), 96–115 [in German]CrossRefGoogle Scholar
Middendorf, M., and Pfeiffer, F. [1993]: On the complexity of the disjoint paths problem. Combinatorica 13 (1993), 97–107CrossRefGoogle Scholar
Minkowski, H. [1896]: Geometrie der Zahlen. Teubner, Leipzig 1896 [in German]Google Scholar
Mitchell, J. [1999]: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing 28 (1999), 1298–1309CrossRefGoogle Scholar
Mnich, M., and Mömke, T. [2018]: Improved integrality gap upper bounds for TSP with distances one and two. European Journal of Operational Research 266 (2018), 436–457CrossRefGoogle Scholar
Mömke, T. [2015]: An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality. Information Processing Letters 115 (2015), 866–871CrossRefGoogle Scholar
Mömke, T., and Svensson, O. [2016]: Removing and adding edges for the traveling salesman problem. Journal of the ACM 63 (2016), Article 2CrossRefGoogle Scholar
Monma, C.L., Munson, B.S., and Pulleyblank, W.R. [1990]: Minimum-weight two-connected spanning networks. Mathematical Programming 46 (1990), 153–171CrossRefGoogle Scholar
Mucha, M. [2014]: -approximation for graphic TSP. Theory of Computing Systems 55 (2014), 640–657CrossRefGoogle Scholar
Nagamochi, H., and Ibaraki, T. [1992]: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics 5 (1992), 54–66CrossRefGoogle Scholar
Nagamochi, H., Nishimura, K., and Ibaraki, T. [1997]: Computing all small cuts in an undirected network. SIAM Journal on Discrete Mathematics 10 (1997), 469–481CrossRefGoogle Scholar
Nagarajan, V., and Ravi, R. [2008]: The directed minimum latency problem. Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008), 193–206CrossRefGoogle Scholar
Nagarajan, V., and Ravi, R. [2011]: The directed orienteering problem. Algorithmica 60 (2011), 1017–1030CrossRefGoogle Scholar
Nash-Williams, C.S.J.A. [1961]: Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society 36 (1961), 445–450CrossRefGoogle Scholar
von Neumann, J. [1947]: Discussion of a maximum problem. Working paper, Princeton 1947 [published in: John von Neumann, Collected Works; Vol. VI (Taub, A.H., ed.), Pergamon Press, Oxford 1963, pp. 27–28]Google Scholar
Newman, A. [2020]: An improved analysis of the Mömke–Svensson algorithm for graph-TSP on subquartic graphs. SIAM Journal on Discrete Mathematics 34 (2020), 865–884CrossRefGoogle Scholar
Orlin, J.B. [1993]: A faster strongly polynomial minimum cost flow algorithm. Operations Research 41 (1993), 338–350CrossRefGoogle Scholar
Oveis Gharan, S., and Saberi, A. [2011]: The asymmetric traveling salesman problem on graphs with bounded genus. Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), 967–975CrossRefGoogle Scholar
Oveis Gharan, S., Saberi, A., and Singh, M. [2011]: A randomized rounding approach to the traveling salesman problem. Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), 550–559CrossRefGoogle Scholar
Padberg, M.W., and Rao, M.R. [1982]: Odd minimum cut-sets and b-matchings. Mathematics of Operations Research 7 (1982), 67–80CrossRefGoogle Scholar
Panconesi, A., and Srinivasan, A. [1997]: Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds. SIAM Journal on Computing 26 (1997), 350–368CrossRefGoogle Scholar
Papadimitriou, C.H., and Vempala, S. [2006]: On the approximability of the traveling salesman problem. Combinatorica 26 (2006), 101–120CrossRefGoogle Scholar
Papadimitriou, C.H., and Yannakakis, M. [1993]: The traveling salesman problem with distances one and two. Mathematics of Operations Research 18 (1993), 1–12CrossRefGoogle Scholar
Pillai, A., and Singh, M. [2023]: Linear programming based reductions for Multiple Visit TSP and vehicle routing problems. arXiv:2308.11742Google Scholar
Prim, R.C. [1957]: Shortest connection networks and some generalizations. Bell System Technical Journal 36 (1957), 1389–1401CrossRefGoogle Scholar
Pritchard, D. [2010]: k-edge-connectivity: approximation and LP relaxation. Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA 2010). 225–236CrossRefGoogle Scholar
Qian, J., Schalekamp, F., Williamson, D.P., and van Zuylen, A. [2015]: On the integrality gap of the subtour LP for the 1,2-TSP. Mathematical Programming 150 (2015), 131–151CrossRefGoogle Scholar
Rado, R. [1942]: A theorem on independence relations. Quarterly Journal of Mathematics 13 (1942), 83–89CrossRefGoogle Scholar
Rao, S.B., and Smith, W.D. [1998]: Approximating geometric graphs via “spanners” and “banyans.” Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998), 540–550CrossRefGoogle Scholar
Rayleigh, J.W.S. [1871]: On the theory of resonance. Philosophical Transactions 161 (1871), 77–118Google Scholar
Robertson, N., and Seymour, P.D. [1995]: Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory B 63 (1995), 65–110CrossRefGoogle Scholar
Rosenkrantz, D.J., Stearns, R.E., and Lewis, P.M. II [1977]: An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing 6 (1977), 563–581CrossRefGoogle Scholar
Sahni, S., and Gonzalez, T. [1976]: P-complete approximation problems. Journal of the ACM 23 (1976), 555–565CrossRefGoogle Scholar
Saller, S., Koehler, J., and Karrenbauer, A. [2023]: A systematic review of approximability results for traveling salesman problems leveraging the TSP-T3CO definition scheme. arXiv:2311.00604Google Scholar
Schalekamp, F., Sebő, A., Traub, V., and van Zuylen, A. [2018]: Layers and matroids for the traveling salesman’s paths. Operations Research Letters 46 (2018), 60–63CrossRefGoogle Scholar
Schalekamp, F., Williamson, D.P., and van Zuylen, A. [2014]: 2-matchings, the traveling salesman problem, and the subtour LP: A proof of the Boyd–Carr conjecture. Mathematics of Operations Research 39 (2014), 403–417CrossRefGoogle Scholar
Schrijver, A. [2000]: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory B 80 (2000), 346–355CrossRefGoogle Scholar
Schrijver, A. [2003]: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin 2003Google Scholar
Sebő, A. [1987]: A quick proof of Seymour’s theorem on T-joins. Discrete Mathematics 64 (1987), 101–103CrossRefGoogle Scholar
Sebő, A. [1997]: Potentials in undirected graphs and planar multiflows. SIAM Journal on Computing 26 (1997), 582–603CrossRefGoogle Scholar
Sebő, A. [2013]: Eight-fifth approximation for TSP paths. Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO 2013), 362–374CrossRefGoogle Scholar
Sebő, A., and Vygen, J. [2014]: Shorter tours by nicer ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica 34 (2014), 597–629CrossRefGoogle Scholar
Sebő, A., and van Zuylen, A. [2019]: The salesman’s improved paths through forests. Journal of the ACM 66 (2019), Article 28CrossRefGoogle Scholar
Serdyukov, A.I. [1978]: Some extremal bypasses in graphs. Upravlyaemye Sistemy 17 (1978), 76–79 [in Russian]Google Scholar
Shmoys, D., and Talwar, K. [2008] A constant approximation algorithm for the a priori traveling salesman problem. Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008), 331–343CrossRefGoogle Scholar
Shmoys, D., and Williamson, D. P. [1990]: Analyzing the Held–Karp TSP bound: A monotonicity property with application. Information Processing Letters 35 (1990), 281–285CrossRefGoogle Scholar
Singh, M., and Vishnoi, N.K. [2014]: Entropy, optimization and counting. Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), 50–59CrossRefGoogle Scholar
Spielman, D.A., and Teng, S.-H. [2014]: Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications 35 (2014), 835–885CrossRefGoogle Scholar
Steinitz, E. [1916]: Bedingt konvergente Reihen und konvexe Systeme. Journal für die reine und angewandte Mathematik 146 (1916), 1–52 [in German]CrossRefGoogle Scholar
Stoer, M., and Wagner, F. [1997]: A simple min cut algorithm. Journal of the ACM 44 (1997), 585–591CrossRefGoogle Scholar
Straszak, D., and Vishnoi, N.K. [2019]: Maximum entropy distributions: Bit complexity and stability. Proceedings of the 32nd Conference on Learning Theory (COLT 2019), 2861–2891Google Scholar
Svensson, O. [2013]: Overview of new approaches for approximating TSP. Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), 5–11CrossRefGoogle Scholar
Svensson, O. [2015]: Approximating ATSP by relaxing connectivity. Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), 1–19CrossRefGoogle Scholar
Svensson, O., Tarnawski, J., and Végh, L. [2018]: Constant factor approximation for ATSP with two edge weights. Mathematical Programming 172 (2018), 371–397CrossRefGoogle Scholar
Svensson, O., Tarnawski, J., and Végh, L. [2020]: A constant-factor approximation algorithm for the asymmetric traveling salesman problem. Journal of the ACM 67 (2020), Article 37CrossRefGoogle Scholar
Tardos, É. [1985]: A strongly polynomial minimum cost circulation algorithm. Combinatorica 5 (1985), 247–255CrossRefGoogle Scholar
Tardos, É. [1986]: A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research 34 (1986), 250–256CrossRefGoogle Scholar
Toth, P., and Vigo, D., eds. [2014]: Vehicle Routing: Problems, Methods, and Applications. MOS-SIAM Series on Optimization, Philadelphia, Second Edition 2014Google Scholar
Traub, V. [2017]: Approximating the s-t-path TSP. Master’s thesis, University of Bonn, 2017Google Scholar
Traub, V. [2020a]: Approximation algorithms for traveling salesman problems. PhD thesis, University of Bonn, 2020Google Scholar
Traub, V. [2020b]: Improving on Best-of-Many-Christofides for T-tours. Operations Research Letters 48 (2020), 798–804CrossRefGoogle Scholar
Traub, V., and Vygen, J. [2019a]: Approaching for the s-t-path TSP. Journal of the ACM 66 (2019), Article 14CrossRefGoogle Scholar
Traub, V., and Vygen, J. [2019b]: An improved upper bound on the integrality ratio for the s-t-path TSP. Operations Research Letters 47 (2019), 225–228CrossRefGoogle Scholar
Traub, V., and Vygen, J. [2022]: An improved approximation algorithm for the asymmetric traveling salesman problem. SIAM Journal on Computing 51 (2022), 139–173CrossRefGoogle Scholar
Traub, V., and Vygen, J. [2023]: Beating the integrality ratio for s-t-tours in graphs. SIAM Journal on Computing 52 (2023), FOCS18-37–FOCS18-84CrossRefGoogle Scholar
Traub, V., Vygen, J., and Zenklusen, R. [2022]: Reducing Path TSP to TSP. SIAM Journal on Computing 51 (2022), STOC20-24–STOC-20-53CrossRefGoogle Scholar
Traub, V., and Zenklusen, R. [2021]: A better-than-2 approximation for weighted tree augmentation. Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021), 1–12CrossRefGoogle Scholar
Traub, V., and Zenklusen, R. [2022]: Local search for weighted tree augmentation and Steiner tree. Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), 3253–3271CrossRefGoogle Scholar
Tutte, W.T. [1961]: On the problem of decomposing a graph into n connected factors. Journal of the London Mathematical Society 36 (1961), 221–230CrossRefGoogle Scholar
Vazirani, V.V., and Yannakakis, M. [1992]: Suboptimal cuts: Their enumeration, weight and number. Proceedings of the 19th International Colloquium on Automata, Languages, and Programming (ICALP 1992), 366–377CrossRefGoogle Scholar
Vishnoi, N.K. [2012]: A permanent approach to the traveling salesman problem. Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), 76–80CrossRefGoogle Scholar
Vygen, J. [2012]: New approximation algorithms for the TSP. OPTIMA 90 (2012), 1–12Google Scholar
Vygen, J. [2016]: Reassembling trees for the traveling salesman. SIAM Journal on Discrete Mathematics 30 (2016), 875–894CrossRefGoogle Scholar
Weyl, H. [1935]: Elementare Theorie der konvexen Polyeder. Commentarii Mathematici Helvetici 7 (1935), 290–306 [in German]CrossRefGoogle Scholar
Whitney, H. [1932a]: Non-separable and planar graphs. Transactions of the American Mathematical Society 34 (1932), 339–362CrossRefGoogle Scholar
Whitney, H. [1932b]: Congruent graphs and the connectivity of graphs. American Journal of Mathematics 54 (1932), 150–168CrossRefGoogle Scholar
Wigal, M.C., Yoo, Y., and Yu, X. [2023]: Approximating TSP walks in subcubic graphs. Journal of Combinatorial Theory B 158 (2023), 70–104CrossRefGoogle Scholar
Williamson, D.P. [1990]: Analysis of the Held–Karp heuristic for the traveling salesman problem. Master’s thesis, Massachusetts Institute of Technology, 1990Google Scholar
Williamson, D.P. [2019]: Network Flow Algorithms. Cambridge University Press, Cambridge 2019CrossRefGoogle Scholar
Williamson, D.P., and Shmoys, D.B. [2011]: The Design of Approximation Algorithms. Cambridge University Press, Cambridge 2011CrossRefGoogle Scholar
Wolsey, L.A. [1980]: Heuristic analysis, linear programming and branch and bound. Mathematical Programming Study 13 (1980), 121–134CrossRefGoogle Scholar
Xu, Z., and Rodrigues, B. [2015]: A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots. INFORMS Journal on Computing 27 (2015), 636–645CrossRefGoogle Scholar
Zenklusen, R. [2019]: A 1.5-approximation for path TSP. Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), 1539–1549CrossRefGoogle Scholar
Zhong, X. [2020]: Slightly improved upper bound on the integrality ratio for the s-t path TSP. Operations Research Letters 48 (2020), 627–629CrossRefGoogle Scholar
van Zuylen, A. [2011]: Deterministic sampling algorithms for network design. Algorithmica 60 (2011), 110–151CrossRefGoogle Scholar
van Zuylen, A. [2018]: Improved approximations for cubic bipartite and cubic TSP. Mathematical Programming 172 (2018), 399–413CrossRefGoogle Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • Bibliography
  • Vera Traub, University of Bonn, Jens Vygen, University of Bonn
  • Book: Approximation Algorithms for Traveling Salesman Problems
  • Online publication: 14 November 2024
  • Chapter DOI: https://doi.org/10.1017/9781009445436.020
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • Bibliography
  • Vera Traub, University of Bonn, Jens Vygen, University of Bonn
  • Book: Approximation Algorithms for Traveling Salesman Problems
  • Online publication: 14 November 2024
  • Chapter DOI: https://doi.org/10.1017/9781009445436.020
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • Bibliography
  • Vera Traub, University of Bonn, Jens Vygen, University of Bonn
  • Book: Approximation Algorithms for Traveling Salesman Problems
  • Online publication: 14 November 2024
  • Chapter DOI: https://doi.org/10.1017/9781009445436.020
Available formats
×