Document Open Access Logo

A Parallel Framework for Approximate Max-Dicut in Partitionable Graphs

Authors Nico Bertram, Jonas Ellert , Johannes Fischer

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.10.pdf
  • Filesize: 1.7 MB
  • 15 pages

Document Identifiers

Author Details

Nico Bertram
  • Department of Computer Science, Technische Universität Dortmund, Germany
Jonas Ellert
  • Department of Computer Science, Technische Universität Dortmund, Germany
Johannes Fischer
  • Department of Computer Science, Technische Universität Dortmund, Germany

Funding

This work has been supported by the German Research Association (DFG) within the Collaborative Research Center SFB 876 “Providing Information by Resource-Constrained Analysis”, project A6.

Cite AsGet BibTex

Nico Bertram, Jonas Ellert, and Johannes Fischer. A Parallel Framework for Approximate Max-Dicut in Partitionable Graphs. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SEA.2022.10

Abstract

Computing a maximum cut in undirected and weighted graphs is a well studied problem and has many practical solutions that also scale well in shared memory (despite its NP-completeness). For its counterpart in directed graphs, however, we are not aware of practical solutions that also utilize parallelism. We engineer a framework that computes a high quality approximate cut in directed and weighted graphs by using a graph partitioning approach. The general idea is to partition a graph into k subgraphs using a parallel partitioning algorithm of our choice (the first ingredient of our framework). Then, for each subgraph in parallel, we compute a cut using any polynomial time approximation algorithm (the second ingredient). In a final step, we merge the locally computed solutions using a high-quality or exact parallel Max-Dicut algorithm (the third ingredient). On graphs that can be partitioned well, the quality of the computed cut is significantly better than the best cut achieved by any linear time algorithm. This is particularly relevant for large graphs, where linear time algorithms used to be the only feasible option.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Design and analysis of algorithms
Keywords
  • maximum directed cut
  • graph partitioning
  • algorithm engineering
  • approximation
  • parallel algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Y. Akhremtsev, P. Sanders, and C. Schulz. High-Quality Shared-Memory Graph Partitioning. IEEE Transactions on Parallel and Distributed Systems, 31(11):2710-2722, 2020. URL: https://doi.org/10.1109/TPDS.2020.3001645.
  2. Amotz Bar-Noy and Michael Lampis. Online maximum directed cut. Journal of combinatorial optimization, 24(1):52-64, 2012. URL: https://doi.org/10.1007/s10878-010-9318-6.
  3. Paolo Boldi, Bruno Codenotti, Massimo Santini, and Sebastiano Vigna. UbiCrawler: A scalable fully distributed web crawler. Software: Practice & Experience, 34(8):711-726, 2004. URL: https://doi.org/10.1002/spe.587.
  4. N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz. A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 649-658, 2012. URL: https://doi.org/10.1137/130929205.
  5. A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz. Recent Advances in Graph Partitioning, pages 117-158. Springer International Publishing, Cham, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_4.
  6. U. Feige and S. Jozeph. Oblivious Algorithms for the Maximum Directed Cut Problem. Algorithmica, 71(2):409-428, February 2015. URL: https://doi.org/10.1007/s00453-013-9806-z.
  7. M. X. Goemans and D. P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42(6):1115-1145, 1995. URL: https://doi.org/10.1145/227683.227684.
  8. Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz, and Daniel Seemaier. Deep Multilevel Graph Partitioning. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1-48:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.48.
  9. N. Gusmeroli, T. Hrga, B. Luvzar, J. Povh, M. Siebenhofer, and A. Wiegele. BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints. arXiv: Optimization and Control, 2020. URL: https://doi.org/10.48550/arxiv.2009.06240.
  10. E. Halperin and U. Zwick. Combinatorial Approximation Algorithms for the Maximum Directed Cut Problem. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '01, pages 1-7, USA, 2001. Society for Industrial and Applied Mathematics. Google Scholar
  11. T. Hrga and J. Povh. MADAM: A parallel exact solver for Max-Cut based on semidefinite programming and ADMM. Computational Optimization and Applications, 80:347-375, 2021. URL: https://doi.org/10.1007/s10589-021-00310-6.
  12. A. Jez. Recompression: A Simple and Powerful Technique for Word Equations. J. ACM, 63(4):1-51, 2016. URL: https://doi.org/10.1145/2743014.
  13. R. M. Karp. Reducibility among Combinatorial Problems, pages 85-103. Springer US, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  14. S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? SIAM J. Comput., 37(1):319-357, 2007. URL: https://doi.org/10.1137/S0097539705447372.
  15. N. Krislock, J. Malick, and F. Roupin. BiqCrunch: A Semidefinite Branch-and-Bound Method for Solving Binary Quadratic Problems. ACM Trans. Math. Softw., 43(32):1-23, 2017. URL: https://doi.org/10.1145/3005345.
  16. M. Lampis, G. Kaouri, and V. Mitsou. On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures. In Seok-Hee Hong, Hiroshi Nagamochi, and Takuro Fukunaga, editors, Algorithms and Computation, pages 220-231, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-540-92182-0_22.
  17. M. Lewin, D. Livnat, and U. Zwick. Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems. In W. J. Cook and A. S. Schulz, editors, Integer Programming and Combinatorial Optimization, pages 67-82, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-47867-1_6.
  18. Michael Luby and Noam Nisan. A parallel approximation algorithm for positive linear programming. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 448-457, 1993. URL: https://doi.org/10.1145/167088.167211.
  19. P. Raghavan. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Journal of Computer and System Sciences, 37(2):130-143, 1988. URL: https://doi.org/10.1016/0022-0000(88)90003-7.
  20. F. Rendl, G. Rinaldi, and A. Wiegele. Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations. Mathematical Programming, 121:307-335, 2010. URL: https://doi.org/10.1007/s10107-008-0235-8.
  21. R. A. Rossi and N. K. Ahmed. The Network Data Repository with Interactive Graph Analytics and Visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015. URL: http://networkrepository.com.
  22. J. Spencer. Ten Lectures on the Probabilistic Method, volume CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, 2nd edition, 1994. URL: https://doi.org/10.1137/1.9781611970074.
  23. U. Zwick. Analyzing the MAX 2-SAT and MAX DI-CUT approximation algorithms of Feige and Goemans, 2000. manuscript. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact