Algorithms Reading Group - Spring 2008

"Unique Coverage" has important applications in wireless networks. The problem is defined as follows: Given a set of finite input points P in the euclidean plane and a finite set of unit disks D, call a subset of disks D' to uniquely cover a point p in P if exactly one disk d in D' contains point p. The "Unique Coverage" problem is then to find a subset D' that maximizes the number of input points uniquely covered. The problem is NP-hard. The paper presents a 1/18 approximation algorithm. I will present both these results on Friday. However, the paper contains other interesting variants such as Budgeted-Low Coverage on fat objects of "bounded ply" where any input point is covered by a bounded number of fat objects. They give an asymptotic FPTAS for this. Another variant considered is the Minimum Membership Set Cover problem where the goal is to cover P while minimizing the maximum number of times a point is covered. They show that this is (1-epsilon) ln n hard to approximate and give a O(log n) approximation algorithm.

We consider a restricted version of the art gallery problem within simple polygons in which the guards are required to lie on a given one-dimensional object, a watchman route. We call this problem the vision point problem. We prove the following:
- The original art gallery problem is NP-hard for the very restricted class of street polygons
- The vision point problem can be solved efficiently for the class of street polygons.
- A linear time algorithm for the vision point problem exists for the subclass of street polygons called the straight walkable polygons.

A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices, $\delta$ the minimum degree, and $\Delta$ the maximum degree.
We show that every graph has a domatic partition with $(1 - o(1))(\delta + 1)/\ln n$ dominating sets and, moreover, that such a domatic partition can be found in polynomial-time. This implies a $(1 + o(1))\ln n$-approximation algorithm for domatic number, since the domatic number is always at most $\delta + 1$. We also show this to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every $\epsilon > 0$, a $(1 - \epsilon)\ln n$-approximation implies that $NP \subseteq DTIME(n^{O(\log\log n)})$.

Given a large online network of online auction users and their histories of transactions, how can we spot anomalies and auction fraud? This paper describes the design and implementation of NetProbe, a system that we propose for solving this problem. NetProbe models auction users and transactions as a Markov Random Field tuned to detect the suspicious patterns that fraudsters create, and employs a Belief Propagation mechanism to detect likely fraudsters. Our experiments show that NetProbe is both efficient and effective for fraud detection. We report experiments on synthetic graphs with as many as 7,000 nodes and 30,000 edges, where NetProbe was able to spot fraudulent nodes with over 90% precision and recall, within a matter of seconds. We also report experiments on a real dataset crawled from eBay, with nearly 700,000 transactions between more than 66,000users, where NetProbe was highly effective at unearthing hidden networks of fraudsters, within a realistic response time of about 6 minutes. For scenarios where the underlying data is dynamic in nature, we propose IncrementalNetProbe, which is an approximate, but fast, variant of NetProbe. Our experiments prove that Incremental NetProbe executes nearly doubly fast as compared to NetProbe, while retaining over 99% of its accuracy.

Greedy routing is a class of routing algorithms where packets are routed (in a multi-hop manner) in such a way that the distance (w.r.t. the underlying metric) to the destination is reduced in every hop. Papadimitrioiu and Ratajczak [TCS 2005] conjectured that every 3-connected planar graph can be "drawn" in the euclidean plane s.t. the drawing allows for greedy routing (in the euclidean sense).
In this paper, the conjecture is settled in the affirmative for the case of planar triangulations (a class which appears to constitute almost all the non-trivial 3-connected planar graphs). The (existence) proof relies upon Schnyder Drawings [SODA 1990] of triangulations and their properties. The algorithmic question is still open in the sense that it is unclear as to quickly a "reasonable" approach converges to a Schnyder Drawing.

Last time I presented the O(log n) approximation algorithm and the beginnings of the O(log n) hardness of approximation proof. This talk will focus on the hardness of approximation proof. I will review what was discussed last time and then spend the majority of the time describing the reduction from Max-3-colorability.

An online problem is one that must be "solved" without knowing the future or without having complete information. In this talk, we present updated results we have obtained on online routing and scheduling problems. In particular, we consider first online routing optimization problems where the objective is to minimize the time needed to visit a set of locations under various constraints; the problems are online because the set of locations are revealed incrementally over time. We consider several problems such as (1) the online Traveling Salesman Problem (TSP) with precedence and capacity constraints and (2) the online TSP with m salesmen.
For both problems we propose online algorithms, sometimes with best- possible competitive ratios. We also consider resource augmentation, where we give the online servers additional resources to offset the powerful offline adversary advantage. We derive improved competitive ratios. Finally, we study online algorithms from an asymptotic point of view, and show that, under general stochastic structures for the problem data, unknown and unused by the online player, many of these online algorithms are almost surely asymptotically optimal.

Currently, there are no known explicit algorithms for the great majority of graph problems in the dynamic distributed message-passing model. Instead, most state-of-the-art dynamic distributed algorithms are constructed by composing a static algorithm for the problem at hand with a simulation technique that converts static algorithms to dynamic ones. We argue that this powerful methodology does not provide satisfactory solutions for many important dynamic distributed problems, and this necessitates developing algorithms for these problems from scratch. In this paper we develop a fully dynamic distributed algorithm for maintaining sparse spanners. Our algorithm improves drastically the quiescence time of the state-of-the-art algorithm for the problem. Moreover, we show that the quiescence time of our algorithm is optimal up to a small constant factor. In addition, our algorithm improves significantly upon the state-of-the-art algorithm in all efficiency parameters, specifically, it has smaller quiescence message and space complexities, and smaller local processing time. Finally, our algorithm is self-contained and fairly simple, and is, consequently, amenable to implementation on unsophisticated network devices.

In this paper, we give a O(log c_opt)-approximation algorithm for the point guard problem where c_opt is the optimal number of guards. Our algorithm runs in time polynomial in n, the number of walls of the art gallery and the spread Δ, which is defined as the ratio between the longest and shortest pairwise distances. Our algorithm is pseudopolynomial in the sense that it is polynomial in the spread Δ as opposed to polylogarithmic in the spread Δ, which could be exponential in the number of bits required to represent the vertex positions. The special subdivision procedure in our algorithm finds a finite set of potential guard-locations such that the optimal solution to the art gallery problem where guards are restricted to this set is at most 3 c_opt. We use a set cover cum VC-dimension based algorithm to solve this restricted problem approximately.