Source author record

Stavros G. Kolliopoulos

Stavros G. Kolliopoulos appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.CO

Catalog footprint

What is connected

7works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Irrelevant Vertices for the Planar Disjoint Paths Problem

The Disjoint Paths Problem asks, given a graph $G$ and a set of pairs of terminals $(s_{1},t_{1}),\ldots,(s_{k},t_{k})$, whether there is a collection of $k$ pairwise vertex-disjoint paths linking $s_{i}$ and $t_{i}$, for $i=1,\ldots,k.$ In their $f(k)\cdot n^{3}$ algorithm for this problem, Robertson and Seymour introduced the irrelevant vertex technique according to which in every instance of treewidth greater than $g(k)$ there is an "irrelevant" vertex whose removal creates an equivalent instance of the problem. This fact is based on the celebrated Unique Linkage Theorem, whose - very technical - proof gives a function $g(k)$ that is responsible for an immense parameter dependence in the running time of the algorithm. In this paper we give a new and self-contained proof of this result that strongly exploits the combinatorial properties of planar graphs and achieves $g(k)=O(k^{3/2}\cdot 2^{k}).$ Our bound is radically better than the bounds known for general graphs.

preprint2015arXiv

Planar Disjoint-Paths Completion

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 follows: given a, not necessarily connected, plane graph $G,$ $k$ pairs of terminals, and a face $F$ of $G,$ find a minimum-size set of edges, if one exists, to be added inside $F$ so that the embedding remains planar and the pairs become connected by $k$ disjoint paths in the augmented network. Our results are twofold: first, we give an upper bound on the number of necessary additional edges when a solution exists. This bound is a function of $k$, independent of the size of $G.$ Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time $f(k)\cdot n^{2}.$

preprint2014arXiv

Extended Formulation Lower Bounds via Hypergraph Coloring?

Exploring the power of linear programming for combinatorial optimization problems has been recently receiving renewed attention after a series of breakthrough impossibility results. From an algorithmic perspective, the related questions concern whether there are compact formulations even for problems that are known to admit polynomial-time algorithms. We propose a framework for proving lower bounds on the size of extended formulations. We do so by introducing a specific type of extended relaxations that we call product relaxations and is motivated by the study of the Sherali-Adams (SA) hierarchy. Then we show that for every approximate relaxation of a polytope P, there is a product relaxation that has the same size and is at least as strong. We provide a methodology for proving lower bounds on the size of approximate product relaxations by lower bounding the chromatic number of an underlying hypergraph, whose vertices correspond to gap-inducing vectors. We extend the definition of product relaxations and our methodology to mixed integer sets. However in this case we are able to show that mixed product relaxations are at least as powerful as a special family of extended formulations. As an application of our method we show an exponential lower bound on the size of approximate mixed product formulations for the metric capacitated facility location problem, a problem which seems to be intractable for linear programming as far as constant-gap compact formulations are concerned.

preprint2014arXiv

Sherali-Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location

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-constrained generalizations, such as capacitated facility location (CFL) and lower-bounded facility location (LBFL), have proved notorious as far as LP-based approximation is concerned: while there are local-search-based constant-factor approximations, there is no known linear relaxation with constant integrality gap. According to Williamson and Shmoys devising a relaxation-based approximation for \cfl\ is among the top 10 open problems in approximation algorithms. This paper advances significantly the state-of-the-art on the effectiveness of linear programming for capacity-constrained facility location through a host of impossibility results for both CFL and LBFL. We show that the relaxations obtained from the natural LP at $Ω(n)$ levels of the Sherali-Adams hierarchy have an unbounded gap, partially answering an open question of \cite{LiS13, AnBS13}. Here, $n$ denotes the number of facilities in the instance. Building on the ideas for this result, we prove that the standard CFL relaxation enriched with the generalized flow-cover valid inequalities \cite{AardalPW95} has also an unbounded gap. This disproves a long-standing conjecture of \cite{LeviSS12}. We finally introduce the family of proper relaxations which generalizes to its logical extreme the classic star relaxation and captures general configuration-style LPs. We characterize the behavior of proper relaxations for CFL and LBFL through a sharp threshold phenomenon.

preprint2013arXiv

Integrality gaps for strengthened LP relaxations of Capacitated and Lower-Bounded Facility Location

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 capacitated facility location (CFL) and lower-bounded facility location (LBFL). In the former, every facility has a capacity which is the maximum demand that can be assigned to it, while in the latter, every open facility is required to serve a given minimum amount of demand. Both CFL and LBFL are approximable within a constant factor but their respective natural LP relaxations have an unbounded integrality gap. According to Shmoys and Williamson, the existence of a relaxation-based algorithm for CFL is one of the top 10 open problems in approximation algorithms. In this paper we give the first results on this problem. We provide substantial evidence against the existence of a good LP relaxation for CFL by showing unbounded integrality gaps for two families of strengthened formulations. The first family we consider is the hierarchy of LPs resulting from repeated applications of the lift-and-project Lovász-Schrijver procedure starting from the standard relaxation. We show that the LP relaxation for CFL resulting after $Ω(n)$ rounds, where $n$ is the number of facilities in the instance, has unbounded integrality gap. Note that the Lovász-Schrijver procedure is known to yield an exact formulation for CFL in at most $n$ rounds. We also introduce the family of proper relaxations which generalizes to its logical extreme the classic star relaxation, an equivalent form of the natural LP. We characterize the integrality gap of proper relaxations for both LBFL and CFL and show a threshold phenomenon under which it decreases from unbounded to 1.

preprint2012arXiv

The 2-valued case of makespan minimization with assignment constraints

We consider the following special case of minimizing makespan. A set of jobs $J$ and a set of machines $M$ are given. Each job $j \in J$ can be scheduled on a machine from a subset $M_j$ of $M$. The processing time of $j$ is the same on all machines in $M_j.$ The jobs are of two sizes, namely $b$ (big) and $s$ (small). We present a polynomial-time algorithm that approximates the value of the optimal makespan within a factor of 1.883 and some further improvements when every job can be scheduled on at most two machines.

preprint2005arXiv

Approximation Algorithms for Covering/Packing Integer Programs

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 bicriteria-approximation algorithm that, given epsilon in (0, 1], finds a solution of cost O(ln(m)/epsilon^2) times optimal, meeting the covering constraints (Ax > a) and multiplicity constraints (x < d), and satisfying Bx < (1 + epsilon)b + beta, where beta is the vector of row sums beta_i = sum_j B_ij. Here m denotes the number of rows of A. This gives an O(ln m)-approximation algorithm for CIP -- minimum-cost covering integer programs with multiplicity constraints, i.e., the special case when there are no packing constraints Bx < b. The previous best approximation ratio has been O(ln(max_j sum_i A_ij)) since 1982. CIP contains the set cover problem as a special case, so O(ln m)-approximation is the best possible unless P=NP.