Algorithms Reading Group Fall 2004

Venue : B-13 MLH
Time : 10:00 am to 11:00 am
Days : Tuesdays

If you would like to speak, please send e-mail to rraman at cs dot uiowa dot edu.

Date	Speaker	Topic
8/31/2004	Sriram Pemmaraju	Upper Bounds on Total Chromatic Number
9/7/2004	Rajiv Raman	Tight bounds for dynamic storage allocation
9/14/2004	Saurav Pandit	End-to-End Packet-Scheduling in Wireless Ad-hoc Networks
9/21/2004	Saurav Pandit	End-to-End Packet-Scheduling in Wireless Ad-hoc Networks (cond...)
9/28/2004	CANCELLED	??
10/5/2004	Ben Gum
10/12/2004	Kasturi Varadarajan	Iterative algorithm of Garg and Kapoor (STOC 04) for computing an approximate equilibrium in an exchange market with linear utilities.
10/19/2004	Ben Gum	An exact subexponential-time lattice algorithm for Asian options
	Rajiv Raman	Improved Bounds for the Sum Multicoloring Problem
	CANCELLED
11/9/2004	Saurav Pandit	Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
11/16/2004	Wenli He
11/29/2004	Shouxi Yang	Winner Determination in Combinatorial Auctions

Seminars from previous semesters: Spring 2004, Fall 2003

Abstracts

(8/31/2004) Sriram Pemmaraju
Upper Bounds on Total Chromatic Number

In a total coloring of a graph, each vertex and each edge receives a color
so that no two adjacent vertices get the same color and no two edges
incident on the same vertex get the same color. The total chromatic number
of a graph is the minimum number of colors needed for a total coloring.
An easy upper bound on the total chromatic number of a graph is 2 \Delta +
1, where \Delta is the maximum vertex degree of the graph.

Behzad and Vizing have independently conjectured that \Delta + 2 is an
upper bound on the total chromatic number of a graph. In a series of
papers using the probabilistic method, Hind, Molloy, and Reed have shown a
\Delta + poly(log \Delta) upper bound (SIAM J. Computing 1998) and a
\Delta + c upper bound (Combinatorica 1998). In this talk, I will describe
how the \Delta + poly(log \Delta) upper bound is obtained.

(9/7/2004) Rajiv Raman
Tight bounds for dynamic storage allocation.
Dynamic storage allocation is the problem of allocation of a
one-dimensional storage to proceses in a dynamic environment. At the time
of arrival of a process, it is allocated storage area. This area is
required to form a contiguous location in the storage device. Once
allocated, a process cannot be moved to a different location. At some
later point the process leaves, thereby liberating the storage area it
occupied. The objective is to find an allocation that minimizes the wasted
space. In this talk, I will present upper and lower bounds on the
performance of two online algorithms for this problem.

References :
"Tight Bounds for Dynamic Storage Allocation", Michael Luby, Joseph Naor, Ariel Orda, SIAM Journal of Discrete Mathematics, 9(1): 155-166 (1996)

(9/14/2004)Saurav Pandit
End-to-End Packet-Scheduling in Wireless Ad-hoc Networks
Packet-scheduling is a particular challenge in wireless networks due to
interference from nearby transmissions. A distance-2 interference model serves
as a useful abstraction here, and we study packet routing and scheduling under
this model. The main focus of our work is the development of fully-distributed
(decentralized) protocols. We present polylogarithmic/constant factor
approximation algorithms for various families of disk graphs (which capture the
geometric nature of wireless-signal propagation), as well as near-optimal
approximation algorithms for general graphs. The packet-scheduling work by
Leighton, Maggs and Rao(Combinatorica, 1994) and a basic distributed coloring
procedure, originally due to Luby (J. Computer and System Sciences,
1993), underlie many of our algorithms. Experimental work of Finocchi,
Panconesi, and Silvestri (SODA 2002) showed that a natural modification of
Luby's algorithm leads to improved performance, and a rigorous explanation of
this was left as an open question; we prove that the modified algorithm is
provably better in the worst-case. Finally, using simulations, we study the
impact of the routing strategy and the choice of parameters on the performance
of our distributed algorithm for unit disk graphs.

(10/19/2004) Ben Gum
An exact subexponential-time lattice algorithm for Asian options
by Tian-Shyr Dai and Yu-Dauh Lyuu
from SODA 2004

Asian options are path-dependent derivatives. How to price them
efficiently and accurately has been a long-standing research and practical
problem. Asian options can be priced on the lattice. But only
exponential-time algorithms are currently known if such options are to be
priced on a lattice without approximation. Although efficient
approximation methods are available, most of them lack accuracy
guarantees. This paper proposes a novel lattice for pricing Asian options.
The resulting exact pricing algorithm runs in subexponential time. This is
the first exact lattice algorithm to break the exponential-time barrier.
Because this lattice converges to the continuous-time stock price process,
the proposed algorithm is guaranteed to converge to the desired
continuous-time option value.

(10/25/2004) Rajiv Raman
Improved Bounds for the Sum Multicoloring Problem
The sum-multicoloring problem models scheduling conflicting jobs on a set
of processors. The input is a graph G with positive integral weights on
the vertices. The vertices correspond to jobs, the weights correspond to
processing times and the edges correspond to a conflict between jobs
(i.e., adjacent jobs cannot be scheduled together). The objective is to
find a schedule of the jobs on (unlimited) machines that minimizes the
average completion time of the jobs. This is modeled as a multicoloring
problem on graphs. The vertices are colored with natural numbers such that
adjacent vertices receive as many colors as the weight of the vertex and
adjacent vertices receive disjoint sets of colors. The colors correspond
to the time units when the job runs. The objective is to minimize the sum
of the largest colors assigned to the vertices. In this talk, I will
describe algorithms for sum-multicoloring that use an LP formulation for a
scheduling problem devised by Hall, et. al. ( "Scheduling to Minimize
Average Completion Time : Off-line and On-line Approximation Algorithms",
Math of OR, vol.22, 1997), L.A. Hall, A. Schulz, D.B. Shmoys, J. Wein),
and improve existing bounds for various graph classes.

(11/9/2004) Saurav Pandit
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons" by D.
Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, A. Srinivasan.

Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms
for two problems. Given a network, we first show how to compute connected and weakly connected
dominating sets whose size is at most O(log�� times optimal, ��being the maximum degree of the
input network. This is best-possible if NP != DTIME[n^O(log log n)] and if the processors are limited
to polynomial-time computation. We then show how to construct dominating sets which satisfy the above
properties, as well as the "low stretch" property that any two adjacent nodes in the network have
their dominators at a distance of at most O(log n) in the network. (Given a dominating set S, a
dominator of a vertex u is any v ��S such that the distance between u and v is at most one.) We
also show our time bounds to be essentially optimal.

(11/29/2004) Shouxi Yang
Winner Determination in Combinatorial Auctions

Basically, I am going to to talk about the following points,

1*. Winner determination problem in combinatorial auctions
2*. Branch and Bound method, upper bound and lower bound
3. (Recent experiment using nagging, a technique of parallel
computing)