Top

Journal of Combinatorial Optimization

Published in:

01-01-2019

A spectral partitioning algorithm for maximum directed cut problem

Authors: Zhenning Zhang, Donglei Du, Chenchen Wu, Dachuan Xu, Dongmei Zhang

Published in: Journal of Combinatorial Optimization | Issue 3/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We investigate the maximum directed cut (MaxDC) problem by designing a spectral partitioning algorithm. Given a directed graph with nonnegative arc weights, we wish to obtain a bipartition of the vertices such that the total weight of the directed cut arcs is maximized. Relaxing the MaxDC problem as a quadratic program allows us to explore combinatorial properties of the optimal solution, leading to a 0.272-approximation algorithm via the technique of spectral partitioning rounding.

previous article On the complexity and approximability of repair position selection problem

next article On the complexity of and algorithms for detecting k-length negative cost cycles

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Beckenbach E, Bellman R (1961) An introduction to inequalities. Random House, New YorkCrossRef

Feige U, Jozeph S (2015) Oblivious algorithms for the maximum directed cut problem. Algorithmica 71:409–428MathSciNetCrossRef

Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42:1115–1145MathSciNetCrossRef

Kale S, Seshadhri C (2010) Combinatorial approximation algorithms for MaxCut using random walks (preprint). arXiv:1008.3938

Lewin M, Livnat D, Zwick U (2002) Improved rounding techniques for the MAX \(2\)-SAT and MAX DI-CUT problems. In: Proceedings of the 9th international conference on integer programming and combinatorial optimization, pp 67–82

Nikiforov V (2016) Max \(k\)-cut and the smallest eigenvalue. Linear Algebra Appl 504:462–467MathSciNetCrossRef

Soto A (2015) Improved analysis of Max-Cut algorithm based on spectral partitioning. SIAM J Discrete Math 29:259–268MathSciNetCrossRef

Trevisan L (2012) Max cut and the smallest eigenvalue. SIAM J Comput 41:1769–1786MathSciNetCrossRef

Title: A spectral partitioning algorithm for maximum directed cut problem
Authors: Zhenning Zhang
Donglei Du
Chenchen Wu
Dachuan Xu
Dongmei Zhang
Publication date: 01-01-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2021
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-018-0369-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2021

Tropical paths in vertex-colored graphs

An improved mechanism for selfish bin packing

Mixed connectivity properties of random graphs and some special graphs

A dynamic approach to detecting, eliminating and fixing memory leaks

The one-cop-moves game on planar graphs

The spectral radius and domination number in linear uniform hypergraphs

Premium Partner