Titles and Abstracts

Ryerson Hall

Sourav Chakraborty, University of Chicago
Property Testing of ST-Connectivity in the Orientation Model

Abstract:
We will consider the question of determining whether a given object has a predetermined property or is ``far'' from any object having the property. Specifically, objects are modeled by functions, and distance between functions is measured as the fraction of the domain on which the functions differ. We consider (randomized) algorithms which may obtain samples of the function value or even query the function at arguments of their choice, and seek algorithms of relatively low complexity (i.e., much lower than the size of the function's domain). Testing graph properties is common in this field. That is given a representation of the graph we want to test whether the graph has some particular property. But the definition of ``far-ness" and the form of queries allowed depends on the representation of the graph. In this talk we consider the problem of testing for a particular graph property called ``st -connectedness" is a directed graph. That we want to test whether there is a path between two given vertices s and t in the directed graph. The model of querying that we use is called orientation model. We give an algorithm that make only constant number of queries and test st-connectivity.

Erin Wolf Chambers, University of Illinois, Urbana-Champaign
Walking Your Dog in the Woods in Polynomial Time

Abstract:
The \Frechet\ distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without backtracking. We propose a natural extension of \Frechet\ distance to more general metric spaces, which requires the leash itself to move continuously over time. For example, for curves in the punctured plane, the leash cannot pass through or jump over the point obstacles (``trees''). We describe a polynomial-time algorithm to compute the \emph{homotopic} \Frechet\ distance between two given polygonal curves in the plane minus a given set of points.

Christine Cheng, University of Wisconsin-Milwaukee
The Generalized Median Stable Matchings: Finding Them Is Not That Easy

Abstract:
About a decade ago, Teo and Sethuraman showed that generalized median stable matchings exist. They are obtained as follows -- let $I$ be an instance with $N$ stable matchings. For each man $m$, collect $m$'s stable partners in these $N$ stable matchings and order them from his most preferred to his least preferred woman. Let $p_i(m)$ denote the $i$th woman in this sorted list. For $i=1, \hdots, N$, the {\it $i$th generalized median stable matching of $I$}, $\alpha_i$, matches every man $m$ to $p_i(m)$. The most interesting of these are the ones in the ``middle'' -- $\alpha_{(N+1)/2}$ when $N$ is odd, and $\alpha_{N/2}$ and $\alpha_{(N+2)/2}$ when $N$ is even -- called the {\it median stable matching} of $I$. Every man is matched to his (lower or upper) median stable partner and, simultaneously it turns out, every woman is also matched to her (lower or upper) median stable partner. Thus, the median stable matching of $I$ is fair at the individual level in a very strong sense. Determining whether there are efficient algorithms for finding these generalized median stable matchings is an open problem. In this talk, we resolve this open problem by presenting a new characterization of generalized median stable matchings that is solely based on the rotation poset of the instance. It allows us to prove the following: (i) when $i=O(\log n)$ where $n$ is the number of men (or women) of the instance, finding $\alpha_i$ and $\alpha_{N-i+1}$ can be done efficiently, but (ii) when $i$ is a constant fraction of $N$, finding $\alpha_i$ and $\alpha_{N-i+1}$ is NP-hard. Thus, determining the median stable matching of an instance is NP-hard. We also consider what it means to approximate the median stable matching of an instance, and present results for this problem.

Bhaskar DasGupta, University of Illinois at Chicago
On Approximating Transitive Reduction Problems for Biological and Social Networks: What Can We Get from a Primal-Dual Formulation of Edmond and Karp?

Abstract:
We consider the p-ary transitive reduction problem (TR_p) that was defined in a previous paper. For p=1, this includes the so-called minimum equivalent digraph (MED) problem as a special case; for p=2 this was described as the binary transitive reduction problem in (Albert et al., 2007); the more general case of p being any prime appears in another previous paper. We first consider TR_1 that includes MED. We consider a natural (albeit, exponential size) primal and dual IP formulation for TR_1. We use this formulation to provide a 1.5-approximation for TR_1 that improved the 1.78-approximation in a previous paper. Our result also provides a somewhat simpler proof of 1.5-approximation for MED. This result is then extended to provide a 1.5+o(1)-approximation for TR_p for any prime p>1. We also show some inherent limitations of our approach by showing an integrality grap of at least 4/3. Finally, on the inapproximability side, we show that the MED problem is MAX-SNP-hard even if all cycles are of length at most 5. This improves a result by Khuler, Raghavachari and Young where the MAX-SNP-hardness was proved provided cycles of length up to 17 were allowed. (joint result with Piotr Berman)

Scott Diehl, University of Wisconsin
A New Time-Space Lower Bound for Nondeterministic Algorithms Solving Tautologies

Abstract:
We show that for all reals c and d such that c^2d < 4 there exists a positive real e such that tautologies cannot be decided by both a nondeterministic algorithm that runs in time n^c, and a nondeterministic algorithm that runs in time n^d and space n^e. In particular, for every real d < 4^{1/3} there exists a positive real e such that tautologies cannot be decided by a nondeterministic algorithm that runs in time n^d and space n^e. This is a joint work with Dieter van Melkebeek and Ryan Williams.

Matt Gibson, University of Iowa
On Clustering to Minimize the Sum of Radii

Abstract:
Let P be a set of n points in the plane. Consider the problem of finding k disks, each centered at a point in P, whose union covers P with the objective of minimizing the sum of the radii of the disks. We present an exact algorithm for this well-studied problem with polynomial running time. The algorithm generalizes in a straightforward manner to any fixed dimension d and to some other related problems. This is joint work with Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi Varadarajan and will appear in SODA 2008.

Judy Goldsmith, University of Kentucky
Competition Adds Complexity

Abstract:
It is known that determining whether a DEC-POMDP, namely, a cooperative partially observable stochastic game (POSG) has a cooperative strategy with positive expected reward is complete for NEXP. It was not known until now how cooperation affected that complexity. We show that, for competitive POSGs, the complexity of determining whether one team has a positive-expected-reward strategy is complete for NEXP^{NP}.

Nitish Korula, University of Illinois, Urbana-Champaign
Better Approximations for Orienteering With Time Windows

Abstract:
In the orienteering problem, we are given an edge-weighted graph G, two vertices s,t, and a budget B. The goal is to find a walk from s to t of length at most B that visits as many vertices as possible. Orienteering with time-windows is the generalization in which every vertex has a release time and deadline, and we get credit for a vertex only if we visit it within the appropriate time window. For the time-window problem, the best previously known approximation ratio was O(\log^2 n) in undirected graphs and O(\log^4 n) in directed graphs. Let L_max be the length of the longest time window, and L_min be the length of the shortest window. By focusing on the ratio L= L_max/L_min, we give an O(\alpha \max{\log L, \log n})-approximation for the time-window problem, where \alpha is the approximation ratio for the orienteering problem (without time windows). In particular, for instances where L_max/L_min is poly-bounded, we improve the approximation ratios for both directed and undirected graphs by a factor of O(\log n).

Raghav Kulkarni, University of Chicago
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

Abstract: The isolation lemma (due to Mulmuley, Vazirani and Vazirani) randomly assigns small(log bit) weights to the elements of a set S such that the minimum weight subset in any family F of subsets of S becomes unique. The lemma, isolate a perfect matching in general graphs which in turn gives fast parallel algorithm for finding a perfect matching. We will present a deterministic way of assigning small weights to the edges of a bipartite planar graph so that the minimum weight perfect matching in it becomes unique. (Joint work with Samir Datta and Sambuddha Roy.)

Marina Langlois, University of Illinois at Chicago
Combinatorial Problems for Horn Clauses

Abstract: Given a family of Horn clauses, what is the minimal number of Horn clauses implying all other clauses in the family? What is the maximal number of Horn clauses from the family without having resolvents of a certain kind? We consider various problems of this type, and give some sharp bounds.

Imran Pirwani, University of Iowa
Good Quality Realization of Unit Disk Graphs

Abstract:
Given a unit disk graph (UDG) with only connectivity information (no geometric model), we compute an approximate embedding into the Euclidean plane of the graph (a realization) that seeks to minimize the ratio of the longest edge and the shortest non-edge. The approximation ratio achieved is log^{2.5} n; the construction is combinatorial. This is an improvement over the best known approximation of log^{3} n times lower order terms which requires solving an LP with exponentially many constraints. We also provide a (k, sqrt{log n})-volume respecting embedding (in O(log^{3} n) dimensions) of a growth restricted graph which corresponds to a clique partition of the given UBG. We also provide an O(1) quality embedding of the UBG in O(1) dimensions. The key structure (the cluster graph) is based upon a partition of the neighborhood of a vertex into O(1) cliques without any geometry. A consequence of this is a first polynomial time (computational complexity of each node), fully distributed O(1) factor approximation to the minimum clique cover of a UDG without geometry in deterministic O(log \Delta log* n) rounds, where \Delta is the maximum degree in the graph. In the talk, I plan to focus on the construction of a growth-restricted cluster graph of the underlying UDG without the use of geometry.

Michael Skalak, Northwestern University
An Improved Algorithm for a Haplotype Inference Problem

Abstract:
Given a pedigree indicating the genotypes of $n$ related individuals and parent-child relationships between them (where each genotype contains $m$ loci), the haplotype inference problem consists of finding a haplotype pair for each of the $n$ individuals that is consistent with the pedigree. The best known algorithm for this general problem (due to Xiao et al.) has running time $O(m n^2 + n^3 \log n \log \log n)$; for the special case where the pedigree contains no mating loops (i.e., where no two descendants of a common ancestor made), an $O(mn)$-time algorithm was given by Chan et al. We present an $O(m n)$-time algorithm for the general problem (with mating loops) for the case where all individuals share some common heterozygous locus (i.e., for some locus, the haplotype pairs for every individual are known to contain two different alleles). (Joint work with Ming-Yang Kao (Northwestern University) and Eric Schwabe (DePaul University).)

Haitao Wang, University of Notre Dame
Online Rectangle Filling

Abstract:
We study an online geometric problem arising in channel-aware scheduling of wireless networks, which we call the online rectangle filling problem. We present an online algorithm for this problem with a competitive ratio of 1.848. We prove a lower bound of $1.6358$ for the competitive ratio of the problem. In addition, we give an $O(n^2)$-time optimal offline algorithm, where $n$ is the size of the input. All three results are significant improvements on the previous results. Our techniques are based on new observations of the combinatorial structures in the problem.