Algorithms Reading Group Fall 2003

Venue - B13 MLH
Time - 12:30 - 1:30

Date	Speaker	Topic
4th September 2003	Bruno Codenotti	Game theory and Computer Science : Challenges for Algorithmists
11th September 2003	Sriram Pemmaraju	The hardness of the assymmetric k-center problem
18th September 2003	Jarkko Kari	Snake Tiling Problems
25th September 2003	Kasturi Varadarajan	Min-k-enclosing ball
2nd October 2003	Ganesh Venkataraman	An O((\sqrt n)L)-iteration homogenous and self-dual linear programming algorithm
9th October 2003	Kasturi Varadarajan	Market Equilibrium via a Primal-Dual-Type Algorithm
16th October 2003	Benjamin Gum	Clustering with Qualitative Information
23rd October 2003	Sriram Penumatcha	Embedding Series Parallel graphs in l_1
30th October 2003	Rajiv Raman	OPT vs LOAD in Dynamic storage allocation (CANCELLED)
6th November 2003	Eugen Czeizler	The Road Coloring Problem, and The Cerny Conjecture
13th November 2003	Rajiv Raman	Survey of results for Min-Sum Scheduling problems
20th November 2003	CANCELLED
27th November 2003	Thanksgiving Break
4th December 2003	Sriram Pemmaraju	A 2-approximation for the Steiner network problem
11th December 2003	Bruno Codenotti	Some problems at the intersection between linear algebra and combinatorics

Abstracts

Bruno Codenotti (4/9/2003)
In this talk I will describe several algorithmic questions arising from Game Theory.
I will introduce some of the most important recent results, and raise some open questions.
I will also give pointers to the relevant papers (that I am aware of).
The topics will include
-- Algorithms for the computation of a Nash Equilibrium in bimatrix games,
-- Algorithms for market equilibria,
-- Finding equilibria for congestion and load-balancing games,
-- Computing relevant parameters in weighted majority games,
-- Solving facility location and other network design problems.

Sriram Pemmaraju (11/9/2003)
The Hardness of the Asymmetric k-center problem

The k-center problem takes as input a bound k and n points and seeks
a set of k points to serve as centers so that the maximum distance of
any point from the centers is minimized. This problem is NP-hard and
has a 2-approximation.

In the asymmetric k-center problem, dist(p, q) may be distinct from
dist(q, p). Since 1998 an O(log^*(n))-approximation algorithm has been
known for this problem. In a very recent breakthrough result, it has been
shown that the asymmetric k-center problem is (1 - o(1))log^*(n) hard
to approximate. This is the first natural optimization problem whose
approximability threshold does not polynomially relate to the known
approximation classes.

I will describe this hardness of approximation result. This is due to
Chuzhoy, Guha, Halperin, Khanna, Kortsarz, Krauthgamer, and Naor.

Jarkko Kari (18/9/2003)
Snake tiling problems

The snake tiling problem takes as input a finite set of Wang tiles
(=square tiles with colored edges) and asks whether it is possible
to form an infinite "snake" using copies of these tiles, where
consecutive tiles of the snake must match in color in their adjacent
edges. I discuss variants of this problem, and outline a proof showing
the undecidability of these questions.

The snake tiling problems were first brought-up more than a decade ago
in a paper by Harel et.al. Recently the same questions came up in
a new context when Adleman et.al started using Wang tiles as a
mathematical model of the self-assembly process of molecules.

Kasturi Varadarajan (9/25/2003)
Min-k-enclosing ball

