 |
- Talks: Winter 2004 -
"Talks are generally held on Wednesdays,
from 10:10-11:30am in Surge 349."
|
| Date |
Speaker |
Topic |
| Jan. 07 |
Jing Li |
Title:
"Efficient Haplotype Inference on Pedigrees and Applications"
Ref: Extended Abstract
|
| Jan. 14 |
Marek Chrobak |
Title:
"The Wake-Up Problem in Multi-Hop Radio Networks"
Ref: M. Chrobak, L.Gasieniec, D.Kowalski
from Proc. SODA'2004
|
| Jan. 21 |
Marek Chrobak |
Title:
"The Analysis of the Greedy Algorithm for Minimum Common String Patrition"
Ref: Work in Progress
|
| Jan. 28 |
Neal Young |
Title:
"Lagrangian relaxation via randomized rounding"
Abstract:
Lagrangian relaxation algorithms have a long history (dating back at
least to von Neumann). These algorithms are used mainly to find
approximate solutions to packing and covering problems -- linear
programs and integer linear programs, with non-negative coefficients.
The algorithms build a solution in small steps, guided by a smooth
penalty function that serves as a proxy for some of the underlying
constraints of the original problem. In comparison to other methods of
solving linear programs, Lagrangian relaxation algorithms can be easier
to implement and faster, and they handle sparse problems gracefully.
These algorithms have been extensively studied over the last 15 years.
Their design and analysis is fairly technical. For example, designing
the appropriate penalty functions is something of a black art.
In the talk I will introduce a particular approach to the design of one
class of Lagrangian relaxation algorithms (corresponding roughly to
algorithms developed in the computer science literature over the last
fifteen years). I will introduce techniques that help both to
understand existing algorithms (including the underlying techniques and
the relationships between the algorithms), and to design and analyze
new algorithms
The framework for this is randomized rounding -- an elegant technique,
based on the probabilistic method, for designing approximation
algorithms for combinatorial problems. This is a novel approach to
Lagrangian relaxation algorithms and a novel use of randomized
rounding, using a new kind of randomized rounding scheme based on
random sampling.
More information available at
http://www.cs.ucr.edu/~neal/wiki/wiki.pl?LRviaRR
|
| Feb. 4 |
Jie Zheng |
Title:
"Complexity and Approximation of Minimum Common Partition"
Ref: Work in Progress
|
| Feb. 11 |
Keith Humphreys |
Title:
"Approximate Quantiles in One Pass with Limited Memory"
Ref:
Approximate Medians and other Quantiles in One Pass and with Limited Memory,
by G S Manku, S Rajagopalan and B G Lindsay,
Proc. 1998 ACM SIGMOD, Vol 27, No 2, p 426-35, June 1998.
Slides from talk here
|
| Feb. 18 |
Haifeng Li |
Title:
"A Class of Edit Kernels for SVMs to Predict Translation Initiation Sites in Eukaryotic mRNAs"
Ref:
|
| Feb. 25 |
Qiaofeng Yang |
Title:
"Finding biclusters by random projections"
Ref: Work in Progress
|
| Mar. 3 |
Wojciech Jawor |
Title:
" Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs"
(joint work with Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Ron Lavi, Jiri Sgall and Tomas Tichy)
Abstract:
We will consider an online problem of scheduling unit length
jobs to maximize the weighted throughput. Each job will be specified by
the release time, deadline, and weight. The goal of the algorithm is to
schedule the maxium weighted number of jobs. Each job needs to be
scheduled between its release time and deadline, otherwise it brings no
profit. In the problem jobs arrive over time and the algorithm needs to
make the decision of which job to schedule without the knowledge of the
future. I will show upper and lower bounds for the problem, as well as
some known results on some special cases of the problem.
|
| Mar. 10 |
John Noga |
Title:
"Online List Batching"
Ref:
|
|
|
|