81 citations · 87 across the 7 of their papers we have counts for
9 papers
Finding irrelevant vertices in linear time on bounded-genus graphs
Petr A. Golovach, Stavros G. Kolliopoulos, Giannos Stamoulis +1
The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these probl…
Planar Disjoint-Paths Completion
Isolde Adler, Stavros G. Kolliopoulos, Dimitrios M. Thilikos
introduce {\sc Planar Disjoint Paths Completion}, a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follo…
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…
Irrelevant Vertices for the Planar Disjoint Paths Problem
Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause +3
The Disjoint Paths Problem asks, given a graph and a set of pairs of terminals , whether there is a collection of pairwise vertex-disjoi…
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…
Approximation Algorithms for Covering/Packing Integer Programs
Stavros G. Kolliopoulos, Neal E. Young
Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing min {c.x: x in Z^n_+, Ax > a, Bx < b, x < d}. We give a bicrit…