A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond

References

• [1] An H-C, Kleinberg R, Shmoys DB (2015) Improving Christofides’ algorithm for the s-t path TSP. J. ACM 62(5):1–28.Crossref, Google Scholar
• [2] An H-C, Kleinberg R, Shmoys D (2021) Approximation algorithms for the bottleneck asymmetric traveling salesman problem. ACM Trans. Algorithms 17(4):1–12.Crossref, Google Scholar
• [3] Asadpour A, Goemans MX, Madry A, Gharan SO, Saberi A (2017) An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem. Oper. Res. 65(4):1043–1061.Link, Google Scholar
• [4] Bansal N, Khandekar R, Nagarajan V (2009) Additive guarantees for degree-bounded directed network design. SIAM J. Comput. 39(4):1413–1431.Crossref, Google Scholar
• [5] Bansal N, Khandekar R, Könemann J, Nagarajan V, Peis B (2013) On generalizations of network design problems with degree bounds. Math. Programming Ser. A 141:479–506.Crossref, Google Scholar
• [6] Chaudhuri K, Rao S, Riesenfeld S, Talwar K (2009) A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids. Theoretical Comput. Sci. 410(44):4489–4503.Crossref, Google Scholar
• [7] Chaudhuri K, Rao S, Riesenfeld S, Talwar K (2009) What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs. Algorithmica 55:157–189.Crossref, Google Scholar
• [8] Chekuri C, Vondrák J, Zenklusen R (2009) Dependent randomized rounding for matroid polytopes and applications. Preprint, submitted September 24, https://arxiv.org/abs/0909.4348.Google Scholar
• [9] Chekuri C, Vondrák J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. Proc. 51st Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 575–584.Google Scholar
• [10] Cheriyan J, Friggstad Z, Gao Z (2015) Approximating minimum-cost connected T-joins. Algorithmica 72(1):126–147.Crossref, Google Scholar
• [11] Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA.Google Scholar
• [12] Christofides N (2022) Worst-case analysis of a new heuristic for the travelling salesman problem. Oper. Res. Forum 3(20). https://link.springer.com/article/10.1007/s43069-021-00101-z#citea.Crossref, Google Scholar
• [13] Edmonds J (1971) Matroids and the greedy algorithm. Math. Programming 1(1):127–136.Crossref, Google Scholar
• [14] Edmonds J, Johnson EL (1973) Matching, Euler tours and the Chinese postman. Math. Programming 5(1):88–124.Crossref, Google Scholar
• [15] Goddyn LA (2018) Some open problems I like. Accessed September 29, 2023, https://people.math.sfu.ca/~goddyn/Problems/problems.html.Google Scholar
• [16] Goemans MX (2006) Minimum bounded degree spanning trees. Proc. 47th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 273–282.Google Scholar
• [17] Gottschalk C, Vygen J (2018) Better s-t-tours by Gao trees. Math. Programming 172:191–207.Crossref, Google Scholar
• [18] Karlin AR, Klein N, Oveis Gharan S (2021) A (slightly) improved approximation algorithm for metric TSP. Proc. 53rd Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 32–45.Google Scholar
• [19] Karlin AR, Klein N, Oveis Gharan S (2023) A deterministic better-than-3/2 approximation algorithm for metric TSP. Del Pia A, Kaibel V, eds. Integer Programming and Combinatorial Optimization. IPCO 2023. Lecture Notes in Computer Science, vol. 13904 (Springer, Cham, Switzerland), 261–274.Google Scholar
• [20] Kawarabayashi K, Kobayashi Y, Reed B (2012) The disjoint paths problem in quadratic time. J. Combin. Theory Ser. B 102(2):424–435.Crossref, Google Scholar
• [21] Könemann J, Ravi R (2000) A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees. Proc. 32nd Annual ACM Sympos. Theory Comput. (ACM, New York), 537–546.Google Scholar
• [22] Könemann J, Ravi R (2003) Primal-dual meets local search: Approximating MSTs with nonuniform degree bounds. Proc. 35th Annual ACM Sympos. Theory Comput. (ACM, New York), 389–395.Google Scholar
• [23] Korte B, Vygen J (2018) Combinatorial Optimization: Theory and Algorithms, 6th ed. (Springer, Berlin).Crossref, Google Scholar
• [24] Linhares A, Swamy C (2018) Approximating min-cost chain-constrained spanning trees: A reduction from weighted to unweighted problems. Math. Programming 172:17–34.Crossref, Google Scholar
• [25] Martin R (1991) Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3):119–128.Crossref, Google Scholar
• [26] Nagamochi H, Nishimura K, Ibaraki T (1997) Computing all small cuts in an undirected network. SIAM J. Discrete Math. 10(3):469–481.Crossref, Google Scholar
• [27] Nägele M, Zenklusen R (2019) A new dynamic programming approach for spanning trees with chain constraints and beyond. Proc. 30th ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1550–1569.Google Scholar
• [28] Olver N, Zenklusen R (2018) Chain-constrained spanning trees. Math. Programming 167(2):293–314.Crossref, Google Scholar
• [29] Schrijver A (2003) Combinatorial Optimization – Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• [30] Sebő A (2013) Eight-fifth approximation for the path TSP. Goemans M, Correa J, eds. Integer Programming and Combinatorial Optimization. IPCO 2013. Lecture Notes in Computer Science, vol. 7801 (Springer, Berlin), 362–374.Google Scholar
• [31] Sebő A, van Zuylen A (2019) The salesman’s improved paths through forests. J. ACM 66(4):1–16.Crossref, Google Scholar
• [32] Serdyukov AI (1987) O nekotorykh ekstremal’nykh obkhodakh v grafakh. Upravlyaemye Sistemy 17:76–79.Google Scholar
• [33] Singh M, Lau LC (2007) Approximating minimum bounded degree spanning trees to within one of optimal. Proc. 39th Annual ACM Sympos. Theory Comput. (ACM), 661–670.Google Scholar
• [34] Svensson O, Tarnawski J, Végh L (2020) A constant-factor approximation algorithm for the asymmetric traveling salesman problem. J. ACM 67(6):1–53.Crossref, Google Scholar
• [35] Tardos É (1986) A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34(2):250–256.Link, Google Scholar
• [36] Traub V (2020) Improving on best-of-many-Christofides for T-tours. Oper. Res. Lett. 48(6):798–804.Crossref, Google Scholar
• [37] Traub V, Vygen J (2019) Approaching 3/2 for the s-t path TSP. J. ACM 66(2):1–17.Crossref, Google Scholar
• [38] Traub V, Vygen J (2022) An improved approximation algorithm for the asymmetric traveling salesman problem. SIAM J. Comput. 51(1):139–173.Crossref, Google Scholar
• [39] Traub V, Vygen J, Zenklusen R (2021) Reducing path TSP to TSP. SIAM J. Comput. 51(3):24–53.Google Scholar
• [40] van Bevern R, Slugina VA (2020) A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem. Historia Mathematica 53:118–127.Crossref, Google Scholar
• [41] Vygen J (2016) Reassembling trees for the traveling salesman. SIAM J. Discrete Math. 30(2):875–894.Crossref, Google Scholar
• [42] Wolsey LA (1980) Heuristic analysis, linear programming and branch and bound. Math. Programming Stud. 13:121–134.Crossref, Google Scholar
• [43] Zenklusen R (2012) Matroidal degree-bounded minimum spanning trees. Proc. 23rd ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1512–1521. Google Scholar
• [44] Zenklusen R (2019) A 1.5-approximation for path TSP. Proc. 30th ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1539–1549.Google Scholar