4 citations · 6 across the 4 of their papers we have counts for
5 papers
Extended Formulation Lower Bounds via Hypergraph Coloring?
Stavros G. Kolliopoulos, Yannis Moysoglou
Exploring the power of linear programming for combinatorial optimization problems has been recently receiving renewed attention after a series of breakthrough impossibility results…
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…
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…
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…
The 2-valued case of makespan minimization with assignment constraints
Stavros G. Kolliopoulos, Yannis Moysoglou
We consider the following special case of minimizing makespan. A set of jobs and a set of machines are given. Each job can be scheduled on a machine from a subset…