4 citations · 6 across the 4 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.DS2013★ 4 cited
Exponential lower bounds on the size of approximate formulations in the natural encoding for Capacitated Facility Location
Stavros G. Kolliopoulos, Yannis Moysoglou
The metric capacitated facility location is a well-studied problem for which, while constant factor approximations are known, no efficient relaxation with constant integrality gap…
cs.DS2013★ 1 cited
Sherali-Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location
Stavros G. Kolliopoulos, Yannis Moysoglou
Metric facility location is a well-studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. The capacity-constra…
cs.DS2013★ 1 cited
Integrality gaps for strengthened LP relaxations of Capacitated and Lower-Bounded Facility Location
Stavros G. Kolliopoulos, Yannis Moysoglou
The metric uncapacitated facility location problem (UFL) enjoys a special stature in approximation algorithms as a testbed for various techniques. Two generalizations of UFL are ca…