| Midwest Theory Day |
| D e P a u l U n i v e r s i t y |
| A u t u m n 2 0 0 3 |
| Distributed Heuristics for Weakly-Connected Dominating Sets and Sparse Spanners in Unit-Disk Graphs |
| Khaled M. Alzoubi (Saint Xavier University) |
| A unit-disk graph (UDG) is a geometric
graph in which there is an edge between two nodes if and only if their
distance is at most one. The UDG has been proposed as a typical model for
wireless ad hoc networks, and weakly-connected dominating sets (WCDSs) and
spanners have been proposed as virtual backbones for wireless ad hoc
networks. Unlike wired networks or cellular networks, no physical backbone
infrastructure is installed in wireless ad hoc networks. A communication
session is achieved either through a single-hop radio transmission if the
communication parties are close enough, or through relaying by intermediate
nodes otherwise. A set S is dominating if each node in the graph G = (V,E) is either in S or adjacent to at least one of the nodes in S. The subgraph weakly induced by S is the graph G' = (V,E') such that each edge in E'has at least one end point in S. The set S is a (WCDS) of the graph G if S is dominating and G' is connected. G' is a sparse spanner if it has linear edges. However, it is NP-hard to find a minimum WCDS. Approximation heuristics for a minimum WCDS have been proposed in the literature with approximation ratio of O(ln D), where D is the maximum nodal degree. Furthermore, these heuristics suffer from high time and message complexity. In this conference, we present two distributed heuristics for finding WCDSs and spanners in the UDG. Both heuristics have a time complexity of O(n). The first heuristic has an approximation ratio of 5, and requires O(n log n) messages. The second heuristic has a larger approximation ratio (still constant), but it requires only O(n) messages. The graph G' generated by the second heuristic forms a sparse spanner with a topological dilation of 3, and a geometric dilation of 6. |
| Combining algorithms for acceptance and rejection |
| David Bunde (University of Illinois at Urbana-Champaign) |
| Admission control algorithms attempt to maximize the use of a fixed pool of resources. They receive a stream of requests and decide for each request to either satisfy it using available resources or reject it. An algorithm is competitive for acceptance if it always accepts a particular fraction of the number of jobs accepted by the optimal algorithm and competitive for rejection if it never rejects more than a particular multiple of the number of jobs rejected by the optimal algorithm. These notions of competitiveness are not comparable, but we show how to combine an algorithm that is c_A-competitive for acceptances with an algorithm that is c_R-competitive for rejections to create an algorithm simultaneously O(c_A)-competitive for acceptances and O(c_Ac_R)-competitive for rejections, improving on the recent result of Azar et al. |
| Computational Issues in Information Markets |
| Lance Fortnow (University of Chicago) |
| Consider some potential future event, such
as Bush winning the 2004 presidential election and a security that pays off
$1 if that event happens and $0 if it fails to happen. We consider two
separate computational issues dealing with information markets that trade
futures in these events. Studies have shown that these markets are very good estimators of the likelihood of future events--the current price corresponds to the probability that the event will occur. These markets appear to efficiently perform information aggregation where individuals betting with partial information create a price that reflects the sum total of the known information. We give a formal analysis of a simple case considering an n-input Boolean function f and a security that pays off $1 if f is true and $0 if f is false. We have n traders each of which know a single input bit as well as common knowledge of a common distribution from which the input is drawn. We give an exact characterization of the set of functions for which the price will converge to the value of the function for all initial distributions. No reasonable set of securities can cover all possible future events and we look at the ability to trade new securities that are Boolean functions of other base securities. We consider the matching problem--given a set of securities and prices, is there a way to trade some subset of the securities without any risk? We give four variations of this question each yielding a different complexity result. This talk presents research developed in two papers presented at the 2003 ACM Conference on Electronic Commerce. - Betting Boolean Style: A Framework for Trading in Securities Based on
Logical Formula by Lance Fortnow, - Computation in a Distributed Information Market by Joan Feigenbaum,
Lance Fortnow, David Pennock and |
| On the complexity of multi-covering radii |
| Andrew Mertz (University of Kentucky) |
| The multi-covering radius is a generalization of the
covering radius. In this paper we show: Lower bounding the m-covering radius
of an arbitrary code is NP-complete when m is polynomial in the length of
the code. Lower bounding the m-covering radius of a linear code is
Sigma_2^p-complete when m is polynomial
in the length of the code. If P is not equal to NP, then the m-covering
radius of an arbitrary code cannot be approximated within a constant
additive factor or within an additive factor n^\epsilon where n is the
length of the code and \epsilon < 1. Note that the case when m = 1 was also previously unknown. If NP is not equal to \Sigma_2^p, then the m-covering radius of a linear code cannot be approximated within a constant factor or within a factor n^\epsilon where n is the length of the code and \epsilon < 1. |
| The Optimality of Random Number Generation from Biased Coin |
| Sung-il Pae (University of Illinois at Urbana-Champaign) |
| Consider the problem of simulating coin flips of a
given bias r using coin flips of a known bias p. A natural class of algorithms for this problem can be represented as binary trees, which we call DDG-trees. A DDG-tree is optimal if the corresponding algorithm uses the minimum average number of source coin flips to generate one output of the target coin. We show that it is impossible to construct an optimal DDG-tree with a real-RAM program by using a topological property of the problem domain of a decision problem that is reducible to the construction of optimal DDG-trees. For some special cases, we present an algorithm that constructs optimal DDG-trees. |
| The Bin-Covering Technique for Thresholding Random Geometric Graph Properties |
| Gopal Pandurangan (Purdue University) |
| We study the emerging phenomenon of ad hoc,
sensor-based communication networks. The communication is modeled by the geometric random graph model $G(n,r,\ell)$ where $n$ points randomly placed within $[0,\ell]^d$ form the nodes, and any two nodes that correspond to points at most distance $r$ away from each other are connected. The more widely studied $G(n,r)$ model where $\ell$ is held fixed at unity and $n\rightarrow \infty$ applies for dense ad hoc networks, but the $G(n,r,\ell)$ model is more detailed, and more generally applicable to modeling communication networks, sparse or dense. We study fundamental properties of $G(n,r,\ell)$ of interest: connectivity, coverage, and routing-stretch. Our main contribution is a simple analysis technique we call {\em bin-covering} that we apply uniformly to get {\em (asymptotically) tight} thresholds for each of these properties. Typically, in the past, geometric random graph analyses involved sophisticated methods from continuum percolation theory; on contrast, our bin-covering approach is discrete and very simple, yet it gives us tight threshold bounds. Our specific results should also prove interesting to the networking community that has seen a recent increase in the study of geometric random graphs motivated by engineering ad hoc networks. (Joint work with S. Muthukrishnan.) |
| Buffer minimization using max-coloring |
| Rajiv Raman (University of Iowa) |
| Given a graph G=(V,E) and a
positive weight function w on the vertices, the max-coloring problem asks
for a proper vertex coloring of this graph into color classes C_1, ... C_k
that minimizes sum_{i=1}^k (cost(C_i)), where the cost of a color class C_i
is the maximum weight of a vertex in C_i. The problem restricted to interval
graphs arises in finding an optimal allocation of memory buffers for a
program. The problem is NP-complete for interval graphs. We give a 2-approximation for the problem, and also prove that a first-fit coloring is a 10-approximation, by showing that online coloring an interval graph by first-fit is a 10-approximation. (Joint work with Sriram Pemmaraju, and Kasturi Varadarajan -- To appear in SODA 2004) |
| Bounded-Hops Power Assignment in Ad-Hoc Wireless Networks |
| Mohammad Sarwat (Illinois Institute of Technology) |
| Motivated by topology control in ad-hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity). These problems have been studied in the past. In this talk we consider delay bounds as an additional constraint to provide Quality of Service. Delay is measured by the number of hops on a path between two nodes. We will present an algorithm for Minimum Power Bounded Hops Broadcast with guaranteed bicriteria ratio of $(O(\log{n}),O(\log{n}))$ for general graphs. That is, in the solution produced by our algorithm the number of hops between the root and any other node is at most $O(\log{n})$ times the given bound and the power is at most $O(\log{n})$ times the power of optimal solution. Our bicriteria results extend to other kinds of strong and symmetric connectivity requirements as well. We will also discuss improvement of these guarantees for the Euclidean cases, by post processing solutions of the main algorithm. |
| Complexities for Generalized Models of Self-Assembly |
| Robert Schweller (Northwestern University) |
| In this paper, we extend Rothemund and Winfree’s
examination of the tile complexity of tile self-assembly [6]. They provided
a lower bound of Omega( logN/log logN ) on the tile complexity of assembling
an N × N square for almost all N. Adleman et al. [Running Time and Program
Size for Self-Assembled Squares] gave a construction which achieves this
bound. We consider whether the tile complexity for self-assembly can be
reduced through several natural generalizations of the model. One of our
results is a tile set of size O(sqrt(logN)) which assembles an N×N square in a model which allows flexible glue strength between non-equal glues (This was independently discovered by Q. Cheng and P.M. de Espanes in "Resolving two open problems in the self-assembly of squares"). This result is matched by a lower bound dictated by Kolmogorov complexity. For three other generalizations, we show that the Omega( logN/log logN ) lower bound applies to N ×N squares. At the same time, we demonstrate that there are some other shapes for which these generalizations allow reduced tile sets. Specifically, for thin rectangles with length N and width k, we provide a tighter lower bound of Omega(N^(1/k)/k ) for the standard model, yet we also give a construction which achieves O( logN/log logN ) complexity in a model in which the temperature of the tile system is adjusted during assembly. We also investigate the problem of verifying whether a given tile system uniquely assembles into a given shape, and show that this problem is NP-hard. |
| Graph decomposition and a greedy algorithm for edge disjoint paths |
| Ganesh Venkataraman (University of Iowa) |
| Given a directed graph G=(V,E), with n vertices and a
parameter l>=1, we present an algorithm that finds a cut (set of edges) of
size $O((n/l)^2log^2(n/l))$ whose removal separates every pair of vertices (s,t)
such that their minimum distance in G is at least l. Such a cut implies a
nearly tight analysis of the greedy algorithm for finding edge-disjoint
paths in directed graphs and gives the best known approximation algorithm
for this problem in terms of the number of vertices. (Joint work with Kasturi Varadarajan. -- To appear in SODA 2004) |
| Efficient algorithms for the inverse protein folding problem in 2D and 3D lattices |
| Yi Zhang (University of Illinois at Chicago) |
| We investigate the inverse protein folding (IPF)
problem under the Canonical method on 3D and 2D lattices. In this
problem we are given a contact graph G of n vertices of a protein sequence
that is embeddable in a 3D (respectively 2D) lattice and an integer 1<=K<=n
and our goal is to find an induced subgraph of G of at most K vertices with
the maximum number of edges. An earlier proof of NP-completeness of the IPF
problem on 3D lattices is based on the NP-completeness of the IPF problem on
the 2D lattices. However, the reduction was not correct and we show that the
IPF problem for 2D lattices can be solved in O(Kn) time. But, we show that
IPF problem on 3D lattices is indeed NP-complete by providing a different
reduction from the CLIQUE problem. We also design a polynomial-time
approximation scheme for the IPF problem on 3D lattices using the shifted
slice-and-dice approach, thereby improving the previous best polynomial-time
approximation algorithm which had a performance ratio of 1/2. (Joint work with Piotr Berman, Bhaskar DasGupta, Dhruv Mubayi, and Robert Sloan) |