Algorithms Seminar
Amos Fiat and Yishay Mansour |
We
meet every Monday at 16:10 in Schreiber 309. Talks usually last until 17:30.
Seminar schedule also appears in Google calendar (look for "algorithms
seminar at Tel Aviv University). For more information, or to join the mailing
list, please send an email to Uri Nadav, or
subscribe to google calendar: "Algorithms seminar at
Tel Aviv university".
|
Date |
Speaker |
Title |
|
2007/02/26 |
Competitive analysis of on-line least squares
forecasts |
|
|
2007/03/05 |
The
Strategic Justification for BGP |
|
|
2007/03/12 |
TBA |
|
|
2007/03/19 |
Broadcasting
in UDG Radio Networks with Unknown Topology |
|
|
2007/03/26 |
An
Approach to Bounded Rationality |
|
|
2007/04/02 |
Passover |
|
|
2007/04/09 |
Passover |
|
|
2007/04/16 |
||
|
2007/04/23 |
Yom Hazikaron |
|
|
2007/04/30 |
The
Dominating Set Problem in Planar Graphs |
|
|
2007/05/07 |
Amir Epstein |
|
|
2007/05/14 |
Elias Koutsoupias |
|
|
2007/05/21 |
Michal Feldman |
|
|
2007/05/28 |
|
|
|
2007/06/04 |
Gil Shallom |
|
Abstracts
Title:
Competitive analysis of on-line least squares forecasts
Abstract:
The problem of on-line prediction is try to predict an arbitrary
sequence of numbers about as well as can be done if you had seen all
the data ahead of time. Of course, to make this a "fair"
problem, we
will have to restrict the possible after-the-fact forecasts. This
talk will use the easiest possible loss function--namely least
squares. I will focus on some new spin-offs of this theory. In
particular, it is easy to show that a weakly calibrated forecast
exists.
(joint with Sham Kakade)
Title: The Strategic Justification for BGP
Abstract:
The Internet consists of many administrative domains, or Autonomous
Systems (ASes), each owned by an economic entity. The task of ensuring
connectivity between ASes is currently handled by the Border Gateway Protocol
(BGP). ASes are self interested and might be willing to manipulate the protocol
if they stand something to gain by doing so.
We consider the realistic Gao-Rexford constraints, that are known to guarantee
robust BGP convergence. The Gao-Rexford setting is said to accurately depict the
business relationships between ASes in today's Internet. We show that BGP can
be rationally manipulated even if the Gao-Rexford constraints hold. In
contrast, we show that a slight modification of BGP is incentive-compatible
(no AS has rational motivation to unilaterally deviate from BGP). Moreover, we
show that if a certain reasonable condition holds, then BGP is also collusion-proof (i.e., immune
to rational manipulations even by coalitions
of ASes of any size).
Unlike most previous
works on incentive-compatibility in interdomain routing (and the vast majority
of works in mechanism design), our results do not require any monetary transfer between the strategic agents (as
is the case in practice), and can be regarded as the strategic justification for using BGP in
practice.
Based on
joint work with Hagay Levin and Aviv Zohar (see http://www.cs.huji.ac.il/
Title:
Frugality in set system auctions: an overview
Abstract: In set-system auctions, there is a
task than can be completed
by several overlapping teams of selfish agents, and the center's goal is
to hire one of these teams and pay as little as possible. Examples of
this setting include shortest path auctions, minimum spanning tree
auctions, and vertex cover auctions. Recently, Karlin, Kempe and Tamir
introduced a new definition of {\em frugality ratio} for this problem.
Informally, the ``frugality ratio'' is the ratio of the total payment of
a mechanism to a desired payment bound. The ratio captures the extent to
which the mechanism overpays, relative to perceived fair cost. In this
talk, we discuss several alternative definitions of frugality ratio, and
recent lower and upper bounds on frugality ratio for various classes of
set systems.
References:
1. Elkind, Sahai, Steiglitz
Frugality in path auctions (SODA'04)
2. Karlin, Kempe, Tamir
Beyond VCG: frugality of truthful mechanisms (FOCS'05)
3. Elkind, L.A.Goldberg, P.W.Goldberg
Frugality ratios and improved truthful mechanisms for vertex cover (EC'07)
Title:
Broadcasting in UDG Radio Networks with Unknown Topology.
Abstract:
We consider
broadcasting in radio networks, modeled as unit disk
graphs (UDG). Network stations are modeled as points in the plane,
where a station is connected to all stations at Euclidean distance at
most 1 from it. A message transmitted by a station reaches all its
neighbors, but a station \emph{hears} a message (receives the message
correctly) only if exactly one of its neighbors transmits at a given
time step. One station of the network, called the \emph{source}, has a
message which has to be disseminated to all other stations. Stations
are unaware of the network topology. Two broadcasting models are
considered. In the \emph{conditional wake up} model, the stations
other than the source are initially idle and cannot transmit until
they hear a message for the first time. In the \emph{spontaneous wake
up} model, all stations are awake (and may transmit messages) from the
beginning.
It turns out that the running time of deterministic broadcasting
algorithms depends on two parameters of the UDG network, namely, its
diameter $D$ and its \emph{granularity} $g$, which is the inverse of
the minimum Euclidean distance between any two stations. We present a
deterministic broadcasting algorithm which works in time $O(D g)$
under the conditional wake up model. On the negative side, we prove
that any deterministic algorithm requires $\Omega(D \sqrt{g})$ time to
accomplish broadcasting. For the spontaneous wake up model, we
establish a lower bound of $\Omega(\min\{D + g2, D \log{g}\})$ on
deterministic broadcasting time and prove that this is tight. Thus our
results yield a provable separation between the two models: for some
parameter values, the lower bound in the first model is significantly
larger than the upper bound in the second.
Title:
An Approach to Bounded Rationality
Abstract:
Title: Two Simplified Proofs for
Roberts' Theorem
Abstract:
Roberts
(1979) showed that any social choice function that is
truthfully implementable must be weighted VCG, i.e. maximizes the
weighted social welfare. We provide two simplified proofs for this.
The first proof uses the same underlying key-point, but significantly
simplifies the technical construction around it, thus helps to shed
light on it. The second proof shows how Rochet's cycle monotonicity
characterization (that describes the effect of every individual
player on the social choice function) implies the \u201dglobal\u201d
constraint of affine maximization in unrestricted domains.
If time permits I'll describe some new related results referring to
discrete domains.
(joint with Ron Lavi and Noam Nisan)
Title:
Abstract:
Speaker: Amir Epstein
Title:
Abstract:
Speaker: Gil Shalom
Title: On the Value of Preemption in
Scheduling
Abstract:
Speaker: Michal Feldman
Title:
Abstract:
<