Capital Area Theory Seminar: Fall 2008
Capital Area Theory Seminar: Fall 2008
| The Capital Area Theory Symposia is an UMIACS sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department. |
CATS usually meets on Fridays 1:00pm- 2:00 pm AVW 4185 but some talks may be at a different place and time.
For additional information send email to Samir Khuller.
If you want to receive announcements of upcoming talks join the theory-local mailing list.
|
|
From March 2009 will be a postdoc at EPFL Lausanne.
Budgeted Allocations in the Full-Information Setting.
We build on the work of Andelman & Mansour and Azar,
Birnbaum, Karlin, Mathieu & Thach Nguyen to show that the full information
(i.e., offline) budgeted-allocation problem can be approximated to within 4/3:
we conduct a rounding of the natural LP relaxation, for which our algorithm
matches the known lower-bound on the integrality gap.
Nearest neighbor searching
is a fundamental problem in computational geometry, databases, information
retrieval and pattern recognition. Given a large set of points S in space,
the problem involves preprocessing these points into a data structure so
that, given a query point q, it is possible to rapidly report the closest
point to q. For the sake of efficiency, we consider approximate solutions,
where the user can specify the required degree of accuracy of the final
result.
This problem has been extensively studied in the context of Euclidean
distances, but Euclidean distance is not the most meaningful measure for
many applications. For example, distances between strings are often measured
using edit distance, and distances between geometric shapes are measured
using the earth mover's distance. There has been growing interest in
studying proximity searching in the context of general metric spaces. The
distance function is provided by a black-box function, which returns the
distance between any given pair of points. This function is assumed to
satisfy basic geometric properties, such as the triangle inequality. This
has sparked a great deal of research on the question of how to generalize
data structures for proximity searching in Euclidean spaces to metric
spaces.
In this talk, we will provide a brief tutorial of many of the important
concepts that have been developed recently in the context of proximity
searching in metric spaces. We will discuss the concept of doubling
dimension, which generalizes the notion of dimension in Euclidean spaces. We
will discuss theoretical limitations of the general black-box model for
approximate nearest neighbor searching, and we will introduce a somewhat
more powerful model that allows for more efficient algorithms for nearest
neighbor searching in metric spaces of low doubling dimension.
(This is joint work with Sunil Arya, Jian Xia of the Hong Kong University of
Science and Technology and Antoine Vigneron of INRA, Paris.)
The set-multicover problem differs from the
set-cover problem in that an element now needs to be covered a pre-specified
number of times. In this talk we will present our works on improved randomized
approximations for offline and online versions of this problem, together with a
novel application of this problem to reverse engineering of signal-transduction
networks in biology.
Brief Bio
Bhaskar DasGupta is currently an associate professor in the Computer Science
department at University of Illinois at Chicago (UIC) and also affiliated with
the Bioengineering department at UIC. He did his PhD from University of
Minnesota in 1995, was a post-doctoral fellow at DIMACS and jointly at
University of Waterloo and McMaster University in Canada before he joined the
computer science department of camden campus of Rutgers University; in 2001 he
moved to UIC. His research specific research interests include application of
combinatorial techniques to design efficient algorithms for computational
problems in bioinformatics, systems biology and hybrid systems; his broader
research interests include designing efficient combinatorial algorithms for
computationally hard
problems in diverse areas in addition to bioinformatics such as computational
geometry, VLSI/CAD, parallel computing, optical networks, and combinatorial
auctions. His research works have been supported by numerous NSF grants,
including an NSF CAREER award.
Single-Sink Network Design Problems with Vertex-Connectivity Requirements
Nitish Korula
We study single-sink network
design problems in undirected graphs with vertex connectivity requirements. The
input to these problems is an edge-weighted undirected graph G = (V, E), a
sink/root vertex r, a set of terminals T \subseteq V, and an integer k. The goal
is to connect each terminal t \in T to the root r via k vertex-disjoint paths.
In the connectivity problem, the objective is to find a min-cost subgraph of G
that contains the desired paths. When k=1, this is the well-known Steiner Tree
problem, and there is a 2-approximation for this problem when k \le 2, but for k
\ge 3, the first non-trivial approximation was obtained very recently by
Chakraborty, Chuzhoy and Khanna, who describe and analyze an algorithm with an
approximation ratio of k^{O(k^2)} log^4 n. In this paper, we show a k^{O(k)}
log |T|-approximation bound for a very simple greedy algorithm. Our analysis is
based on the dual of a natural linear program and is of independent technical
interest. We use the insights from this analysis to obtain simple approximation
algorithms for more general problems in which the cost of an edge depends on the
number of terminals that use it.
Our results show that for each of these problems, simple and natural algorithms
that have been developed for k = 1 have good performance for small k > 1.
On coloring edges, covering shortest paths,
and reducing diameter
We formulate a conjecture on
edge colorings of directed graphs, prove special cases and show that it leads to
interesting results on covering shortest paths, which improve the approximation
bound for a problem of augmenting a graph to reduce its diameter.
Iterative relaxation
In this talk we will present an
iterative relaxation method to analyze linear programming formulations of
combinatorial optimization problems. This method was first developed to tackle
degree-bounded network design problems, where it gave approximation algorithms
with only additive constant errors. In particular, it gave an approximation
algorithm with error at most 1 for the minimum bounded degree spanning tree
problem, proving a conjecture of Goemans. Then we will discuss how this method
provides new proofs of exact linear programming formulations for classical
problems, and see how these new proofs lead to new results in approximation
algorithms. Finally we will discuss potential future directions of this method,
and highlight some interesting open problems. This iterative relaxation method
is an extension of Jain's iterative rounding method. We will start this talk
with Jain's method and the necessary background.
Joint work with T. Kiraly, J. Naor, M. Salavatipour, R. Ravi, and M. Singh.
In numerous areas of operations
research and artificial intelligence, we face a problem common to gamblers
choosing slot machines (or bandits) in a casino: whether to try new machines or
keep playing the one we know and hope for the best. More generally, we face the
trade-off between exploration and exploitation: between learning from and
adapting to a stochastic system and exploiting our current best-knowledge. A
fundamental decision-theoretic model that captures this trade-off is the
celebrated Multi-arm Bandit Problem. The basic multi-armed bandit problem admits
to an elegant polynomial time solution. However, many stochastic scheduling
applications can only be modeled using a generalization termed the Restless
Bandit Problem, which in its ultimate generality, is PSPACE-Hard to approximate
to any non-trivial factor.
In this talk, we derive a 2-approximation algorithm for a general subclass of
the Restless Bandit Problem, in which the state-transition probability for each
bandit is "separable" into a constant probability matrix and a vector of
arbitrary monotone functions of time. The monotonicity models increasing levels
of uncertainty as time-since-last-observation increases. We mention applications
of this model to wireless scheduling and unmanned aircraft navigation. The
resulting algorithm is simple and intuitive, and in addition, applicable to
related stochastic scheduling problems.
Joint work with Sudipto Guha, UPenn, and Peng Shi, Duke.
We consider the problem of query rewrites in the
context of keyword advertisement. Given a three-layer graph consisting of
queries, query rewrites, and the corresponding ads that can be served for the
rewrites, we formulate a family of graph covering problems whose goals are to
suggest a subset of ads with the maximum benefit by suggesting rewrites instead.
We obtain constant-factor approximation algorithms for these covering problems,
under two versions of constraints and a realistic notion of ad benefit. We
perform experiments on real data and show that our algorithms are capable of
outperforming a competitive baseline algorithm in terms of the
benefit of the rewrites.
Joint Work with Chi Chao Chang, Ravi Kumar and Grant Wang.
Edge Coloring and Decomposition of Weighted Graphs
Barna Saha
We are given an edge-weighted bipartite graph G=(V,E) with weights w : E -> [0,1]. We consider the following two problems on weighted bipartite graphs: 1. Weighted Bipartite Edge Coloring 2. Balanced Decomposition of Bipartite Graphs In the first problem, we need to obtain a proper weighted coloring of the edges with as few colors as possible. An edge coloring of a weighted graph is called proper, if the sum of the weights of the edges incident on any vertex of the same color is at most one. We will show a polynomial time algorithm to achieve a coloring, which uses ceil(2.25d) colors, where d is the maximum total weight incident at any vertex. In the second problem, we are given a_1,a_2,...,a_k \in (0,1), summing to 1. The task is to find a partition E_1,E_2,..,E_k of edges such that deg_{E_i}(v) is close to a_i*deg_{E}(v). We will show a polynomial time algorithm to find a decomposition such that for each v and for i=1,2,..,k, the following holds: floor(a_i*deg_{E}(v))-2 <= deg_{E_i}(v) <= ceil(a_i*deg_{E}(v))+2
Reference:
Uriel Feige and Mohit Singh. Edge coloring and decompositions of weighted graphs
Proceedings of ESA 2008: 405-416.
Jian Li
ABSTRACT
We consider the Shapley network design game of network, which is also called network design games with fair cost allocation. In this game, we have a edge cost network G(V, E) and n selfish players with player planning to choose a path from source vertex si to destination vertex ti. The cost of each edge is equally splitted among all players who pass it. The prize of stability is defined as the ratio of the cost of the best Nash equlibrium to the globle optimum. In directed network, it has been proved the prize of stability has a matching upper and lower bound H_n. In undirected network, it is an open question whether the upper bound is o(logn). People conjecture the bound is constant. We present a O(log/loglogn) upper bound for the single sink case, i.e, t_i=t for all i.
A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding
Nate (Xiaoming) Xu
(joint work with Mordecai Golin and Jiajin Yu, to appear at SODA 2009)
ABSTRACT
Given a probability distribution over a set of n words to be transmitted, the Huffman Coding problem is to find a minimal-cost prefix free code for transmitting those words The basic Huffmancoding problem can be solved in O(n log n) time but variations are more difficult. One of the standard techniques for solving these variations utilizes a top-down dynamic programming approach. In this paper we show that this approach is amenable to dynamic programming speedup techniques, permitting a speedup of an order of magnitude for many algorithms in the literature for such variations as mixed radix, reserved length and one-ended coding. These speedups are immediate implications of a general structural property that permits batching together the calculation of many DP entries.
http://www.cs.umd.edu/areas/Theory/ / Webmaster: Azarakhsh Malekian