Abstracts:
Vincenzo Auletta
Title: Deterministic Truthful Approximation Mechanisms for
Scheduling Related Machines
Abstract:
We consider the problem of scheduling jobs on related machines
owned by selfish agents and provide the first deterministic mechanisms
with constant approximation that are truthfu}; that is, truth-telling is a
dominant strategy for all agents.
More precisely, we present deterministic polynomial-time (2
+epsilon)-approximation algorithms and suitable payment functions that
yield truthful mechanisms for several NP-hard restrictions of this problem.
Our result also yields a family of deterministic polynomial-time
truthful (4+epsilon)-approximation mechanisms for any fixed number of
machines.
The only previously-known mechanism for this problem
(proposed by Archer and Tardos [FOCS 2001]) is 3-approximated,
randomized and truthful under a weaker notion of truthfulness.
To obtain our results we introduce a technique to transform the
PTAS by Graham into a deterministic truthful mechanism.
Philippe Baptiste
Title: Scheduling a Single Machine to Minimize a Regular
Objective Function under Setup Constraints
Abstract:
We study the scheduling situation
in which a set of jobs subjected to release dates and deadlines are to
be performed on a single machine. The objective is to minimize a
regular sum objective function $\sum_i f_i$ where $f_i(C_i)$
corresponds to the cost of the completion of job $J_i$ at time $C_i$. On
top of this, we also have to take into account setup times and setup
costs between families of jobs as well as the fact that some jobs can
be nperformed'' to reduce the load of the machine. We describe a
lower bound for the problem and a Branch and Bound procedure with
constraint propagation. Experimental results on real life and randomly
generated instances are reported.
Ioannis Caragiannis
Title: Approximation algorithms for path coloring problems
Abstract:
Motivated by the wavelength assignment problem in
WDM optical networks, we study path coloring
problems in graphs. Given a set of paths $P$ on a
graph $G$, the path coloring problem is to color
the paths of $P$ so that no two paths traversing
the same edge of $G$ are assigned the same color
and the total number of colors used is minimized.
The problem has been proved to be NP-hard even for
trees and rings.
Using optimal solutions to fractional path
coloring, a natural relaxation of path coloring,
on which we apply a randomized rounding technique
combined with existing coloring algorithms, we
obtain new upper bounds on the minimum number of
colors sufficient to color any set of paths on
any graph. The upper bounds are either existential
or constructive. Our results extend to variations
of the original path coloring problem arising in
multifiber WDM optical networks.
Andrea Clementi
Title: Asymptotical Cost and Good Heuristics for the
Bounded-Hop MST on the Plane
Abstract:
Given a finite set $S$ of points (i.e. nodes)
on the $2$-dimensional Euclidean space, a root node $b \in S$, and
a positive integer $1\le h \le |S|-1$, an
$h$-hops MST $T_{h}(S)$ is a spanning tree for $S$, rooted at
$b$, such that its
height (depth) is at most $h$ and its total cost (i.e. the sum
of the edge weights) $\mis(T_{h}(S))$ is minimal. The weight of the
edge $(i,j)\in T_{h}(S)$ equals the Euclidean distance $d(i,j)$.
Two main issues related to this fundamental problem are
investigated in this paper:
the asymptotical behaviour of the $\mis(T_{h}(S))$
function and the approximation ratio of a new simple algorithm.
As for the first issue, we provide a general lower bound
on $T_{h}(S)$ for constant $h$. The
lower bound is a function of $|S|$, $h$ and the minimum distance
over all the pairs of stations in $S$. Then, we derive
an upper bound as a function of
$|S|$, $h$ and the maximum distance over all pairs of stations
in $S$ (i.e. {\em the diameter} of $S$).
It turns out that, when the minimum distance between any two stations
is ot too small'' (i.e. well-spread instances), the upper bound
matches the lower bound.
As for the second issue, we observe that our upper
bound is obtained via a simple Divide et Impera procedure.
Furthermore, the lower bound holds for \emph{any} instance.
These two facts implies that our problem, restricted to "well-spread"
instances, yields a simple polynomial-time approximation algorithm.
Besides having a \emph{per-se} interest, well-spread
instances are strongly-related to uniformly-distributed random
instances.
We indeed show that our simple algorithm achieves
asymptotically-optimal expected approximation
ratio over such input model as well.
The performances of our algorithm are also compared to
other heuristics proposed in the literature
(i.e. some naturalal adaptation of the Prim's algorithm).
Intensivea experimental tests show that our algorithm has
the best average cost. This property
is also argumented by a suitable probabilistic analysis.
JOINT WORK with Miriam DI IANNI, Angelo MONTI, Gianluca ROSSI,
and Riccardo SILVESTRI.
Guy Even
Title: Conflict-Free Colorings of Simple Geometric Regions
with Applications to Frequency Assignment in Cellular Networks
Abstract:
Motivated by a frequency assignment problem in cellular networks, we
introduce and study a new coloring problem that we call \emph{Minimum
Conflict-Free Coloring} (Min-CF-Coloring). In its general form, the
input of the Min-CF-coloring problem is a set system $(X,{\cal S})$,
where each $S \in {\cal S}$ is a subset of $X$. The output is a colorin
$\chi$ of the sets in ${\cal S}$ that satisfies the following constrain
for every $x \in X$ there exists a color $i$ and a unique set $S \in
{\cal S}$, such that $x \in S$ and $\chi(S) = i$. The goal is to
minimize the number of colors used by the coloring $\chi$.
Min-CF-coloring of general set systems is not easier than the classic
graph coloring problem. However, in view of our motivation, we
consider set systems induced by simple geometric regions in the plane.
We present CF-coloring algorithms for circles and squares that use
$O(\log n)$ colors (where $n$ is the number of regions). For
rectangles and hexagons we obtain a constant-ratio approximation
algorithm when the ratio between the largest and smallest region is
constant. We also show that, even in the case of unit disks,
$\Theta(\log n)$ colors may be necessary.
Joint work with Zvi Lotker, Dana Ron, and Shakhar Smorodinsky.
Alexei Fishkin
Title: Large resources in maximizing the weight of rectangles
packed into a rectangle
Abstract:
We study the problem of packing a list of $n$ rectangles with weights
into a dedicated rectangle so that the weight of rectangles packed is
maximized.
We consider the case of large resources, that is, the rectangle widths
and heights are in $(0,1]$, and for the dedicated rectangle its width
is unit $1$ whereas its height is at least $1/\eps^4$,
for a positive $\eps>0$. We present an algorithm which finds a packing
of a sublist of rectangles whose total weight is at least ($1-\eps$)
of the optimum.
The running time of the algorithm is polynomial in $n$ and $1/\eps$.
Pierre Fraigniaud
Title: A Survey of Routing in Small Worlds
Abstract:
This talk will survey the recent results related to routing in
augmented graphs. From the seminal work of Kleinberg, we will mostly
concentrate our attention on d-dimensional meshes augmented with links
chosen at random. Greedy routing in these graphs aims at modeling the
behavior of entities looking for information in a societal network,
and at giving formal support to Milgram's experiment. The many
different types of greedy routing strategies will be surveyed, and
their applications to the design of overlay networks for P2P
applications discussed.
Sudipto Guha
Title: Time indexed Linear programming relaxations for scheduling problems
Abstract:
In this talk we will explore time indexed linear programming
formulations for scheduling problems. In particular we would foucus on
problems. First we will consider Throughput maximization and subsequent
we will focus on machine minimization. We will present contant factor
approximations for both problems.
Klaus Jansen
Title: Approximation algorithms for mixed fractional
packing and covering problems
Abstract:
We propose an approximation algorithm based on the Lagrangian
or price directive decomposition method to compute an $\epsilon$ -
approximate solution of the mixed fractional packing and covering
problem: find $x \in B$ such that $f(x) \le (1+\epsilon)a$,
$g(x) \ge (1 - \epsilon)b$ where $f, g$ are vectors with $M$
nonnegative convex and concave functions, $a, b$ are $M$ - dimensional
nonnegative vectors and $B$ is a convex set that can be queried by a
feasibility oracle of the form: find $\hat{x} \in B$ with
$p^T f(\hat{x}) \le q^T g(\hat{x}) + \alpha$. We propose an algorithm
that needs only $O(M (\epsilon^{-2} \ln \epsilon^{-1} + \ln M))$
iterations or calls to the oracle. The main contribution is that the
algorithm solves the general mixed fractional packing and covering
problem (in contrast to pure fractional packing and pure fractional
covering problems) and runs in time independent of the so-called width
of the problem.
Christos Kaklamanis
Title : Energy-Efficient Communication in Ad Hoc Wireless Networks
Abstract:
Efficiently supporting communication patterns that are common in
traditional (wired) networks is an important problem in ad hoc wireless
network as well. These patterns include broadcasting, multicasting,
gossiping (all-to-all communication), and multiconnectivity. Since
establishing communication in ad hoc wireless networks strongly depends on
the use of energy, the important question to be solved is to guarantee a
desired communication pattern minimizing the total energy consumption.
Depending on the properties of the desired communication pattern, we
define and discuss a series of communication problems where the
minimization of energy is the main concern.
Claire Kenyon
Title: Approximation schemes for multidimensional packing
Abstract:
We consider a classic multidimensional generalization of the bin packin
problem, namely, packing d-dimensional rectangles into the minimum numb
of unit cubes. Our two results are: an asymptotic polynomial time
approximation scheme for packing d-dimensional cubes into the minimum
number of unit cubes and a polynomial time algorithm for packing
rectangles into at most OPT bins whose sides have length $(1 + \eps)$,
where OPT denotes the minimum number of unit bins required to pack the
rectangles. Both algorithms also achieve the best possible additive
constant term. For cubes, this settles the approximability of the probl
and represents a significant improvement over the previous best known
asymptotic approximation factor of $2 - (2/3)^d + \eps$. For rectangles
this contrasts with the currently best known approximation factor of
1.691....
This is joint work with Jose Correa.
Samir Khuller
Title: Algorithms for Data Migration with Cloning
Abstract:
Our work is motivated by the problem of managing data on storage
devices, typically a set of disks. Such storage servers are used as
web servers, or multimedia servers for handling high demand for data.
As the system is running, it needs to dynamically respond to changes
in demand for different data items. In this work we study the data
migration problem, which arises when we need to quickly change one
storage configuration into another. We show that this problem is
NP-hard. In addition, we develop polynomial time approximation
algorithms for this problem and prove a worst case bound of 9.5
on the approximation factor achieved by our algorithm. We also compare
the algorithm to several heuristics for this problem.
Joint work with Yoo Ah Kim and Justin Wan.
Seffi Naor
Title: A General Approach to Online Network Optimization Problems
Abstract:
We study a wide range of online graph and network optimization
problems, focusing on problems that arise in the study of
connectivity and cuts in graphs. In a general online network
design problem, we have a communication network known to an
on-line algorithm in advance. What is not known in advance are the
bandwidth or connectivity demands between nodes in the network.
The demands (or requests) are given to the online algorithm one by one.
We consider several calssical
network design problems in this framework, among
them: the set cover problem, non-metric facility location
problem, the multicast tree problem, and the group Steiner problem.
Our algorithms are based on a
unified framework for designing online algorithms for problems
involving connectivity and cuts. We first present a general
$O(\log m)$-deterministic algorithm for generating a fractional
solution that satisfies the online connectivity or cut demands,
where $m$ is the number of edges in the network. This may be of
independent interest for solving fractional online bandwidth
allocation problems, and is applicable to node versions as
well. The integral solutions are obtained by an online rounding of
the fractional solution, and we obtain randomized
polylogarithmic competitve factors for the problems we consider.
This part of the framework is problem dependent, and applies
various tools including results on the
approximate max-flow min-cut for multicommodity flow, the HST
method and its extensions, certain rounding techniques for
dependent variables, and Raecke's new hierarchical decomposition
of graphs.
Joint work with: Noga Alon, Baruch Awerbuch, Yossi Azar, and
Niv Buchbinder.
Pino Persiano
Title: Truthful Mechanisms for Scheduling Verifiable Related Machines
Abstract:
We study the problem of mechanism design for
scheduling related machines owned by selfish agents that
keep as private information the speed of the machines.
We show that, if agents can lie in one direction
(that is they are only allowed to declared to be faster than they
actually are or to be slower) then any (polynomial-time)
$c$-approximation algorithm, for the optimization problem without
selfish agents, can be turned into a (polynomial-time)
$c(1+\epsilon)$-approximation truthful
mechanism, for any $\epsilon >0$.
We also consider the model in which payments are given to the agents on
after the machines have completed the jobs assigned.
This means that for each machine that receives at least one job,
the mechanism can verify if the corresponding agent declared
a greater speed.
For this setting, we characterize the allocation algorithms $A$ that ad
payment function $P$ such that $M=(A,P)$ is a truthful mechanism.
In addition, we give a $(1+\epsilon)$-approximation truthful
mechanism for the case in which machine speeds are bounded by a
constant.
Kirk Pruhs
Title: Scheduling to Minimize Energy Usage and Heat
Abstract:
Energy usage and heat are quickly becoming limiting factors in the
design of computational devices as the power usage of
these devices increase. The energy in batteries in mobile devices
(such as your laptop) is growing at a much slower rate than processor
speeds and power usage,
thus making conserving energy ever more important. Processors are requi
ever big fans and more elaborate schemes to cool them.
There are many different techniques being developed to attack these pro
One of these techniques is dynamic voltage scaling, that is, the proces
may be run at different speeds. Most laptops now come with multi-speed
processors.
As power is approximated by the processor speed cubed, slowing down the
processor when possible can greatly extend the life of the battery,
as well as allowing less expensive cooling methods.
In a traditional scheduling problem, the scheduler has to determine whi
job to run at each point in time. In the setting of a multi-speed proce
the scheduler also has to determine at what speed/power to run the
processor at each time. This leads to dual criteria scheduling problems
That is, one wants to maximize the Quality of Service (QoS) while
minimizing the heat/energy.
There is relatively little literature on these problems to date.
I'll survey what is known, and will highlight open problems that
I believe are interesting.
Adi Rosen
Title: On Delivery Times in Packet Networks under Adversarial Traffic
Abstract:
We consider packet networks and make use of the `adversarial queuing
theory'' model introduced by Borodin et al. In this model, packet
injection into the network is modeled as being done by an adversary,
which is characterized by a "rate". The rate can be informally
described as the average number of packets injected per time step and
for any given communication link.
We are interested in the question of guaranteeing that all packets are
actually delivered to destination, and of having an upper bound on the
delivery times of all packets. Whether this is possible against all
rate-$1$ adversaries (i.e., adversaries that use the full bandwidth of
the network) was previously posed as an open question.
Among other, we give a queuing policy that guarantees bounded delivery
time whenever the rate-$1$ adversary itself can deliver all packets in
bounded time and adheres to certain additional conditions. On the
negative side we show that even the adversary itself cannot deliver
all packets in bounded time for all rate-$1$ sequences of packets. We
thus answer an open question posed by Gamarnik \cite{G}. We further
show that delivering {\em all} packets while maintaining stability (we
coin the term `reliability'' for this property) can be done by an
offline scheduler whenever the injection of packets is done at rate of
at most $1$. Thus any rate-$1$ adversary can have this property. But,
on the other hand, we also show that there is no online protocol (even
centralized) that can achieve that property against all rate-$1$
adversaries. We thus answer an open question of Borodin et al.
\cite{BKR+}.
Joint work with Michael Tsirkin.
Baruch Schieber
Title: Online QoS Buffer Management
Abstract:
We study the behavior of algorithms for scheduling
transmission of packets
weighted by different levels of Quality of Service (QoS) guarantees usi
a single queue. Buffer space is limited, and packet loss occurs when t
buffer overflows. We describe a modification of the previously propose
"preemptive greedy'' algorithm of for buffer management and give an
analysis to show that this algorithm achieves a competitive ratio of at
most 1.75. This improves upon recent work showing a 1.98 competitive
ratio, and a previous result that shows a simple greedy
algorithm has a competitive ratio of 2.
This is joint work with Nikhil Bansal, Lisa Fleischer, Tracy Kimbrel,
Mohammad Mahdian and Maxim Sviridenko
Martin Skutella
Title: Online Scheduling with Bounded Migration
Abstract:
Consider the classical online scheduling problem where jobs that
arrive one by one are assigned to identical parallel machines with
the objective of minimizing the makespan. We generalize this
problem by allowing the current assignment to be changed whenever a
new job arrives, subject to the constraint that the total size of
moved jobs is bounded by $\beta$ times the size of the arriving job.
Our main result is a linear time line approximation scheme', that
is, a family of online algorithms with competitive
ratio $1+\epsilon$ and constant migration factor $\beta(\epsilon)$,
for any fixed $\epsilon>0$. This result is of particular importance
if considered in the context of sensitivity analysis: While a newly
arriving job may force a complete change of the entire structure of
an optimal schedule, only very limited Local' changes suffice to
preserve near-optimal solutions. We believe that this concept will
find wide application in its own right.
We also present simple deterministic online algorithms with
migration factors $\beta=2$ and $\beta=4/3$, respectively. Their
competitive ratio $3/2$ beats the lower bound on the performance of
any online algorithm in the classical setting without migration. We
also present improved algorithms and similar results for closely
related problems. In particular, there is a short discussion of
corresponding results for the objective to
maximize the minimum load of a machine. The latter problem has an
application for configuring storage servers that was the original
motivation for this work.
This is joint work with Peter Sanders and Naveen Sivadasan.
Denis Trystram
Title: " Open questions on scheduling for grid computing"
by L. Eyraud, G. Mounie and D. Trystram
Abstract:
This talk will review the main existing approaches for
efficient scheduling of parallel algorithms on new execution supports
(cluster, grid and global computing).
We will survey many open questions, including discussion about objectiv
functions.
Wolf Zimmermann
Title: Hierarchical Task Scheduling and Compilers
Abstract:
We show how task-scheduling techniques can be integrated
into compilers for parallel languages.
Such an integration allows to compile parallel
languages without the need for explicit definition of data distributions
and control-flow parallelism. Our approach is robust when libraries are
used. The key technique is the use of hierarchically scheduling
malleable tasks, i.e., tasks that can be executed on several processors.
(Joint work with Welf Loewe)
|