Reduced-size formulations for metric and cut polyhedra in sparse graphs - Sorbonne Université Access content directly
Journal Articles Networks Year : 2017

Reduced-size formulations for metric and cut polyhedra in sparse graphs

Abstract

Given a graph G = (V, E) with |V | = n and |E| = m, we consider the metric cone MET(G) and the metric polytope METP(G) defined on R E. These polyhedra are relaxations of several important problems in combinatorial optimization such as the max-cut problem and the multicommodity flow problem. They are known to have non-compact formulations via the cycle inequalities in the original space R E and compact (i.e., polynomial size) extended formulations via the triangle inequalities defined on the complete graph K n. In this paper, we show that one can reduce the number of triangle inequalities to O(nm) and still have extended formulations for MET(G) and METP(G). This is particularly interesting for sparse graphs when m = O(n), since formulations of size O(n 2) variables and constraints are thus obtained. Moreover, the possibility of achieving further reduction in size for special classes of sparse graphs is investigated; it is shown that for the case of series-parallel graphs, for which the max-cut problem can be solved in linear time (Barahona (1986)), one can refine the above reduction to obtain extended formulations for MET(G) and METP(G) fearturing O(n) variables and constraints.
Fichier principal
Vignette du fichier
Nguyen_2016_Reduced-size.pdf (255.14 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01405725 , version 1 (30-11-2016)

Identifiers

Cite

Viet Hung Nguyen, Michel Minoux, Dang Phuong Nguyen. Reduced-size formulations for metric and cut polyhedra in sparse graphs. Networks, 2017, 69 (1), pp.142-150. ⟨10.1002/net.21723⟩. ⟨hal-01405725⟩
292 View
180 Download

Altmetric

Share

Gmail Facebook X LinkedIn More