Algorithms
Reading Group Spring 2004
Venue : B-13 MLH
Time : 2:30 - 3:30 pm
Days : Wednesdays
If you would like to speak, please send e-mail to rraman at cs dot
uiowa dot edu.
Seminars from previous semesters: Fall
2003
Abstracts
Bruno Codenotti (1/28/2004)
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.
Rajiv Raman
(2/11/2004)
Approximating the two-level facility location problem via a
quasi-greedy approach
The 2-level facility location is a generalization of the classical
facility location problem. In the single level facility location
problem,
we are given a set of clients and a set of facilities. We want to open a
subset of the facilities such that all the clieents are served by the
open
facilities, and the total cost of opening facilities and serving clients
is minimized. In the k-level uncapacitated facility location problem,
the
demands must be routed among the facilities in a hierarchical order
before
reaching the clients. We show a 1.77-approximation for the 2-level
facility location problem using a quasi-greedy approach. The algorithm
also has an interesting feature of combining randomized rounding and
dual-fitting".
The result is by Jiawei Zhang, SODA (2004).
Darren Schipper (25/2/2004)
Sub-quadratic Global Alignment of DNA
Sequences
The classical algorithm for computing the similarity between two
sequences
uses a dynamic programming matrix, and compares two strings of size n in
O(n^2) time. We address the challenge of computing the similarity of two
strings in sub-quadratic time, for metrics which use a scoring matrix of
unrestricted weights. Our algorithm applies to both local and global
similarity computations.
The speed-up is achieved by dividing the dynamic programming matrix into
variable sized blocks, as induced by Lempel-Ziv parsing of both
strings, and
utilizing the inherent periodic nature of both strings. This leads to an
O(n^2 / log n) algorithm for an input of constant alphabet size. For
most
texts, the time complexity is actually O(h n^2 / log n) where h <= 1
is the
entropy of the text.
Ben Mccune (3/3/2004)
A Finite Algorithm for the Linear
Exchange Model
It is shown that Lemke's algorithm can be used to compute, in a
finite number of steps, an equilibrium or reduction for the pure
exchange
model with linear utilities. The paper, by B. Curtis Eaves is available
at
http://econpapers.hhs.se/paper/cwlcwldpp/389.htm
Sriram Pemmaraju (3/24/2004)
Online coloring of intervals with
bandwidth
The input is a set of intervals. Each interval has an associated
bandwidth
in [0, 1]. The problem is to find an online algorithm for coloring the
intervals so that the total weight of intersecting intervals in a color
class does not exceed 1. Adamy and Erleback (2003) have presented an
online algorithm for this problem with a competitive ratio of 195. A
part
of their algorithm is a simple first-fit scheme and they analyze this
using Kierstead's centrality approach. I will describe a different
analysis using the column construction procedure (described in a SODA
2004 paper) that shows that reduces the competitive ratio of the
Adamy-Erlebach algorithm to 35.
Rajiv Raman (4/7/2004)
Multicoloring Graphs
Given a graph, with positive integral weights on the vertices, the
multicoloring problem seeks to assign colors from the set of natural
numbers, such that each vertex gets as many colors as it's weight and
the
set of colors assigned to adjacent vertices are disjoint. The objective
function is to minimize the sum or average of the maximum color assined
to
each vertex.
The problem arises in scheduling conflicting jobs on machines. Here the
jobs are represented as vertices of a graph, and the edges represent
jobs
have conflicting requirements. The weight of a vertex represents the
number of units of time required to complete a job. The colors represent
the units of time when a job is run.
I will present results on general graphs and trees, when the jobs can be
preempted, when they cannot be preempted and a coscheduling model where
the jobs must be scheduled in batches. The problem is NP-hard on trees,
and I will present a PTAS for the problem, and highlight the approaches
in
solving the problem on other related classes of graphs.
This combines results from the following papers :
1. "Minimum Sum Multi-coloring of Graphs" (A.Bar-Noy, M.Halldorsson,
G.Kortsarz, R.Salman, H.Shachnai), Journal of Algorithms, 2000
2. "Sum Multicoloring Trees", M.Halldorsson, G.Kortsarz, A.Proskurowski,
R.Salman, H.Shachnai, J.A. Telle, Information and Computation (2003).
3. "Tools for Multicoloring with applications to planar graphs and
partial
k-trees", M.Halldorsson and G.Kortsarz, Journal of Algorithms (2002).
4. "Multicolorings of Series-Parallel Graphs", Xiao Zhou and Takao
Nishizeki, Algorithmica (Vol. 38, #2).
Some related papers are the following :
1. "The complexity of tree multicolorings", D.Marx (MFCS 2002)
2. Sum-multicoloring on paths, A. Kovacs (STACS 2004)