Given a set of n points in the plane and an integer k between 1 and n,
we want to compute the smallest radius ball that contains at least
k of the set of n points. We describe an O(n)-time (randomized) algorithm
due to Mazumdar and Har-Peled (from ESA'03) that computes a ball
containing k points whose radius is at most twice the optimal. This
improves over a previous O(n log n)-time algorithm.

The paper can be accessed from
http://valis.cs.uiuc.edu/~sariel/research/papers/

Ganesh Venkatraman(10/03/2003)
An O((\sqrt n)L)-iteration homogenous and self-dual linear programming algorithm

We present an O(n^1/2*L)-iteration homogeneous self-dual linear
programming (LP) algorithm which solves the problem without any regularity
assumptions concerning the existence of optimal, feasible or interior
solutions. The result is due to Ye, Todd and Mizuno.

Kasturi Varadarajan (10/09/2003)
Market Equilibrium via a Primal-Dual-Type Algorithm

Although the study of market equilibria has occupied centerstage
within Mathematical Economics for over a century, polynomial time
algorithms for such questions have so far evaded researchers.
We discuss the first such algorithm for the linear version of a
problem defined by Fisher in 1891. The algorithm, due to Devanur,
Papadimitriou, Saberi, and Vazirani, is modeled after Kuhn's
primal-dual algorithm for bipartite matching.

The paper appeared in FOCS 02 and is available at Vijay Vazirani's
web-page:
http://www.cc.gatech.edu/fac/Vijay.Vazirani/

Ben Gum (19/10/2003)
Clustering with Qualitative Information

We consider the problem of clustering a collection of elements based on
pairwise judgments of similarity and dissimilarity. Bansal, Blum and Chawla
cast the problem thus: given a graph G whose edges are labeled "+" (similar)
or "-" (dissimilar), partition the vertices into clusters so that the number
of pairs correctly (resp incorrectly) classified with respect to the input
labeling is maximized (resp minimized). Complete graphs, where the classifier
labels every edge, and general graphs, where some edges are not labeled, are
both worth studying. We answer several questions left open in the paper of
Bansal et al.

In this presentation I will show a factor 4 approximation algorithm for
minimization on complete graphs, and a factor O(log n) approximation for
general graphs. For the maximization version, a PTAS (polynomial time
approximation scheme) for complete graphs is shown by Bansal et al.; I will
demonstrate a factor 0.7664 approximation for general graphs, using
semi-definite programming. If time permits, I will summarize the reductions
used in showing that some of these problems are APX-hard.

This is work of Tony Wirth, Moses Charikar and Venkatesan Guruswami from FOCS
2003.

Sriram Penumatcha(23/10/2003)
L_1 Embedding of Series-Parallel graphs

In this talk I will talk about constant distortion
embeddings of all series-parallel graphs.These are
the first natural families known to have constant
distortion.

This is part of the results from the paper:
Cuts Trees and L1 embeddings of Graphs - Gupta, Newman, Rabinovich,
Sinclair.

Rajiv Raman (30/10/2003)
OPT vs LOAD in dynamic storage allocation

Dynamic storage allocation is the problem of packing rectangles into a
horizontal strip of minimum height by sliding the rectangles vertically
but not horizontally. LOAD is the maximum sum of heights of rectangles
that intersect a given vertical line, and OPT is the minimum height of the
enclosing strip. I will present a 2 - \epsilon approximation result for
this problem.

The result is by Adam L. Buschbaum, Howard Karloff, Claire Kenyon, Nick
Reingold, and Mikkel Thorup.

The result appeared in STOC 2003.

Eugen Czeizler(11/4/2003)
The Road Coloring Problem, and The Cerny Conjecture

Cerny's Conjecture and The Road Coloring Problem are two open
problems concerning synchronization of finite automata.

We say that a finite automata is syncronizable if there exist a word w
such that starting from any state q of the underlayed directed graph and
applying the transitions determined by w, we reach an unique node. Such a
w is called a syncronizing word.

Our first problem conjecture the existence of a syncronizing word w of
length at most (n-1) square, for each syncronized automaton, where n is
the number of states of the automaton.

The Road Coloring Problem asks whether a syncronized coloring exists for
every directed graph which is aperiodic and strongly connected.

Both problems have been solved in some special cases, but the general case
remains open. The presentation will show some of the cases in which the
problems have been solved, as well as an (easy to obtain) cubic upper
bound for the smallest syncronizing word.

Rajiv Raman (11/13/2003)
Survey of results Min-Sum criteria Scheduling problems

Scheduling problems with the objective of minimizing sum of completion times or the average completion time have been one of the hardest
scheduling problems to solve. Recently however, some techniques have led to satisfactory answers to these problems. In this talk, I will present
a constant factor bound for scheduling a set of jobs with release dates on parallel machines, and also present a PTAS for the problem on single and parallel
machines.

Sriram Pemmaraju (12/3/2003)
A 2-approximation for the Steiner network problem

Kamal Jain (Combinatorica, 2001) presents a factor 2 approximation for the
Steiner network problem. The techniques used include iterated rounding of
an LP solution, and certain polyhedral facts relating to submodular
functions. I will present these results.

Bruno Codenotti (12/11/2003)
Some problems at the intersection between linear algebra and combinatorics
I will describe some results and open questions related to
-- the construction of graphs with certain extremal
algebraic properties;
-- the Shannon capacity of odd cycles.