21.02.2017
On the most imbalanced orientation of a graph
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2018
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
NP
-hard and cannot be approximated within a ratio of \(\frac{1}{2}+\varepsilon \) for any constant \(\varepsilon >0\) in polynomial time unless \(\texttt {P}=\texttt {NP}\) even if the minimum degree of the graph \(\delta \) equals 2. Then we describe a polynomial-time approximation algorithm whose ratio is almost equal to \(\frac{1}{2}\). An exact polynomial-time algorithm is also derived for cacti. Finally, two mixed integer linear programming formulations are presented. Several valid inequalities are exhibited with the related separation algorithms. The performance of the strengthened formulations is assessed through several numerical experiments.