Copyright notice: Since most of these papers are published, the
copyright has been transferred to the respective
publishers. Therefore, the papers cannot be duplicated for commercial
purposes.
The following is ACM's copyright notice; other publishers
have similar ones.
"Copyright by the Association for Computing Machinery, Inc.
Permission to make digital or hard copies of part or all of this work
for personal or classroom use is granted without fee provided that
copies are not made or distributed for profit or commercial advantage
and that new copies bear this notice and the full citation on the
first page. Copyrights for components of this work owned by others
than ACM must be honored. Abstracting with credit is permitted."
Theory papers
|
|
Algorithms for single-source shortest paths
and the minimum mean cycle problem with expected running
time O(n^2 log n) over a comprehensive class of input distributions.
This is the
first
paper ever
to investigate average-case analysis for these problems.
An Omega(nm) lower bound is shown for Bellman-Ford type algorithms.
|
|
|
|
A framework yielding algorithms for five different versions of the
the single-source unsplittable
flow problem. We introduce a deterministic rounding technique based
on divide-and-conquer. We use the fractional solution to define the
subproblems.
Also included, improved results
on special cases of R| p_{ij} = p_j or \infty | Cmax.
|
|
|
|
Design of improved approximation algorithms for the class of
column-restricted packing integer programs, a strict
generalization of the
(0,1) PIPs. Applying these algorithms yields the first nontrivial
approximations for
multiple-source unsplittable flow, a generalization of the edge-disjoint
paths problem. Edge-disjoint paths is one of the most difficult NP-hard
problems to approximate and progress for the general case dates only
from the last few years.
We also introduce a very simple greedy
approximation algorithm
for edge- (vertex-) disjoint
paths which does not rely on solving first the linear relaxation.
|
|
D. W. Engels, D. R. Karger, S. G. Kolliopoulos,
S. Sengupta, R. N. Uma and
J. Wein.
Techniques for Scheduling with Rejection
J. of Algorithms, special
issue on the 6th European Symposium on Algorithms, (49):1, 175-191,
2003.
|
|
We examine approximation algorithms for minsum criteria under the
scenario where some jobs can be rejected (i.e., not scheduled at all)
at a penalty that contributes to the objective. We introduce a number of
techniques for different versions of this relatively new problem, some
based on linear relaxations.
|
|
|
|
This result belongs to the line of research
which started with Arora's seminal TSP work.
Our main contribution in terms of the
technique which enables us to get the fast algorithm is a new way of
decomposing solutions. Through this decomposition
we get a number of portals per
rectangle which, in contrast to previous work for both the k-median
and the TSP,
depends only on epsilon, not on n. The results
extend to any fixed dimension d > 2 and to uncapacitated facility location.
|
|
|
|
We examine a covering integer program (CIP), min c^T x, s.t.
Ax >=b, x >=0, that has in addition
multiplicity constraints x <=d. The integrality gap is
arbitrarily large. Still,
can one get an O(log m)-approximation with respect to the
optimum of the linear relaxation (as for the special
case of Set Cover) while violating the multiplicity constraints by a
multiplicative O(1) factor?
We answer in the affirmative for the case
of column-restricted CIPs, a strict generalization of
(0,1)-CIPs. In contrast to the next paper, the analysis we use is
purely deterministic.
|
|
|
|
We settle, unless P=NP, the approximability of
a general covering integer program (CIP) with multiplicity
constraints:
min c^T x, s.t.
Ax >=b, 0<=x<=d. The previous best bound dates from 1982.
As part of our methods, we present a relatively simple new idea for doing
randomized rounding: randomly round the fractional value of a variable
to its closest multiple of 1/k, for suitable k >1; then take the
ceiling of the resulting value.
|
|
S. G. Kolliopoulos and G. Steiner.
Partially-ordered Knapsack and Applications to Scheduling
Proc. 10th European Symposium on Algorithms (ESA)
2002, Springer-Verlag Lecture Notes in Computer Science
(LNCS) vol. 2461, 612-624. Journal version:
Discrete Applied Mathematics, (155), 889-897, 2007.
The linked file is an update of the conference
version. Sections 5-7 do not appear in the journal version. |
|
Partially-ordered Knapsack (POK)
extends classical Knapsack. A partial order is given on the set of items,
and what ends up in the knapsack should be a prefix of the partial
order. This is a natural problem which is closely related to 1 | prec
| sum w_jC_j. Very little is known for POK.
We give an FPTAS for the
important case of 2-dimensional partial orders, a class which is a
substantial generalization of the series-parallel class, and we
identify the first non-trivial case which is solvable in polynomial
time.
|
|
|
|
Frustratingly little is known on the
approximability of this basic scheduling problem.
We focus on the case where the number of
distinct due dates is fixed and provide two pseudopolynomial
algorithms. Our attempt at an FPTAS succeeds only for
polynomially bounded weights.
|
|
|
|
|
|
We study the approximability of minimum total weighted tardiness with
a modified objective which includes an additive constant. This ensures
the existence of a positive lower bound for the minimum
value. Moreover the new objective has a natural interpretation in
Just-In-Time production systems, namely in minimizing total
work-in-process inventory carrying costs.
|
|
Five papers on selfish routing
|
In the selfish routing setting, network users select
paths non-cooperatively. Each user wants to minimize her
disutility. Typically
one models this behavior by studying the system at an equilibrium in
the game-theoretic sense.
The following papers form a sequel of sorts. Very broadly
speaking they deal with
selfish routing settings where the users experience side constraints
either explicitly due to network characteristics or implicitly through
the design of the disutility function. |
|
|
|
|
We examine the existence and computability of taxes (tolls) on the edges
of a network that steer heterogeneous selfish users towards an
equilibrium that minimizes total latency.
|
|
G. Karakostas and S. G. Kolliopoulos.
The Efficiency of Optimal Taxes
Proc. 1st Workshop on Combinatorial and
Algorithmic Aspects of Networking (CAAN) 2004, Springer-Verlag LNCS vol.
3405, 3-12.
|
|
|
We prove that optimal taxes (tolls) exist even in the
case where the user demands are elastic, i.e., they depend on the
routing costs experienced at equilibrium (which itself depends on the
demands).
|
|
|
|
|
We settle, unless P=NP, the approximability
of total weighted tardiness on a single machine when the number of
distinct due dates is fixed. Previously, an FPTAS, due to Kelleler
and Strusevich, was known only for
the case where all jobs have a common due date.
|
|
|
|
|
|
I. Adler, S. G. Kolliopoulos, D. Thilikos.
Planar Disjoint-Paths Completion
Algorithmica 76(2): 401-425, 2016.
A preliminary version appeared in
Proc. of 6th International Symposium on Parameterized
and Exact Computation (IPEC), 2012.
|
|
Consider an instance of Disjoint Paths on a planar graph G with k pairs of
terminals.
The completion version of the problem is relevant when the
instance is infeasible.
A face F of the graph is specified and we ask whether it is possible
to add edges within F, the so-called completion, so that the instance
becomes feasible in the "patched" graph and planarity is maintained. Moreover, if the answer is
'Yes' we seek the completion with the minimum number of edges.
We prove that if a completion exists its size depends only on k.
This combinatorial result is then used to show that the problem is FPT
(Fixed-Parameter Tractable).
|
|
|
|
One of the cornerstones of Algorithmic
Graph Theory is the algorithm of Robertson and Seymour that solves
the disjoint-paths problem for k pairs of terminals in f(k)n^3
time. This algorithm arose out of the Graph Minors series of papers
and introduced the irrelevant vertex technique.
The dependence of the running time on the parameter k is immense and
the proof of correctness very technical. In this
paper we give an algorithm for disjoint paths on planar graphs with an explicit bound
on the parameter dependence and a new self-contained analysis.
|
|
|
|
|
|
|
Experimental papers
|
|
A number of algorithms and heuristics are evaluated with
respect both to how close they come to the fractional optimum
and running time. Test generators
are designed from scratch, using some ideas from earlier experimental work on
multicommodity flow. The experimental performance is typically much
better than the theoretical guarantees.
|
|
|
|
Packets
are queued at the input ports of a crossbar switch and need to be
transmitted to the output ports.
At every step a bipartite matching has to be
computed between the input and output ports. The question is
which matching is best, i.e., which matching produces a stable
system in the queue-theoretic sense.
A
comprehensive evaluation of matching-based algorithms from the literature is
performed and randomized heuristics are introduced that yield significant
performance improvements. Because of computational
considerations most algorithms from the literature compute only a
maximal matching at each step. We propose techniques that can be
combined essentially with any existing algorithm so as to escape from
locally optimal matchings.
|
|
|
|
An update of the IPCO 99 paper above with experimental results on the
currently best algorithms for minimizing congestion.
|
Book chapters
|
|
|
Ph.D. Thesis
|
mail:
Department of Informatics and Telecommunications,
National and Kapodistrian University of Athens, Panepistimiopolis Ilissia,
Athens 157 84, Greece |
phone: +30
210 727 5108 | office: B6 |
fax: +30 210 727 5114 |
email: id@host.gr, id (=sgk), host (= di.uoa)