LP relaxation and tree packing for minimum \(k\)-cuts. (English) Zbl 07902010
Fineman, Jeremy T. (ed.) et al., 2nd symposium on simplicity in algorithms. SOSA 2019, January 8–9, 2019, San Diego, CA, USA. Co-located with the 30th ACM-SIAM symposium on discrete algorithms (SODA 2019). Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. OASIcs – OpenAccess Ser. Inform. 69, Article 7, 18 p. (2019).
Summary: Karger used spanning tree packings [D. R. Karger, J. ACM 47, No. 1, 46–76 (2000; Zbl 1094.68613)] to derive a near linear-time randomized algorithm for the global minimum cut problem as well as a bound on the number of approximate minimum cuts. This is a different approach from his well-known random contraction algorithm [D. R. Karger, Random Sampling in Graph Optimization Problems. PhD thesis, Stanford University, February 1995; D. R. Karger and C. Stein, J. ACM 43, No. 4, 601–640 (1996; Zbl 0882.68103)]. Thorup developed a fast deterministic algorithm for the minimum \(k\)-cut problem via greedy recursive tree packings [M. Thorup, in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM). 159–166 (2008; Zbl 1231.68185)].
In this paper we revisit properties of an LP relaxation for \(k\)-cut proposed by J. Naor and Y. Rabani [in: Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms, SODA 2001, Washington, DC, USA, January 7–9, 2001. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics; New York, NY: ACM, Association for Computing Machinery. 26–27 (2001; Zbl 0987.05089)], and analyzed in [C. Chekuri et al., SIAM J. Discrete Math. 20, No. 1, 261–271 (2006; Zbl 1107.68121)]. We show that the dual of the LP yields a tree packing, that when combined with an upper bound on the integrality gap for the LP, easily and transparently extends Kargers’ analysis [loc. cit.] for mincut to the \(k\)-cut problem. In addition to the simplicity of the algorithm and its analysis, this allows us to improve the running time of Thorups’ algorithm [loc. cit.] by a factor of \(n\). We also improve the bound on the number of \(\alpha\)-approximate \(k\)-cuts. Second, we give a simple proof that the integrality gap of the LP is \(2(1-1/n)\). Third, we show that an optimum solution to the LP relaxation, for all values of \(k\), is fully determined by the principal sequence of partitions of the input graph. This allows us to relate the LP relaxation to the Lagrangean relaxation approach of [F. Barahona, Oper. Res. Lett. 26, No. 3, 99–105 (2000; Zbl 0955.90142)] and [R. Ravi and A. Sinha, Eur. J. Oper. Res. 186, No. 1, 77–90 (2008; Zbl 1138.90023)]; it also shows that the idealized recursive tree packing considered by Thorup [loc. cit.] gives an optimum dual solution to the LP. This work arose from an effort to understand and simplify the results of Thorup [loc. cit.].
For the entire collection see [Zbl 1407.68030].
In this paper we revisit properties of an LP relaxation for \(k\)-cut proposed by J. Naor and Y. Rabani [in: Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms, SODA 2001, Washington, DC, USA, January 7–9, 2001. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics; New York, NY: ACM, Association for Computing Machinery. 26–27 (2001; Zbl 0987.05089)], and analyzed in [C. Chekuri et al., SIAM J. Discrete Math. 20, No. 1, 261–271 (2006; Zbl 1107.68121)]. We show that the dual of the LP yields a tree packing, that when combined with an upper bound on the integrality gap for the LP, easily and transparently extends Kargers’ analysis [loc. cit.] for mincut to the \(k\)-cut problem. In addition to the simplicity of the algorithm and its analysis, this allows us to improve the running time of Thorups’ algorithm [loc. cit.] by a factor of \(n\). We also improve the bound on the number of \(\alpha\)-approximate \(k\)-cuts. Second, we give a simple proof that the integrality gap of the LP is \(2(1-1/n)\). Third, we show that an optimum solution to the LP relaxation, for all values of \(k\), is fully determined by the principal sequence of partitions of the input graph. This allows us to relate the LP relaxation to the Lagrangean relaxation approach of [F. Barahona, Oper. Res. Lett. 26, No. 3, 99–105 (2000; Zbl 0955.90142)] and [R. Ravi and A. Sinha, Eur. J. Oper. Res. 186, No. 1, 77–90 (2008; Zbl 1138.90023)]; it also shows that the idealized recursive tree packing considered by Thorup [loc. cit.] gives an optimum dual solution to the LP. This work arose from an effort to understand and simplify the results of Thorup [loc. cit.].
For the entire collection see [Zbl 1407.68030].
MSC:
| 68Wxx | Algorithms in computer science |
