On the most imbalanced orientation of a graph

Walid Ben-Ameur (), Antoine Glorieux () and José Neto ()
Additional contact information
Walid Ben-Ameur: Université Paris-Saclay
Antoine Glorieux: Université Paris-Saclay
José Neto: Université Paris-Saclay

Journal of Combinatorial Optimization, 2018, vol. 36, issue 2, No 17, 637-669

Abstract: Abstract We study the problem of orienting the edges of a graph such that the minimum over all the vertices of the absolute difference between the outdegree and the indegree of a vertex is maximized. We call this minimum the imbalance of the orientation, i.e. the higher it gets, the more imbalanced the orientation is. The studied problem is denoted by $${{\mathrm{\textsc {MaxIm}}}}$$ M A X I M . We first characterize graphs for which the optimal objective value of $${{\mathrm{\textsc {MaxIm}}}}$$ M A X I M is zero. Next we show that $${{\mathrm{\textsc {MaxIm}}}}$$ M A X I M is generally NP-hard and cannot be approximated within a ratio of $$\frac{1}{2}+\varepsilon $$ 1 2 + ε for any constant $$\varepsilon >0$$ ε > 0 in polynomial time unless $$\texttt {P}=\texttt {NP}$$ P = 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}$$ 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.

Keywords: Graph theory; Orientation; Complexity; Mixed integer programming; Cutting plane algorithm; (In)approximability; Cactus (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0117-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:2:d:10.1007_s10878-017-0117-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0117-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().