Midwest Theory Day, Fall 2004 Abstracts
Speaker: Kousha Moaveni-Nejad, Illinois Institute of Technology, 10:20 - 10:45 a.m.
Title: Low-Interference Topology Control for Wireless Ad Hoc Networks
Topology control has been well studied in wireless ad hoc networks. However, only a few topology control methods take into account the low interference as a goal of the methods. Some researchers tried to reduce the interference by lowering node energy consumption (i.e. by reducing the transmission power) or by devising low degree topology controls, but none of those protocols can guarantee low interference. Recently, Burkhart et al. [3] proposed several methods to construct topologies whose maximum link interference is minimized while the topology is connected or is a spanner for Euclidean length. In this paper we give algorithms to construct a network topology for wireless ad hoc network such that the maximum (or average) link (or node) interference of the topology is either minimized or approximately minimized.
Joint work with Xiang-Yang Li.
Author emails: moavkoo@iit.edu, xli@cs.iit.edu.
Speaker: Wenzhan Song, Illinois Institute of Technology, 10:45 - 11:10 a.m.
Title: Energy Efficient Topology for Unicast and Broadcast Routings in MANET We propose a novel topology control strategy for each wireless node to locally select communication neighbors and adjust its transmission power. All nodes together self-form an energy efficient topology for both unicast and broadcast. We first introduce an improved method for all nodes to self-form a planar and power efficient network topology for unicast, and each node only need maintain at most $k-1$ ($k \geq 9$ is a customizable parameter) communication neighbors. Then a novel strategy is described for each node to further select some communication neighbors, hence the final topology, called $LS\Theta GG$, has an addition favorable property: it is also power efficient for broadcast among all locally constructed structures. To our best knowledge, this is the first localized algorithm to construct a global topology which is a degree-bounded planar power spanner with low-weight. The strategy used to achieve this can actually be used on top of any know planar structure with bounded node degree with at most double the spanning ratio. We also show that the expected average interference of the final structure is bounded by a small constant.
Moreover, by assuming that the node ID and its position can be represented in $O(\log n)$ bits for a wireless network of $n$ nodes, the total number messages of our methods is in the range of $[5n,13n]$, where each message is $O(\log n)$ bits. Our theoretical results are corroborated in the simulations.
Speaker: Robbie Schweller, Northwestern University, 11:10 - 11:35 a.m.
Title: Reversible Sketches for Efficient and Accurate Change Detection over Network Data Streams
An important primitive for online detection of anomalies in network data streams is the detection of keys that exhibit large changes in traffic volume. One approach to detect such keys is to use a probabilistic summary data structure called a sketch. While sketches are compact and can be updated at the speed of network traffic, the process of extracting the set of keys with heavy traffic changes is not scalable. We propose reversible sketches which allow this extraction to be performed more efficiently.
Speaker: Gruia Calinescu, Illinois Institute of Technology, 11:35 - 12:00 p.m.
Title: Separating Points By Axis-Parallel Lines
We study the problem of separating n points in the plane, no two of which have the same x- or y-coordinate, using a minimum number of vertical and horizontal lines avoiding the points, so that each cell of the subdivision contains at most one point. We prove that this problem and some variants of it are NP-hard. We give a 2-approximation algorithm, and a $d$-approximation algorithm for the $d$-dimensional variant, in which the points are to be separated using axis-parallel hyperplanes.
We reduce the problem to the rectangle stabbing problem studied by Gaur et al. Their approximation algorithm uses LP rounding. We present an alternative LP-rounding procedure which also works for the rectangle stabbing problem. We show that the integrality ratio of the LP is exactly 2.
Joint work with Adrian Dumitrescu, Howard Karloff, and Peng-Jun Wan.
Speaker: David Bunde, University of Illinois at Urbana-Champaign, 1:30 - 1:55 p.m.
Title: Minimizing Flow Time with Rejections
We consider the problem of minimizing flow time on a single machine supporting preemption that can reject jobs for some cost. Our main result is an algorithm with competitive ratio e/(e-1) (about 1.582) and a matching lower bound for the special case when all jobs have unit processing time and rejection cost c. We also show that a ratio better than (2+sqrt(2))/2 (about 1.707) is not possible if job processing times differ. In the offline setting, we show that the problem is NP-hard even when the rejection cost of a job is proportional to its processing time and give an optimal algorithm for jobs with unit processing time and arbitrary rejection costs. This leads to an easy 2-competitive algorithm for the online problem when the jobs have unit processing time and arbitrary rejection costs.
A manuscript with these results is available at http://compgeom.cs.uiuc.edu/~bunde/pubs/rejectflow.html.
Speaker: Maleq Khan, Purdue University, 1:55 - 2:20 p.m.
Title: Local Distributed Algorithms via Nearest Neighbor Trees
There are almost optimal sequential and distributed algorithms for the
Minimum Spanning Tree (MST) problem. However, these algorithms require
relatively large number of messages, and relatively large amount of time,
and are fairly involved, require synchronization and a lot of book keeping;
this makes these algorithms impractical for emerging technologies such as ad
hoc and sensor networks. The central theme of this paper is a family of
extremely simple, local algorithms that have very low message complexity,
but produce a {\em logarithmic} approximation to the {\em Metric} MST
problem. We call these algorithms the {\em Nearest Neighbor Tree (NNT)
algorithms}, and these employ a very simple idea to eliminate the work
involved in cycle detection in other MST algorithms: each node chooses a
distinct rank, and connects to the closest node of higher rank.
We prove several interesting properties and applications of NNT algorithms.
We show that for any metric instance, any NNT algorithm gives an $O(\log{n})$
approximation to the MST. By varying the process of choosing the ranks, we
define Random-NNT, in which each node chooses a rank randomly from some space,
and Directional-NNT, in which each node uses the coordinate information to
define ranks. In the point-to-point distributed model, in which the
processors are connected in a clique, we show that the Random-NNT algorithm
can be implemented in $O(\log{n})$ time and expected $O(n\log{n})$ messages,
contrasting the $\Omega(n^2)$ deterministic lower bound for finding the
optimal MST by Korach et al. For geometric instances, we show that
Random-NNT constructs low-degree spanning trees which have $O(\log{n})$
maximum degree, with high probability, using significantly less work than
the worst-case lower bound. We also show that Random-NNT yields simple and
local distributed dynamic algorithms, that require only $O(\log^2{n})$ work
on the average, for geometric instances. Finally, we show that the
Directional-NNT algorithm gives much better bounds than Random-NNT for
uniformly random distributions of points, but for arbitrary geometric
instances it does not improve on Random-NNT.
Joint work with V.S. Anil Kumar and Gopal Pandurangan.
Author emails: mmkhan@cs.purdue.edu, anil@lanl.gov, gopal@cs.purdue.edu
Speaker: Predrag Tosic, University of Illinois at Urbana-Champaign, 2:20 - 2:45 p.m.
Title: Maximal Clique Based Distributed Group Formation in Large-Scale Multi-Agent Systems
We present a fully distributed algorithm for group or coalition formation among autonomous agents. The algorithm is based on two main ideas. One is a distributed computation of maximal cliques (of up to pre-specified size) in the underlying graph that captures the interconnection communication topology of the agents. Hence, given the current configuration of the agents, the groups that are formed are characterized by a high fault tolerance with respect to node and link failures. The second idea is that each agent chooses its most preferable coalition based on how highly the agent values each such coalition in terms of the coalition members' combined resources or capabilities. Coalitions with sufficient resources for fulfilling particular highly desirable task(s) are preferable to coalitions with either insufficient resources, or with resources that suffice only for completing less valuable tasks. We envision variants of our distributed algorithm herein to prove themselves useful coordination subroutines in many large-scale multi-agent system applications where the agents may repeatedly need to form temporary groups or coalitions in an efficient, online and fully distributed manner.
Joint work with Gul Agha.
Speaker: Dan Cranston, University of Illinois at Urbana-Champaign, 3:00 - 3:25 p.m.
Title: Sorting Permutations by Shifts, Flips, and Shift-Flips
We consider the problem of determing the maximum
number of moves required to sort a permutation of [n]
using shifts, flips, and shift-flips. We give a lower
bound of flr{n/2} and an upper bound of ceil{2n/3}.
Joint work with Stephen Hartke, Hal Sudborough, and Doug West.
Speaker: Judy Goldsmith, University of Kentucky, 3:25 - 3:50 p.m.
Title: Preferences and Domination
Consider the problem of deciding on a restaurant for the Midwest Theory Day dinner. There are many features to consider: Type of food, proximity to DePaul, proximity to El stops, price range, seating capacity, availability of reasonable beer, etc. One could say, for instance, "I prefer Greek food to American food, and given Greek food, I prefer restaurants not in the immediate vicinity of DePaul."
One representation of preferences is a CP-net, which uses a digraph to represent dependencies of features ("My preference about distance depends on the type of food") and conditional preference tables ("If the food is German then I prefer restaurants close to DePaul; If the food is Greek then I prefer restaurants farther from DePaul.")
We say that one instance (Greek food, not close to DePaul, near an El stop, $15-25, large tables and small rooms available, no good beer) is preferable to another (German food, nearby, near the El, $20-40, crowded, German beer) if there is a sequence of single-feature changes that begins with the less-preferred instance and ends with the more-preferred instance, and where each change increases the preferability. We also say that the preferred instance <i>dominates</i> the less-preferred instance.
We show that the dominance problem for cyclic CP-nets is PSPACE complete.
Speaker: Kevin Milans, University of Illinois at Urbana-Champaign, 3:50 - 4:15 p.m.
Title: Problems in Graph Pebbling
Consider a graph G and a distribution of pebbles p to the vertices of G. A pebbling move consists of removing two pebbles from some vertex u and placing one pebble on a neighbor of u. Many natural computational problems arise. For example, given G, p, and a target vertex r in G, does there exist a sequence of pebbling moves which results in a pebble on r? We call this problem Pebble-Reachability. Pebble-Reachability is NP-complete; we sketch a proof that Pebble-Reachability is NP-hard. As time permits, we give an overview of hardness results of other pebbling problems and conclude with open problems.
Joint work with Bryan Clark.
Speaker: Weizhao Wang, Illinois Institute of Technology, 4:30 - 4:55 p.m.
Title: Towards Truthful Mechanisms for Demand Games: A General Framework
The family of the Vickrey-Clarke-Groves (VCG) mechanisms is the most celebrated achievement in truthful mechanism design. However, VCG mechanisms have their limitations. They only apply to optimization problems with a utilitarian objective function and their output should optimize the objective function. For many optimization problems, finding the optimal output is computationally intractable. If we apply VCG mechanisms to such polynomial time algorithms whose output approximates the optimal solution, the resulting mechanisms may no longer be truthful.
In light of these limitations, it is useful to study whether we can design a truthful non-VCG payment scheme that is computationally tractable for a given output method $\cal O$.
In this paper, we focus our attention on \emph{demand game} in
which the agents' only available actions are to take part in the
game or not to. For these problems, we prove that a truthful
mechanism $M=({\cal O},p)$ exists if and only if $\cal O$
satisfies a certain monotone property. We also provide several
general algorithms to compute the payments efficiently for various
types of output. In particular, we show how a truthful payment can
be computed through ``or/and'' combination, round-based
combination, and some more complex combinations of outputs from
subproblems.
Speaker: Adam Kalai, Toyota Technological Institute, 4:55 - 5:20 p.m.
Title: Online convex optimization: gradient descent without a gradient
We study a general online convex optimization problem. We have a convex
set S and an unknown sequence of cost functions c_1,c_2,..., and in each
round, we choose a feasible point x_t in S, and learn the cost c_t(x_t).
If the function c_t is also revealed after each round then, as Zinkevich
has shown that online gradient descent can be used on these functions,
even if they are not related . That is, after n rounds, the total cost
incurred will be O(sqrt(n)) more than the cost of the best single
feasible point chosen with the benefit of hindsight, min_{x\in S}
c_1(x)+c_2(x)+...c_n(x). We present this result and then extend it to
the more difficult "bandit" setting where each period, only the cost
c_t(x_t) is revealed, and bound the expected regret (against an
oblivious adversary) as O(n^{5/6}).
Our approach uses a simple approximation of the gradient that is computed from evaluating c_t at a single (random) point. We show that this biased estimate is sufficient to approximate gradient descent on the sequence of functions. In other words, it is possible to use gradient descent in the online setting without seeing anything more than the value of the functions at a single point.
Joint work Abie Flaxman and Brendan McMahan from CMU.
Author web page: http://www.cs.uchicago.edu/~kalai