APPOL 2 Workshop 23-28 March 2003
University of Bologna Residential Center |
---|
The format of this meeting will be about two, two and a half days of lectures, followed by a few days during which research problems will be discussed in a congenial atmosphere.
08.00-09.00 | breakfast | |||||
---|---|---|---|---|---|---|
09.30-10.10 | Thomas Erlebach | Frits Spieksma | research! | research! | research! | departures |
10.15-11.05 | Alexander Hall | Leen Stougie | ||||
11.05-11.20 | coffee break | coffee break | ||||
11.20-12.00 | Martin Skutella | Sai Anand | ||||
12.30-13.30 | lunch! | lunch! | ||||
16.00-16.40 | Fernandez Dela Vega | Guochuan Zhang | ||||
16.45-17.35 | Gerold Jäger | Rene Sitters | ||||
17.35-17.50 | coffee | coffee | ||||
17.50-18.40 | Stefano Leonardi |
Arrival: Saturday 22 March, 2003 | Departures: 28-29 March, 2003 |
---|---|
Last day of talks: | Tuesday 25 March, 2003 |
End of workshop: | Friday 28 March, 2003 |
Bertinoro itself is picturesque, with many narrow streets and walkways winding around the central peak. The meeting will be held in a redoubtable ex-Episcopal fortress that has been converted by the University of Bologna into a modern conference center with computing facilities and Internet access. From the fortress you can enjoy a beautiful the vista that stretches from the Tuscan Apennines to the Adriatic coast.
Scientific Organizing Committee | Stefano Leonardi Università La Sapienza di Roma |
---|---|
Alessandro Panconesi Università La Sapienza di Roma | Local Organization |
Andrea Bandini, Elena Della Godenza, Centro Congressi di Bertinoro | |
Sponsored by | BICI Bertinoro International Center for Informatics |
Motivated by the fact that competitive analysis yields too pessimistic results
when applied to the paging problem, there has been considerable research
interest in refining competitive analysis and in developing alternative
models for studying online paging. The goal is to devise models in which
theoretical results capture phenomena observed in practice.
In this talk we propose a new, simple model for studying paging with locality
of reference. The model is closely related to Denning's working set concept
and directly reflects the amount of locality that request sequences exhibit.
We demonstrate that our model is reasonable from a practical point of view.
We use the page fault rate to evaluate the quality of paging algorithms,
which is the performance measure used in practice. We develop tight or nearly
tight bounds on the fault rates achieved by popular paging algorithms such as
LRU, FIFO, deterministic Marking strategies and LFD. It shows that LRU is an
optimal online algorithm, whereas FIFO and Marking strategies are not optimal
in general. We present an experimental study comparing the page fault rates
proven in our analyses to the page fault rates observed in practice.
This is the first such study for an alternative/refined paging model.
(Joint work with Lene Favrholdt and Oliver Giel.)
We prove that the combinatorial diameter of the skeleton of the polytope of
feasible solutions of any $m \times n$ transportation problem is less than
$8 \, (m+n)$.
We consider the general on-line two server problem in which at each step
both servers receive a request, which is a point in a metric space. One of
the servers has to be moved to its request. The special case where the
requests are points on the real line is known as the CNN-problem. It has
been a well-known open question if an algorithm with a constant competitive
ratio exists for this problem. We answer this question in the affirmative
sense by providing an algorithm that is 23808-competitive on any metric
space.
The constant is huge and the algorithm is rather ugly but our main goal was
indeed to settle the question. We believe that our result gives new insight
in the problem and will lead to more and much better algorithms for the
general $k$-server problem in the near future.
Joint work with Leen Stougie and Willem de Paepe.
We design the first polynomial time approximation schemes (PTASs) for the
problem of Metric MIN-BISECTION: given a finite metric
space, divide the points into
two halves so as to minimize the sum of distances across that partition.
Our approximation schemes depend on biased sampling
and on a new application of linearized quadratic programs with
randomized rounding of non-uniformly bounded numbers.
Joint work with Marek Karpinski and Claire Kenyon
Spielman and Teng invented the concept of smoothed analysis to explain the
success of algorithms that are known to work well in practice while
presenting poor worst case performance. Spielman and Teng [STOC 01]
proved that the simplex algorithm runs in expected polynomial time if the
input instance is smoothened with a normal distribution. We extend this
notion to analyze online algorithms. In particular we introduce smoothed
competitive analysis to study the Multi-Level Feedback (MLF) algorithm, at
the basis of the scheduling policies of Unix and Windows NT, when
the processing times of jobs released over time are only known at time of
completion.
We show that, if the k least significant of K bits describing the
processing time of a job are randomly changed, MLF achieves a tight
smoothed competitive ratio of O(2K-k) to minimize the average flow time. A
direct consequence is a first constant approximation for this problem in
the average case under a quite general class of probability distributions.
Joint work with L. Becchetti, A. Marchetti-Spaccamela, G. Schäfer, and T. Vredeveld.
A recently proposed model of the Internet at the level of autnomous
systems (ASs) is a graph in which the edges are classified according
to the economic relationships between the ASs that they connect:
Edges can be customer-provider edges or peer-to-peer edges. It is
assumed that a path in the network is only valid if it consists of
a sequence of customer-provider edges, followed by zero or one
peer-to-peer edges, followed by a sequence of provider-customer
edges. Motivated by robustness considerations, we consider the
problem of computing a minimum vertex cut that separates two
given vertices (meaning that no valid path between them remains
after removing the vertices of the cut from the network). We show
that the problem is NP-hard and present a 2-approximation algorithm
based on linear programming techniques.
(joint work with Danica Vukadinovic)
The intention of the talk is to give an introduction into the area of
"flows over time" or "dynamic flows". Flows over time have been introduced
about forty years ago by Ford and Fulkerson and have many real-world
applications such as, for example, traffic control, evacuation plans,
production systems, communication networks, and financial flows. Flows over
time are modeled in networks with capacities and transit times on the arcs.
The transit time of an arc specifies the amount of time it takes for flow to
travel from the tail to the head of that arc. In contrast to the classical
case of static flows, a flow over time specifies a flow rate entering an arc
for each point in time and the capacity of an arc limits the rate of flow
into the arc at each point in time. We discuss recent approximation and
hardness results for flows over time with multiple commodities and costs.
The talk is based on joint work with Lisa Fleischer, Alex Hall, and Steffen
Hippler.
Motivated by applications in road traffic control, we study flows in networks
featuring special characteristics. In contrast to classical static flow
problems, time plays an important role. Firstly, there are transit times on the
arcs of the network which specify the amount of time it takes for flow to travel
through an arc; in particular, flow values on arcs may change over
time. Secondly, the transit time of an arc varies with the current amount of
flow using this arc. The latter feature is crucial for various real-life
applications of flows over time.
K\"ohler et al. (Proceedings of ESA 2002, LNCS 2461, pp. 599-611) study the
single commodity case and give a (2+$\varepsilon$)-approximation based on the
notion of temporarily repeated flows, where flow is pushed at constant rates
into (possibly) several paths which do not change over time. We are able to
generalize this result to the multicommodity case, by modifying the underlying
network and the way flow is pushed into the corresponding paths. Applying the
same technique to condensed time-expanded networks allows variation of flow
paths over time. This approach even yields a fully polynomial time approximation
scheme for the multicommodity case, which is known to be NP-hard. Furthermore we
show that under a certain restriction of valid flows, the single commodity case
is NP-hard as well.
When handling large collections of data, the communication between fast
internal memory and slow external memory (e.g. disks) can be a
performance bottleneck. We study the problem of maximizing the
throughput (that is, the number of requests served per time-unit) for
parallel disks. This retrieval problem can be formulated as assigning a
maximum number of size 1 and size 2 jobs to machines of limited
capacity. We show that the LP-relaxation of an integer programming
formulation is half-integral. Further, we sketch 2/3-approximation
algorithms for this problem.
Joint work with Joep Aerts and Jan Korst.
Joint work with Anand Srivastav
We consider a weighted, directed graph with n vertices and the problem
of dividing the set of vertices in two parts of sizes k and n-k,
so that the edges of some of four regions (edges on the two subgraphs
and edges between the two subgraphs in both directions) becomes maximum. For
example, MAX-k-DENSE-SUBGRAPH is the problem of determining a subset S of size
k, so that the sum of the edge weights of the subgraph induced by S becomes
maximum. There are six nontrivial problems of this kind.
Halperin and Zwick have introduced an algorithm based on semidefinite programming,
which for the case k = n/2 and these six maximum graph partition problems
delivers the best known approximation ratios. We show improvements
of their techniques and generalize the algorithm for arbitrary k.
Joint work with Klaus Jansen.
ABSTRACTS
On Paging with Locality of Reference
by Susanne Albers, Universität Freiburg
A Linear Bound on the Diameter of the Transportation Polytope
by Leen Stougie, Technische Universiteit Eindhoven
A competitive algorithm for the general two server-problem
by Rene Sitters, Technische Universiteit Eindhoven
Polynomial time approximation schemes for metric MIN-BISECTION
by Fernandez De La Vega, Universitè Paris Sud
Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm
by Stefano Leonardi, Università di Roma La Sapienza
Approximating minimum cuts for valid paths in the Internet
by Thomas Erlebach, ETH Zürich
Flows over time - approximation and complexity
by Martin Skutella, Technische Universität Berlin
Routing and Call Control Algorithms in Ring Networks
by Sai Anand, ETH Zürich
FPTAS for Flows Over Time with Inflow-Dependent Transit Times
by Alexander Hall, ETH Zürich
Approximation of a retrieval problem for parallel disks
by Frits Spieksma, Katholieke Universiteit Leuven
Improved Approximation Algorithms for Maximum Graph Partition Problems
by Gerold Jäger, Universität Kiel
On weighted rectangle packing
by Guochuan Zhang, Universität Kiel