SODA 2010 Accepted papers: abstracts

source: http://soda10.cs.princeton.edu/

1. A PTAS for Minimum Clique Partition in Unit Disk Graphs

Authors: Imran Pirwani (Dept. of Computing Science, University of Alberta) Mohammad Salavatipour (Dept. of Computing Science, University of Alberta)

Topics: Algorithm Analysis, Approximation Algorithms, Geometry, Graph Algorithms

We consider the problem of partitioning the set of vertices of a given unit disk graph (UDG) into a minimum number of cliques. The problem is NP-hard and various constant factor approximations are known, with the current best ratio of 3. Our main result is a polynomial time approximation scheme (PTAS) for this problem on UDG. In fact, we present a weakly-robust algorithm that given a graph G (not necessarily UDG) with edge-lengths, it either (i) computes a clique partition or (ii) gives a certificate that the graph is not a UDG; for the case (i) that it computes a clique partition, we show that it is guaranteed to be within (1 + ε) ratio of the optimum if the input is UDG; however if the input is not a UDG it either computes a clique partition as in case (i) with no guarantee on the quality of the clique partition or detects that it is not a UDG. Noting that recognition of UDG’s is NP-hard even if we are given edge lengths, our PTAS is a weakly-robust algorithm. Our main technical contribution involves showing the property of separability of an optimal clique partition: that there exists an optimal clique partition where the convex hulls of the cliques are pairwise non-overlapping. Our algorithm can be transformed into an O(log*n/ε^O(1)) time distributed polynomial-time approximation scheme (PTAS). Finally, we consider a weighted version of the clique partition problem on vertex weighted UDGs given given in the standard form (e.g. adjacency matrix); the weight of a clique is the weight of a heaviest vertex in it, and the weight of a clique partition is the sum of the weights of the cliques in it. This formulation generalizes the classical clique partition problem. We note some key distinctions between the weighted and the unweighted versions, where ideas developed for the unweighted case do not help. Yet, surprisingly, we show that the problem admits a (2 + ε)-approximation algorithm for the weighted version of the problem even when the graph is expressed in standard form. This improves on the best known algorithm which constructs an 8-approximation for the unweighted case for UDGs expressed in standard form.

2. An Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling

Authors: Benjamin Moseley (University of Illinois Urbana-Champaign) Sungjin Im (University of Illinois Urbana-Champaign)

Topics: Algorithm Analysis, Approximation Algorithms, Online problems, Scheduling and Resource Allocation

In this paper the online pull-based broadcast model is considered. In this model, there are $n$ pages of data stored at a server and requests arrive for pages online. When the server broadcasts page $p$, all outstanding requests for the same page $p$ are simultaneously satisfied. We consider the problem of minimizing average (total) flow time online where all pages are unit-sized. For this problem, there has been a decade-long search for an online algorithm which is scalable, i.e. $(1+\eps)$-speed $O(1)$-competitive for any fixed $\eps >0$. Before this work, no known online algorithm was a candidate to be scalable. In this paper, we develop a new algorithm for this problem and give the first analysis of an online scalable algorithm.

3. Probabilistic Analysis of the Semidefinite Relaxation Detector in Digital Communications

Authors: Anthony Man-Cho So (The Chinese University of Hong Kong)

Topics: Algorithm Analysis, Approximation Algorithms, Mathematical Programming, Optimization

We consider the problem of detecting a vector of symbols that is being transmitted over a fading multiple-input multiple-output (MIMO) channel, where each symbol is an $M$-th root of unity for some fixed $M \ge 2$. Although the symbol vector that minimizes the error probability can be found by the so-called maximum-likelihood (ML) detector, its computation is intractable in general. In this paper we analyze a popular polynomial-time heuristic, called the semidefinite relaxation (SDR) detector, for the problem and establish its first non-asymptotic performance guarantee. Specifically, in the low signal-to-noise ratio (SNR) region, we show that for any $M \ge 2$, the SDR detector will yield a constant factor approximation to the optimal log-likelihood value with a probability that increases exponentially fast to $1$ as the channel size increases. In the high SNR region, it is known that for $M=2$, the SDR detector will yield an exact solution to the ML detection problem with a probability that converges to $1$. We refine this result by establishing the rate of convergence. Our work can be viewed as an average-case analysis of a certain SDP relaxation, and the input distribution we use is motivated by physical considerations. Our results also refine and extend those in previous work, which are all asymptotic in nature and apply only to the problem of detecting binary (i.e. when $M=2$) vectors. In particular, our results can give better insight into the performance of the SDR detector in practical settings.

An Improved Construction of Progression-Free Sets

Authors: Michael Elkin (Ben-Gurion University of the Negev)

Topics: Combinatorics, Geometry, Number Theory

The problem of constructing dense subsets S of {1,2,..,n} that contain no arithmetic triple was introduced by Erdos and Turan in 1936. They have presented a construction with |S| = Omega(n^{\log_3 2}) elements. Their construction was improved by Salem and Spencer, and further improved by Behrend in 1946. The lower bound of Behrend is |S| = Omega({ n \over {{2^{2 \sqrt{2} \sqrt{\log_2 n}}} \cdot \log^{1/4} n}}). Since then the problem became one of the most central, most fundamental, and most intensively studied problems in additive number theory. Nevertheless, no improvement of the lower bound of Behrend was reported since 1946. In this paper we present a construction that improves the result of Behrend by a factor of Theta(sqrt{log n}), and shows that |S| = Omega({ n \over {{2^{2 \sqrt{2} \sqrt{\log_2 n}}} }} \cdot \log^{1/4} n \right). In particular, our result implies that the construction of Behrend is not optimal. Our construction and proof are elementary and self-contained. Also, the construction can be implemented by an efficient algorithm. Behrend's construction has numerous applications in Theoretical Computer Science. In particular, it is used for fast matrix multiplication, for property testing, and in the area of communication complexity. Plugging in our construction instead of Behrend construction in the matrix multiplication algorithm of Coppersmith and Winograd improves the state-of-the-art upper bound on the complexity of the matrix multiplication by a factor of log^\nu n, for some fixed constant \nu > 0. We also present an application of our technique in Computational Geometry.

Solving the Replacement Paths Problem for Planar Directed Graphs in O(n*log n) Time

Authors: Christian Wulff-Nilsen (Department of Computer Science, University of Copenhagen)

Topics: Algorithm Analysis, Graph Algorithms, Graph Theory, Internet and Network Algorithms, Optimization

In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linear-space algorithm with O(n*log n) running time for n-vertex planar directed graphs. The previous best time bound was O(n*(log n)^2).

Correlation Clustering with Noisy Input

Authors: Claire Mathieu (Brown University) Warren Schudy (Brown University)

Topics: Approximation Algorithms, Graph Algorithms, Mathematical Programming, Optimization, Probability, Random Graphs

Correlation clustering is a type of clustering that uses a basic form of input data: For every pair of data items, the input specifies whether they are similar (belonging to the same cluster) or dissimilar (belonging to different clusters). This information may be inconsistent, and the goal is to find a clustering (partition of the vertices) that disagrees with as few pieces of information as possible. Correlation clustering is APX-hard for worst-case inputs. We study the following semi-random noisy model to generate the input: start from an arbitrary partition of the vertices into clusters. Then, for each pair of vertices, the similarity information is corrupted (noisy) independently with probability $p$. Finally, an adversary generates the input by choosing similarity/dissimilarity information arbitrarily for each corrupted pair of vertices. In this model, our algorithm produces a clustering with cost at most $1 + O(n^{-1/6})$ times the cost of the optimal clustering, as long as $ p <= 1/2 - n^{-1/3}$. Moreover, if the noise $p$ is small, that is, $p=O(n^{-\epsilon})$, then we can exactly reconstruct all clusters of the planted clustering that have size $\Omega(1/\epsilon)$, and provide a certificate (witness) proving that those clusters are in any optimal clustering. Among other techniques, we use the natural semi-definite programming relaxation followed by an interesting rounding phase. The analysis uses semi-definite programming duality and spectral properties of random matrices.

A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs Authors: Aaron Bernstein (MIT)

Topics: Approximation Algorithms, Graph Algorithms

Let $G = (V,E)$ be a directed graph with non-negative edge weights, let $s,t$ be two specified vertices in this graph, and let $\pi(s,t)$ be the shortest path between them. In the \emph{replacement paths} problem we want to compute, for every edge $e$ on $\pi(s,t)$, the shortest path from $s$ to $t$ that avoids $e$. The naive solution to this problem would be to remove each edge $e$, one at a time, and compute the shortest $s-t$ path each time; this yields a running time of $O(mn + n^2\log n)$. Gotthilf and Lewenstein \cite{GL09} recently improved this to $O(mn + n^2\log\log n)$, but no $o(mn)$ algorithms are known. \\ \\ We present the first \emph{approximation} algorithm for replacement paths in weighted, directed graphs. Given any $\eps \in [0, 1)$, our algorithm returns $\oeps$-approximate replacement paths in $O(\eps^{-1}\log^2 n \log(nC/c)(m + n\log n)) = \widetilde{O}(m\log(nC/c)/\eps)$ time, where $C$ is the largest edge weight in the graph and $c$ is the smallest positive weight. \\ \\ We also present an even faster $\oeps$ approximate algorithm for the simpler problem of approximating the $k$ shortest simple $s-t$ paths in a graph. That is, our algorithm outputs $k$ different simple $s-t$ paths, where the kth path we output is a $\oeps$ approximation to the actual kth shortest simple $s-t$ path. The running time of our algorithm is $O(k \eps^{-1} \log^2 n (m + n\log n)) = \wo(km/\eps)$. The fastest \emph{exact} algorithm for this problem has a running time of $O(k(mn + n^2\log\log n)) = \wo(kmn)$ \cite{GL09}. The previous best approximation algorithm was developed by Roditty \cite{R07}; it has a stretch of $3/2$ and a running time of $\wo(km\sqrt{n})$ (it does not work for replacement paths). \\ \\ Note that all of our running times are nearly optimal except for the $O(\log(nC/c))$ factor in the replacement paths algorithm. Also, our algorithm can solve the variant of approximate replacement paths where we avoid vertices instead of edges.

A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics

Authors: T-H. Hubert Chan (Max-Planck-Institut fuer Informatik) Khaled Elbassioni (Max-Planck-Institut fuer Informatik)

Topics: Algorithm Analysis, Approximation Algorithms, Optimization

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a collection of $n$ subsets (regions or neighborhoods) in the underlying metric space. We give a QPTAS when the regions are what we call $\alpha$-fat weakly disjoint. This notion combines the existing notions of diameter variation, fatness and disjointness for geometric objects and generalizes these notions to any arbitrary metric space. Intuitively, the regions can be grouped into a bounded number of types, where in each type, the regions have similar upper bounds for their diameters, and each such region can designate a point such that these points are far away from one another. Our result generalizes the PTAS for TSPN on the Euclidean plane by Mitchell~\cite{M07} and the QPTAS for TSP on doubling metrics by Talwar~\cite{Tal04}. We also observe that our techniques directly extend to a QPTAS for the Group Steiner Tree Problem on doubling metrics, with the same assumption on the groups.

A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing.

Authors: Aparna Das (Brown University) Claire Mathieu (Brown University)

Topics: Approximation Algorithms, Graph Algorithms

In the capacitated vehicle routing problem, introduced by Dantzig and Ramser in 1959, we are given the locations of n customers and a depot, along with a vehicle of capacity k, and wish to find a minimum length collection of tours, each starting from the depot and visiting at most k customers, whose union covers all the customers. We give a quasi-polynomial time approximation scheme for the setting where the customers and the depot are on the plane, and distances are given by the Euclidean metric.

Fully-Functional Succinct Trees

Authors: Kunihiko Sadakane (National Institute of Informatics) Gonzalo Navarro (University of Chile)

Topics: Compression, Data Structures

We propose new succinct representations of ordinal trees, which have been studied extensively. It is known that any $n$-node static tree can be represented in $2n + o(n)$ bits and various operations on the tree can be supported in constant time under the word-RAM model. However existing data structures are not satisfactory in both theory and practice because (1) the lower-order term is $\Omega(n \log\log n/\log n)$ and cannot be neglected, (2) the hidden constant is also large, and (3) the data structures are complicated and difficult to be implemented. We propose a simple and flexible data structure, called the range min-max tree, that reduces the large number of relevant tree operations considered in the literature, to a few primitives that are carried out in constant time on sufficiently small trees. The result is extended to trees of arbitrary size, achieving $2n + O(n /\polylog(n))$ bits of space. The redundancy is significantly lower than any previous proposal, and the data structure is easily implemented.

Online Learning with Queries

Authors: Chao-Kai Chiang (Academia Sinica) Chi-Jen Lu (Academia Sinica)

Topics: Learning, Online problems, Probability

In the standard online learning problem, a player has to iteratively choose an action before knowing anything about the corresponding loss. However, there are situations in which it seems possible for the player to spend some effort or resources to collect some prior information before her action. This motivates us to study a variant of the online learning problem, in which the player is allowed to query $B$ bits from the loss vector in each iteration before choosing her action. We provide an algorithm for this problem. Suppose each loss value is represented by $K$ bits and distinct loss values differ by at least $\delta$, and suppose there are $N$ actions to choose and $T$ rounds to play. Then our algorithm achieves a regret of the following form. Before $B$ approaching $B_1 = NK/2$, the regret stays at $O(\sqrt{T \ln N})$, and after $B$ exceeding $B_1$ but before approaching $B_2 = NK/2 + 3K - 1$, the regret drops slightly to $O(\sqrt{(T\ln N)/N})$, while after $B$ exceeding $B_2$, the regret takes a dramatic drop to $(N\ln N)/\delta$. Our algorithm is in fact close to optimal as we also provide a regret lower bound which almost matches the regret upper bound achieved by the algorithm.

On the Exact Space Complexity of Sketching and Streaming Small Norms

Authors: Daniel M. Kane (Harvard University) Jelani Nelson (MIT) David P. Woodruff (IBM Almaden)

Topics: Streaming Algorithms

We settle the 1-pass space complexity of (1+eps)-approximating the Lp norm, for real p with 1 <= p <= 2, of a length-n vector updated in a length-m stream with updates to its coordinates. We assume the updates are integers in the range [-M, M]. In particular, we show the space required is Theta(eps^{-2}*log(mM) + loglog(n)) bits. Our result also holds for 0 < g="(V,E)" x="R" q =" \left\{">0. We present a new algorithm for the ATSPP problem that has approximation ratio of O(log n), matching the best known ones, but whose analysis also bounds the integrality gap of the LP relaxation of ATSPP by the same factor. This solves an open problem posed by Chekuri and Pal (2007). We then pursue a deeper study of this LP and its variations and their use in approximating directed latency. Our second major result is an O(log n)-approximation to the directed latency problem. This also places an O(log n) bound on the integrality gap of a new LP relaxation of the latency problem that we introduce. We note that this is essentially the best possible ratio unless an asymptotically better approximation exists for the well-studied asymmetric traveling salesman tour problem.

Data Structures for Range Minimum Queries in Multidimensional Arrays

Authors: Hao Yuan (Purdue University) Mikhail J. Atallah (Purdue University)

Topics: Algorithm Analysis, Data Structures, Geometry, Pattern Matching

Given a d-dimensional array A with N entries, the Range Minimum Query (RMQ) asks for the minimum element within a contiguous subarray of A. The 1D RMQ problem has been studied intensively because of its relevance to the Nearest Common Ancestor problem and its important use in stringology. If constant-time query answering is required, linear time and space preprocessing algorithms were known for the 1D case, but not for the higher dimensional cases. In this paper, we give the first linear-time preprocessing algorithm for arrays with fixed dimension, such that any range minimum query can be answered in constant time. This improves the preprocessing time over all previous work under the same model, i.e., RAM with logarithmic word size.

Incentive Compatible Budget Elicitation in Multi-unit Auctions

Authors: Sayan Bhattacharya (Duke University) Vincent Conitzer (Duke University) Kamesh Munagala (Duke University) Lirong Xia (Duke University)

Topics: Economics, Mechanism Design

In this paper, we consider the problem of designing incentive compatible auctions for multiple (homogeneous) units of a good, when bidders have private valuations and private budget constraints. When only the valuations are private and the budgets are public, Dobzinski et al show that the adaptive clinching auction is the unique incentive-compatible auction achieving Pareto-optimality. They further show that this auction is not truthful with private budgets, so that there is no deterministic Pareto-optimal auction with private budgets. Our main contribution is to show the following Budget Monotonicity property of this auction: When there is only one infinitely divisible good, a bidder cannot improve her utility by reporting a budget smaller than the truth. This implies that the adaptive clinching auction is incentive compatible when over-reporting the budget is not possible (for instance, when funds must be shown upfront). We can also make reporting larger budgets suboptimal with a small randomized modification to the auction. In either case, this makes the modified auction Pareto-optimal with private budgets. We also show that the Budget Monotonicity property does not hold for auctioning indivisible units of the good, showing a sharp contrast between the divisible and indivisible cases. The Budget Monotonicity property also implies other improved results in this context. For revenue maximization, the same auction improves the best-known competitive ratio due to Abrams by a factor of 4, and asymptotically approaches the performance of the optimal single-price auction. Finally, we consider the problem of revenue maximization (or social welfare) in a Bayesian setting. We allow the bidders have public size constraints (on the amount of good they are willing to buy) in addition to private budget constraints. We show a simple poly-time computable 5.83-approximation to the optimal Bayesian incentive compatible mechanism, that is implementable in dominant strategies. Our technique again crucially needs the ability to prevent bidders from over-reporting budgets via randomization. We show the approximation result via designing a rounding scheme for an LP relaxation of the problem, which may be of independent interest.

Sharp kernel clustering algorithms and their associated Grothendieck inequalities

Authors: Subhash Khot (Courant Institute) Assaf Naor (Courant Institute)

Topics: Algorithm Analysis, Approximation Algorithms, Complexity, Geometry, Learning, Optimization

In the kernel clustering problem we are given a (large) $n\times n$ symmetric positive semidefinite matrix $A=(a_{ij})$ with $\sum_{i=1}^n\sum_{j=1}^n a_{ij}=0$ and a (small) $k\times k$ symmetric positive semidefinite matrix $B=(b_{ij})$. The goal is to find a partition $\{S_1,\ldots,S_k\}$ of $\{1,\ldots n\}$ which maximizes $ \sum_{i=1}^k\sum_{j=1}^k \left(\sum_{(p,q)\in S_i\times S_j}a_{pq}\right)b_{ij}$. We design a polynomial time approximation algorithm that achieves an approximation ratio of $\frac{R(B)^2}{C(B)}$, where $R(B)$ and $C(B)$ are geometric parameters that depend only on the matrix $B$, defined as follows: if $b_{ij} = \langle v_i, v_j \rangle$ is the Gram matrix representation of $B$ for some $v_1,\ldots,v_k\in \R^k$ then $R(B)$ is the minimum radius of a Euclidean ball containing the points $\{v_1, \ldots, v_k\}$. The parameter $C(B)$ is defined as the maximum over all measurable partitions $\{A_1,\ldots,A_k\}$ of $\R^{k-1}$ of the quantity $\sum_{i=1}^k\sum_{j=1}^k b_{ij}\langle z_i,z_j\rangle$, where for $i\in \{1,\ldots,k\}$ the vector $z_i\in \R^{k-1}$ is the Gaussian moment of $A_i$, i.e., $z_i=\frac{1}{(2\pi)^{(k-1)/2}}\int_{A_i}xe^{-\|x\|_2^2/2}dx$. We also show that for every $\eps > 0$, achieving an approximation guarantee of $(1-\e)\frac{R(B)^2}{C(B)}$ is Unique Games hard.

On the Optimality of Spiral Search

Authors: Elmar Langetepe (University of Bonn, Institute of Computer Science I)

Topics: Algorithm Analysis, Combinatorics, Complexity, Geometry, Online problems

Searching for a point in the plane is a well-known search game problem introduced in the early eigthies. The best known search strategy is given by a spiral and achieves a \emph{competitive ratio} of $17.289\ldots$ It was shown by Gal \cite{g-sg-80} that this strategy is the best strategy among all \emph{monotone} and \emph{periodic} strategies. Since then it was unknown whether the given strategy is optimal in general. This paper settles this old open fundamental search problem and shows that spiral search is indeed optimal. The given problem can be considered as the continous version of the well-known $m$-ray search problem and also appears in several non-geometric applications and modifications. Therefore the optimality of spiral search is an important questions considered by many researchers in the last decades. We answer the logarithmic spiral conjecture for the given problem. The lower bound construction might be helpful for similar settings, it also simplifies existing proofs on classical $m$-ray search.

Cell-probe lower bounds for prefix sums and matching brackets

Authors: Emanuele Viola (Northeastern University)

Topics: Combinatorics, Complexity, Data Structures, Databases and Information Retrieval

We prove that to store n bits x0... x1 so that each prefix sum (a.k.a. rank) query Sum(i) := {k <> 0, problem p-FOA is strongly NP-hard. *) Even the special case with equi-distant cameras is strongly NP-hard. This settles a question left open in Isler et al. (2005). As our main contribution, we fully resolve the approximability status of p-FOA: *) For every real p, problem p-FOA possesses a PTAS. Our PTAS extends the results and ideas of Isler et al. (2005) for the equi-distant special case. The design of our PTAS is quite intricate, and introduces a number of new ideas to the area. Reference: V. Isler, S. Khanna, J.R. Spletzer, C.J. Taylor (2005). Target tracking with distributed sensors: The focus of attention problem. Computer Vision and Image Understanding 100, 225--247.

A locality-sensitive hash for real vectors

Authors: Tyler Neylon (Bynomial, Inc.)

Topics: Approximation Algorithms, Databases and Information Retrieval, Geometry, Optimization

We present a simple and practical algorithm for the $c-$approximate near neighbor problem ($c-$NN): given $n$ points $P\subset\R^d$ and radius $R$, build a data structure which, given $q\in\R^d$, can with probability $1-\delta$ return a point $p\in P$ with $\mathsf{dist}(p,q)\le cR$ if there is any $p^*\in P$ with $\mathsf{dist}(p^*,q)\le R$. For $c=d+1$, our algorithm deterministically ($\delta=0$) preprocesses in time $O(nd\log d)$, space $O(dn)$, and answers queries in expected time $O(d^2)$; this is the first known algorithm to deterministically guarantee an $O(d)-$NN solution in constant time with respect to $n$ for all $\ell_p$ metrics. A probabilistic version empirically achieves useful $c$ values ($c < t="O(d^2\log{n})$)" t="O(d^2\log{n})$" d="O(\log{n}/\log\log{n})$." k="b(1+o_b(1))/\ln{b}." k="Cb/\ln{b}" c="1" s =" n," i="1,2,\dots,k$." k="O((\log"> 0$. Thus our hidden constant in this case is dramatically smaller than Robertson-Seymour's. In addition, if an input graph $G$ is either $4$-edge-connected planar or Eulerian planar, then our algorithm still runs in polynomial time even if $k$ is not fixed but $k = O((\log n)^{\frac{1}{2}-\epsilon})$ for some $\epsilon > 0$. Moreover, if an input graph is either $4$-edge-connected $H$-minor-free or Eulerian $H$-minor-free, then our algorithm still runs in polynomial time even if $k$ is not fixed but $k=O((\log \log n)^{\frac{1}{2}-\epsilon})$ for some $\epsilon > 0$. (3) We also give our own algorithm for the edge-disjoint paths problem in general graphs. We basically follow Robertson-Seymour's algorithm, but we cut half of the proof of the correctness for their algorithm. In addition, the time complexity of our algorithm is $O(n^2)$, which is faster than Robertson and Seymour's.

Coresets and Sketches for High Dimensional Subspace Approximation Problems

Authors: Dan Feldman (School of Computer Science; Tel Aviv University; Tel Aviv 69978, Israel) Morteza Monemizadeh (Department of Computer Science, University of Dortmund; , Germany) Christian Sohler (Department of Computer Science, University of Dortmund; , Germany) David P. Woodruff (IBM Almaden Research Center, San Jose, CA)

Topics: Approximation Algorithms, Geometry, Learning, Streaming Algorithms, Sublinear Algorithms

Given a point set $P$ in $\REAL^d$, an $F_q(\ell_p)$-subspace approximation problem asks for a subspace that minimizes the sum of $q$-th powers of $\ell_p$-distances to this subspace. In this paper we develop techniques for subspace approximation, regression, and matrix approximation that can be used to deal with massive data sets in high dimensional spaces. In particular, we develop coresets and sketches, i.e. small space representations that approximate the input point set $P$ with respect to a subspace approximation problem. Our results are: \begin{itemize} \item A dimensionality reduction method that can be applied to $F_q(\ell_p)$-clustering and shape fitting problems \cite{DDHKM09, Har06c}. \item The first strong coreset for $F_1(\ell_2)$-subspace approximation in high dimensional spaces, i.e. of size polynomial in the dimension of the space. \item A $(1+\epsilon)$-approximation algorithm for the $j$-dimensional $F_1(\ell_2)$-subspace approximation problem with running time $O(nd (j/\eps)^{O(1)} + (n+d) 2^{O(j/\epsilon)^{O(1)}})$. \item A streaming algorithm that maintains a coreset for the $F_1(\ell_2)$-subspace approximation problem and uses $\tilde{O}(d(\frac{j2^{ O(\sqrt{\log n})}}{\epsilon^2})^{\poly(j)})$ space, where the space gives the number of memory cells used. \item Several streaming algorithm with bounded precision in the turnstile model. We significantly extend the results of \cite{CW09} for approximate linear regression, distance to subspace approximation, and best rank-$j$ approximation, to error measures other than the Frobenius norm, obtaining $1$-pass sublinear, near-optimal space complexity for these problems. Our time is always polynomial for constant $j/\eps$, even for the time to extract a $(1+\eps)$-approximation to the best rank-$j$ subspace from the sketch. \end{itemize} =========================================================================== 1-pass Relative-Error L_p-Sampling with Applications --------------------------------------------------------------------------- Authors: Morteza Monemizadeh (Department of Computer Science, University of Dortmund; , Germany) David P. Woodruff (IBM Almaden Research Center, San Jose, CA) Topics: Streaming Algorithms --------------------------------------------------------------------------- For any p in [1,2], we give a 1-pass poly((log n)/epsilon)-space algorithm which, given a data stream of length m with insertions and deletions of an n-dimensional vector a with updates in the range {-M, -M+1, ..., M-1, M} outputs a sample of {1, 2, ..., m} for which for all i the probability that i is returned is (1 +- epsilon)|a_i|^p/F_p(a) + n^{-C}, where a_i denotes the (possibly negative) value of coordinate i, F_p(a) = sum_{i=1}^m |a_i|^p = ||a||_p^p denotes the p-th frequency moment (i.e., the p-th power of the L_p norm), and C > 0 is an arbitrarily large constant. Here we assume that n,m, and M are polynomially related. Our generic sampling framework improves and unifies algorithms for several communication and streaming problems, including cascaded norms, heavy hitters, and moment estimation. It also gives the first relative-error forward sampling algorithm in a data stream with deletions, answering an open question of Cormode et al. =========================================================================== One-Counter Markov Decision Processes --------------------------------------------------------------------------- Authors: Tomas Brazdil (Faculty of Informatics, Masaryk University) Vaclav Brozek (Faculty of Informatics, Masaryk University) Kousha Etessami (School of Informatics, University of Edinburgh) Antonin Kucera (Faculty of Informatics, Masaryk University) Dominik Wojtczak (CWI, Amsterdam) Topics: Complexity, Game Theory, Markov Chains, Optimization, Probability --------------------------------------------------------------------------- We study the computational complexity of central analysis problems for One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented, countable-state MDPs. OC-MDPs extend finite-state MDPs with an unbounded counter. The counter can be incremented, decremented, or not changed during each state transition, and transitions may be enabled or not depending on both the current state and on whether the counter value is 0 or not. Some states are ``random'', from where the next transition is chosen according to a given probability distribution, while other states are ``controlled'', from where the next transition is chosen by the controller. Different objectives for the controller give rise to different computational problems, aimed at computing optimal achievable objective values and optimal strategies. OC-MDPs are in fact equivalent to a controlled extension of (discrete-time) Quasi-Birth-Death processes (QBDs), a purely stochastic model heavily studied in queueing theory and applied probability. They can thus be viewed as a natural ``adversarial'' extension of a classic stochastic model. They can also be viewed as a natural probabilistic/controlled extension of classic one-counter automata. OC-MDPs also subsume (as a very restricted special case) a recently studied MDP model called ``solvency games'' that model a risk-averse gambling scenario. Basic computational questions for OC-MDPs include ``termination'' questions and ``limit'' questions, such as the following: does the controller have a strategy to ensure that the counter (which may, for example, count the number of jobs in the queue) will hit value 0 (the empty queue) almost surely (a.s.)? Or that the counter will have lim sup value infinity, a.s.? Or, that it will hit value 0 in a selected terminal state, a.s.? Or, in case such properties are not satisfied almost surely, compute their optimal probability over all strategies. We provide new upper and lower bounds on the complexity of such problems. Specifically, we show that several quantitative and almost-sure limit problems can be answered in polynomial time, and that almost-sure termination problems (without selection of desired terminal states) can also be answered in polynomial time. On the other hand, we show that the almost-sure termination problem with selected terminal states is PSPACE-hard and we provide an exponential time algorithm for this problem. We also characterize classes of strategies that suffice for optimality in several of these settings. Our upper bounds combine a number of techniques from the theory of MDP reward models, the theory of random walks, and a variety of automata-theoretic methods. =========================================================================== How far can you reach? --------------------------------------------------------------------------- Authors: Ciprian Borcea (Dept. of Mathematics, Rider University) Ileana Streinu (Computer Science Department, Smith College) Topics: Geometry, Metric Embeddings, Robotics --------------------------------------------------------------------------- Robot Arm Reachability, the problem of computing the extremal configurations of a 3D revolute-jointed manipulator, is a long standing open problem in Robotics. In this paper we completely solve it for orthogonal polygonal chains, which appear as a special case of a larger family, fully characterized here by a technical condition. Until now, in spite of the practical importance of the problem, only numerical optimization heuristics were available. These were not even guaranteed to produce the optimum; in fact, the problem was not even known to be computationally solvable, and in practice, the numerical heuristics were applicable only to small problem sizes. We present surprisingly elementary and efficient (mostly linear time) algorithms for four fundamental problems: (1) finding the minimum and the maximum reach value, (2) finding an extremal configuration (or enumerating all of them), (3) folding a given chain to a given extremal position, and (4) folding a chain in a way that changes the endpoint distance function monotonically. Our theoretical results reduce the first problem to finding a shortest path between two vertices in an associated simple triangulated polygon, and the last problem to a simple version of the planar Carpenter's Rule Problem. =========================================================================== Region growing for multi-route cuts --------------------------------------------------------------------------- Authors: Shuchi Chawla (University of Wisconsin - Madison) Siddharth Barman (University of Wisconsin - Madison) Topics: Approximation Algorithms, Graph Algorithms, Optimization --------------------------------------------------------------------------- We study a number of \emph{multi-route cut} problems: given a graph $G=(V,E)$ and connectivity thresholds $k_{(u,v)}$ on pairs of nodes, the goal is to find a minimum cost set of edges or vertices the removal of which reduces the connectivity between every pair $(u,v)$ to strictly below its given threshold. These problems arise in the context of reliability in communication networks; They are natural generalizations of traditional minimum cut problems where the thresholds are either $1$ (we want to completely separate the pair) or $\infty$ (we don't care about the connectivity for the pair). We provide the first non-trivial approximations to a number of variants of the problem including for both node-disjoint and edge-disjoint connectivity thresholds. A main contribution of our work is an extension of the region growing technique for approximating minimum multicuts to the multi-route setting. When the connectivity thresholds are either $2$ or $\infty$ (the ``$2$-route cut'' case), we obtain polylogarithmic approximations while satisfying the thresholds exactly. For arbitrary connectivity thresholds this approach leads to bicriteria approximations where we approximately satisfy the thresholds and approximately minimize the cost. We present a number of different algorithms achieving different cost-connectivity tradeoffs. =========================================================================== Faster exponential time algorithms for the shortest vector problem --------------------------------------------------------------------------- Authors: Daniele Micciancio (University of California, San Diego) Panagiotis Voulgaris (University of California, San Diego) Topics: Algorithm Analysis, Cryptography, Experimental Algorithmics --------------------------------------------------------------------------- We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$. This improves the best previously known algorithm by Ajtai, Kumar and Sivakumar [Proceedings of STOC 2001] which was shown by Nguyen and Vidick [J. Math. Crypto. 2(2):181--207] to run in time $2^{5.9n}$ and space $2^{2.95n}$. We also present a practical variant of our algorithm which provably uses an amount of space proportional to $\tau_n$, the ``kissing'' constant in dimension $n$. Based on the best currently known upper and lower bounds on the kissing constant, the space complexity of our second algorithm is provably bounded by $2^{0.41n}$, and it is likely to be at most $2^{0.21n}$ in practice. No upper bound on the running time of our second algorithm is currently known, but experimentally the algorithm seems to perform fairly well in practice, with running time $2^{0.48n}$, and space complexity $2^{0.18n}$. =========================================================================== Finding the Jaccard Median --------------------------------------------------------------------------- Authors: Flavio Chierichetti (Sapienza University of Rome) Ravi Kumar (Yahoo! Research Santa Clara) Sandeep Pandey (Yahoo! Research Santa Clara) Sergei Vassilvitskii (Yahoo! Research New York) Topics: Approximation Algorithms, Optimization --------------------------------------------------------------------------- The median problem in the weighted Jaccard metric was analyzed for the first time by Sp\"ath in 1981. Up until now, only an exponential-time exact algorithm was known. We (a) show that the problem does not admit a FPTAS (assuming P $\ne$ NP), even when restricted to binary vectors and (b) give a PTAS for the general weighted Jaccard metric. The PTAS leverages of a number of different algorithmic ideas and our hardness result makes use of a gadget which appears to be ``unique'' in interesting ways. =========================================================================== The scaling window for a random graph with a given degree sequence --------------------------------------------------------------------------- Authors: Hamed Hatami (University of Toronto) Michael Molloy (University of Toronto) Topics: Graph Theory, Random Graphs --------------------------------------------------------------------------- We consider a random graph on a given degree sequence $D$, satisfying certain conditions. We focus on two parameters $Q=Q(D), R=R(D)$. Molloy and Reed proved that $Q=0$ is the threshold for the random graph to have a giant component. We prove that if $|Q|=O(n^{-1/3} R^{2/3})$ then, with high probability, the size of the largest component of the random graph will be of order $\Theta(n^{2/3}R^{-1/3})$. If $Q$ is asymptotically larger/smaller that $n^{-1/3}R^{2/3}$ then the size of the largest component is asymptotically larger/smaller than $n^{2/3}R^{-1/3}$. In other words, we establish the scaling window. =========================================================================== Energy Efficient Scheduling for Data Centers via Partial Shutdown --------------------------------------------------------------------------- Authors: Samir Khuller (University of Maryland) Jian Li (University of Maryland) Barna Saha (University of Maryland) Topics: Approximation Algorithms, Scheduling and Resource Allocation --------------------------------------------------------------------------- Motivated by issues of saving energy in data centers we define a collection of new problems referred to as ``machine activation'' problems. The central framework we introduce considers a collection of $m$ machines (unrelated or related) with each machine $i$ having an {\em activation cost} of $a_i$. There is also a collection of $n$ jobs that need to be performed and $p_{ij}$ is the processing time of job $j$ on machine $i$. Standard scheduling models assume that the set of machines is fixed and all machines are available. However, in our setting, we assume that there is an activation cost budget of $A$ -- we would like to {\em select} a subset $S$ of the machines to activate with total cost $a(S) \le A$ and {\em find} a schedule for the $n$ jobs on the machines in $S$ minimizing the makespan (or any other metric). We consider both the unrelated machines setting, as well as the setting of scheduling uniformly related parallel machines, where machine $i$ has cost $a_i$ and speed $s_i$, and the processing time of job $j$ on machine $i$ is $p_{ij} = \frac{p_j}{s_i}$, where $p_j$ is the processing requirement of job $j$. For the general unrelated machine activation problem, our main results are that if there is a schedule with makespan $T(A)$ and activation cost $A$ then we can obtain a schedule with makespan $\makespanconstant T(A)$ and activation cost $\costconstant A$, for any $\epsilon >0$. We also consider assignment costs for jobs as in the generalized assignment problem, and using our framework, provide algorithms that minimize the machine activation and the assignment cost simultaneously. For the uniformly related parallel machine scheduling problem, we develop a polynomial time scheme that outputs a schedule with the property that the activation cost of the subset of machines is at most $A$ and the makespan is at most $(1+\epsilon) T(A)$ for any $\epsilon >0$. For the special case of $m$ identical speed machines, the machine activation problem is trivial, since the cheapest subset of $k$ machines is always the best choice if the optimal solution activates $k$ machines. In addition, we consider the case when some jobs can be dropped (and are treated as outliers). =========================================================================== Sharp Dichotomies for Regret Minimization in Metric Spaces --------------------------------------------------------------------------- Authors: Robert Kleinberg (Cornell University) Aleksandrs Slivkins (Microsoft Research (SVC)) Topics: Algorithm Analysis, Learning, Online problems, Optimization --------------------------------------------------------------------------- The Lipschitz multi-armed bandit (MAB) problem generalizes the classical multi-armed bandit problem by assuming one is given side information consisting of a priori upper bounds on the difference in expected payoff between certain pairs of strategies. Classical results of Lai and Robbins and Auer et al imply a logarithmic regret bound for the Lipschitz MAB problem on finite metric spaces. Recent results on continuum-armed bandit problems and their generalizations imply lower bounds of $\sqrt{t}$, or stronger, for many infinite metric spaces such as the unit interval. Is this dichotomy universal? We prove that the answer is yes: for every metric space, the optimal regret of a Lipschitz MAB algorithm is either bounded above by any $f\in \omega(\log t)$, or bounded below by any $g\in o(\sqrt{t})$. Perhaps surprisingly, this dichotomy does not coincide with the distinction between finite and infinite metric spaces; instead it depends on whether the completion of the metric space is compact and countable. Our proof connects upper and lower bound techniques in online learning with classical topological notions such as perfect sets and the Cantor-Bendixson theorem. We also consider the "full-feedback" (a.k.a., "best-expert") version of Lipschitz MAB problem, termed the "Lipschitz experts problem", and show that this problem exhibits a similar dichotomy. We proceed to give nearly matching upper and lower bounds on regret in the Lipschitz experts problem on uncountable metric spaces. These bounds are of the form $\tilde{\Theta}(t^\gamma)$, where the exponent $\gamma\in [\tfrac12, 1]$ depends on the metric space. To characterize this dependence, we introduce a novel dimensionality notion tailored to the experts problem. Finally, we show that both Lipschitz bandits and Lipschitz experts problems become completely intractable (in the sense that no algorithm has regret $o(t)$) if and only if the completion of the metric space is non-compact. =========================================================================== Lower Bounds for Sparse Recovery --------------------------------------------------------------------------- Authors: khanh do ba (MIT CSAIL) piotr indyk (MIT CSAIL) eric price (MIT CSAIL) Topics: Approximation Algorithms, Coding Theory, Compression, Geometry, Information Theory, Streaming Algorithms, Sublinear Algorithms --------------------------------------------------------------------------- Over the recent years, a new *linear* method for compressing high-dimensional data has been discovered. For an n-dimensional vector x, its *sketch* is equal to Ax, where A is an m x n matrix, possibly chosen at random. Although typically the sketch length m is much smaller than the number of dimensions n, the sketch often contains plenty of information about x. A particularly useful and well-studied problem is that of sparse recovery: given Ax, recover a k-sparse vector x* (with at most k non-zeros) such that ||x-x*||_p <= C min_{k-sparse x'} ||x-x'||_q for some norm parameters p and q and an approximation factor C=C(k). Sparse recovery has numerous applications to areas such as data stream computing and compressed sensing. It is known that there exist matrices A that achieve the above guarantee with p=q=1 and constant C (in fact, even somewhat stronger bounds), with sketch length m=O(k log (n/k)). However, perhaps surprisingly, it is not known if this bound can be improved any further, even though matching lower bounds are known for specific *algorithms*, specific *matrix types*, or other recovery scenarios (e.g., involving measurement noise). The lack of tight lower bounds represents a major gap in our understanding of the problem. In this paper we make significant progress on this issue. In particular we show that: - in the deterministic case, where we require one matrix A to work for all signals x, we show a tight lower bound of Omega(k log (n/k)), thus resolving the issue completely - in the randomized case, where we require that a matrix A chosen at random from some distribution should work for a *fixed* vector x with probability at least 1-1/n, we show a lower bound of Omega(log n / log log n) =========================================================================== The Complexity of Guarding Terrains --------------------------------------------------------------------------- Authors: James King (McGill University) Erik Krohn (University of Iowa) Topics: Complexity, Geometry --------------------------------------------------------------------------- A set G of points on a 1.5-dimensional terrain, also known as an x-monotone polygonal chain, is said to guard the terrain if any point on the terrain is ‘seen’ by a point in G. Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain. The minimum terrain guarding problem asks for a minimum guarding set for the given input terrain. We prove that the decision version of this problem is NP-hard. This solves a significant open problem and complements recent positive approximability results for the optimization problem. Our proof uses a reduction from PLANAR 3-SAT. We build gadgets capable of ‘mirroring’ a consistent variable assignment back and forth across a main valley. The structural simplicity of 1.5-dimensional terrains makes it difficult to build general clause gadgets that do not destroy this assignment when they are evaluated. However, we exploit the structure in instances of PLANAR 3-SAT to find very specific operations involving only ‘adjacent’ variables. For these restricted operations we can construct gadgets that allow a full reduction to work. =========================================================================== An (almost) Linear Time Algorithm For Odd Cycles Transversal --------------------------------------------------------------------------- Authors: Ken-ichi Kawarabayashi (National Institute of Informatics) Bruce Reed (McGill University) Topics: Graph Algorithms, Graph Theory --------------------------------------------------------------------------- We consider the following problem, which is called the odd cycles transversal problem. Input: A graph G and an integer k. Output : A vertex set X \in V(G) with at most k vertices such that G-X is bipartite. We present an O(m \alpha(m,n)) time algorithm for this problem for any fixed k, where n,m are the number of vertices and the number of edges, respectively, and the function \alpha(m,n) is the inverse of the Ackermann function. This improves the time complexity of the algorithms by Reed, and by Reed, Smith and Vetta who gave an O(nm) time algorithm for this problem. Our algorithm also implies the edge version of the problem, i.e, there is an edge set X' \in E(G) such that G-X' is bipartite. Using this algorithm and our recent result(SODA'09), we give an O(m \alpha(m,n) + n \log n) algorithm for the following problem for any fixed k: Input: A graph G and an integer k. Output : Determine whether or not there is a half-integral k disjoint odd cycles packing, i.e, k odd cycles C_1,\dots,C_k in G such that each vertex is on at most two of these odd cycles. We also give a simpler proof for the following result by Reed. The Erd\H{o}s-P\'osa property holds for the half-integral disjoint odd cycles packing problem. I.e. either G has a half-integral k disjoint odd cycles packing or G has a vertex set X of order at most f(k) such that G-X is bipartite for some function f of k. Note that the Erd\H{o}s-P\'osa property does not hold for odd cycles in general. =========================================================================== Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families --------------------------------------------------------------------------- Authors: Karthekeyan Chandrasekaran (Georgia Institute of Technology) Daniel Dadush (Georgia Institute of Technology) Santosh Vempala (Georgia Institute of Technology) Topics: Geometry, Markov Chains, Probability --------------------------------------------------------------------------- Star-shaped bodies are an important nonconvex generalization of convex bodies (e.g., linear programming with violations). Here we present an ecient algorithm for sampling a given star-shaped body. The complexity of the algorithm grows polynomially in the dimension and inverse polynomially in the fraction of the volume taken up by the kernel of the star-shaped body. The analysis is based on a new isoperimetric inequality. Our main technical contribution is a tool for proving such inequalities when the domain is not convex. As a consequence, we obtain a polynomial algorithm for computing the volume of such a set as well. In contrast, linear optimization over star-shaped sets is NP-hard. =========================================================================== Resource Minimization for Fire Containment --------------------------------------------------------------------------- Authors: Parinya Chalermsook (University of Chicago) Julia Chuzhoy (TTI-C) Topics: Approximation Algorithms, Graph Algorithms, Scheduling and Resource Allocation --------------------------------------------------------------------------- We consider the following model for fire containment. We are given an undirected graph G=(V,E) with a source vertex s where the fire starts. At each time step, firefighters can save up to k vertices of the graph, while the fire spreads from burning vertices to all their neighbors that have not been saved so far. Our goal is to choose the vertices to be saved at each time step so as to contain the fire. This is a simple mathematical model abstracting the dynamic nature of fire containment and other natural processes, such as, for example, the spread of a perfectly contagious disease, and its containment via vaccination. In this paper we focus on the Resource Minimization Fire Containment (RMFC) problem, where we are additionally given a subset T of vertices called terminals that need to be protected from fire. The objective is to minimize k - the maximum number of vertices to be saved at any time step, so that the fire does not spread to any vertex of T. The problem is hard to approximate up to any factor better than 2 even on trees. We show an $O(\log^*n)$-approximation algorithm for RMFC on trees, by rounding a natural linear programming relaxation of the problem. We also show that an even stronger LP relaxation has an integrality gap of $\Omega(\log^*n)$ on trees. Finally, we consider RMFC on directed layered graphs, and show an O(\log n)-approximation LP-rounding algorithm, matching the integrality gap of the LP relaxation. =========================================================================== Price of Anarchy for Greedy Auctions --------------------------------------------------------------------------- Authors: Brendan Lucier (University of Toronto) Allan Borodin (University of Toronto) Topics: Approximation Algorithms, Game Theory, Mechanism Design --------------------------------------------------------------------------- We consider mechanisms for utilitarian combinatorial allocation problems, where agents are not assumed to be single-minded. This class of problems includes combinatorial auctions, multi-unit auctions, unsplittable flow problems, profit-maximizing scheduling, and others. We study the price of anarchy for such mechanisms, which is a bound on the approximation ratio obtained at any mixed Nash equilibrium. We demonstrate that a broad class of greedy approximation algorithms can be implemented as mechanisms for which the price of anarchy nearly matches the performance of the original algorithm. This is true even in Bayesian settings, where the agents' valuations are drawn from publicly known distributions. Furthermore, for a rich subclass of allocation problems, pure Nash equilibria are guaranteed to exist for these mechanisms. For many problems, the approximation factors obtained at equilibrium improve upon the best known results for deterministic truthful mechanisms. In particular, we exhibit a simple deterministic mechanism for the general combinatorial auction with $O(\sqrt{m})$ price of anarchy. =========================================================================== Inapproximability for planar embedding problems --------------------------------------------------------------------------- Authors: Jeff Edmonds (York University) Anastasios Sidiropoulos (University of Toronto) Anastasios Zouzias (University of Toronto) Topics: Approximation Algorithms, Complexity, Geometry, Metric Embeddings --------------------------------------------------------------------------- We consider the problem of computing a minimum-distortion bijection between two point-sets in R^2. We prove the first non-trivial inapproximability result for this problem, for the case when the distortion is constant. More precisely, we show that there exist constants 0 < k="2$"> Topics: Combinatorics, Learning --------------------------------------------------------------------------- In this paper, we consider the problem of reconstructing a hidden graph with $m$ edges using additive queries. Given a graph $G=(V,E)$ and a set of vertices $S\subseteq V$, an additive query, $Q(S)$, asks for the number of edges in the subgraph induced by $S$. The information theoretic lower bound for the query complexity of reconstructing a graph with $n$ vertices and $m$ edges is $$ O\left(\frac{m\log \frac{n^2}{m}}{\log m}\right).$$ In this paper we give the first polynomial time algorithm with query complexity that matches this lower bound\footnote{In this paper, by optimal we mean asymptotically. That is, up to a constant factor.}. This solves the open problem by [S. Choi and J. Han Kim. Optimal Query Complexity Bounds for Finding Graphs. \emph{STOC} ,749--758 ,2008]. In the paper, we actually show an algorithm for the generalized problem of reconstructing weighted graphs. In the weighted case, an additive query, $Q(S)$, asks for the sum of weights of edges in the subgraph induces by $S$. The complexity of the algorithm also matches the information theoretic lower bound. =========================================================================== EDF-schedulability of synchronous periodic task systems is coNP-hard --------------------------------------------------------------------------- Authors: Friedrich Eisenbrand (Institute of Mathematics, EPFL, Lausanne, Switzerland) Thomas Rothvoß (Institute of Mathematics, EPFL, Lausanne, Switzerland) Topics: Complexity, Number Theory, Scheduling and Resource Allocation --------------------------------------------------------------------------- In the synchronous periodic task model, a set T_1,...,T_n of tasks is given, each releasing jobs of running time c_i and relative deadline d_i at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) is an optimal preemptive uni-processor scheduling policy. For constrained deadlines, i.e. d_i <= p_i, the EDF-schedule is feasible if and only if \[ \forall Q >= 0: \sum_{i=1}^n (\floor{(Q-d_i)/p_i} + 1) * c_i <= Q. \] Despite of an enormous amount of literature dealing with this topic, the complexity status of this test has remained unknown. We prove that testing EDF-schedulability of such a task system is coNP-hard. This solves Problem 2 from the survey "Open Problems in Real-time Scheduling" by Baruah & Pruhs. The hardness result is achieved by applying recent results on inapproximability of Diophantine approximation. =========================================================================== Algorithmic Lower Bounds for Problems Parameterized by Clique-width --------------------------------------------------------------------------- Authors: Fedor V. Fomin (University of Bergen) Petr A. Golovach (University of Bergen) Daniel Lokshtanov (University of Bergen) Saket Saurabh (University of Bergen) Topics: Algorithm Analysis, Complexity, Graph Algorithms --------------------------------------------------------------------------- Many NP-hard problems can be solved efficiently when the input is restricted to graphs of bounded tree-width or clique-width. In particular, by the celebrated result of Courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the tree-width of the input graph. On the other hand if we restrict ourselves to graphs of clique-width at most $t$, then there are many natural problems for which the running time of the best known algorithms is of the form $n^{f(t)}$, where $n$ is the input length and $f$ is some function. It was an open question whether natural problems like Graph Coloring, Max-Cut, Edge Dominating Set, and Hamiltonian Path are fixed parameter tractable when parameterized by the clique-width of the input graph. As a first step toward obtaining lower bounds for clique-width parameterizations, in [SODA 2009], we showed that unless $FPT\neqW[1]$, there is no algorithm with run time $O(g(t)\cdot n^c)$, for some function $g$ and a constant $c$ not depending on $t$, for Graph Coloring, Edge Dominating Set and Hamiltonian Path. But the lower bounds obtained in [SODA 2009] are weak when compared to the upper bounds on the time complexity of the known algorithms for these problems when parameterized by the clique-width. In this paper, we obtain the asymptotically tight bounds for Max-Cut and Edge Dominating Set by showing that both problems 1. cannot be solved in time $f(t)n^{o(t)}$, unless Exponential Time Hypothesis (ETH) collapses; and 2. can be solved in time $n^{O(t)}$, where $f$ is an arbitrary function of $t$, on input of size $n$ and clique-width at most $t$. We obtain our lower bounds by giving non-trivial structure-preserving ``linear FPT reductions". =========================================================================== An Improved Competitive Algorithm for Reordering Buffer Management --------------------------------------------------------------------------- Authors: Noa Avigdor-Elgrabli (Technion) Yuval Rabani (Technion) Topics: Approximation Algorithms, Online problems --------------------------------------------------------------------------- We design and analyze an on-line reordering buffer management algorithm with improved $O\left(\frac{\log k}{\log\log k}\right)$ competitive ratio for non-uniform costs, where $k$ is the buffer size. This improves on the best previous result (even for uniform costs) of Englert and Westermann (ICALP 2005) giving $O(\log k)$ competitive ratio, which was also the best (off-line) approximation algorithm for this problem. Our analysis is based on an intricate dual fitting argument using a linear programming relaxation for the problem that we introduce in this paper. =========================================================================== Deterministic Algorithms for the Lovasz Local Lemma --------------------------------------------------------------------------- Authors: Karthekeyan Chandrasekaran (Gatech) Navin Goyal (Microsoft Research, India) Bernhard Haeupler (MIT) Topics: Algorithm Analysis, Combinatorics, Distributed and Parallel Computing, Probability, Random Structures --------------------------------------------------------------------------- The Lovasz Local Lemma (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d<2^k/e k="\omega(1)" p="NP." n =" M" n =" o(2^sqrt(B))." m =" \tilde{\omega}(n^2)$." p =" NP," p="NP."> 0, unless NP has subexponential-time randomized algorithms. Our lower bounds rely on a mixture of geometric and algebraic techniques, whereas the upper bounds use a novel rounding scheme to transform a mechanism with randomized outcomes into one with deterministic outcomes while losing only a bounded amount of revenue. =========================================================================== Covering a symmetric crossing supermodular function with partition constraints --------------------------------------------------------------------------- Authors: Attila Bernáth (MTA-ELTE Egerváry Research Group, Budapest, Hungary) Roland Grappe (Laboratoire G-SCOP, Grenoble, France) Zoltán Szigeti (Laboratoire G-SCOP, Grenoble, France) Topics: Combinatorics, Graph Algorithms, Graph Theory, Optimization --------------------------------------------------------------------------- Given a symmetric crossing supermodular set function $p$ on $V$ and a partition $\mathcal{P}$ of $V$, we solve the problem of finding a graph $G=(V,E)$ having edges only between the classes of $\mathcal{P}$ such that each cut $X$ contains at least as many edges of $G$ as the function value $p(X)$. The objective is to minimize the number of edges of $G$. This problem is a common generalization of the global edge-connectivity augmentation of a graph with partition constraints, which was solved by Bang-Jensen, Gabow, Jord\'an and Szigeti and the problem of covering a symmetric crossing supermodular set function solved by Bencz\'ur and Frank. Our problem can be considered as an abstract form of the problem of global edge-connectivity augmentation of a hypergraph with multipartite graph, which was earlier solved by the authors. =========================================================================== A Max-Flow/Min-Cut Algorithm for a Class of Wireless Networks --------------------------------------------------------------------------- Authors: S. M. Sadegh Tabatabaei Yazdi (Student, Texas A&M university) Serap A. Savari (Professor, Texas A&M university) Topics: Combinatorics, Information Theory, Optimization --------------------------------------------------------------------------- The linear deterministic model of relay channels is a generalization of the traditional directed network model which has become popular in the study of the flow of information over wireless communication networks. The max-flow/min-cut theorem of Ford and Fulkerson has recently been extended to this wireless relay model. This result was first proved by a random coding scheme over large blocks of transmitted signals. We demonstrate the same result with a deterministic, polynomial-time algorithm which takes as input a single transmitted signal instead of a long block of signals. The max-flow/min-cut theorem of Ford and Fulkerson is related to a number of famous results in combinatorics including Hall's marriage theorem. Hall's marriage theorem is a special case of a well-known result in matroid theory and in transversal theory named the Rado-Hall theorem. We show that that the max-flow/min-cut theorem for linear deterministic relay networks is connected to (1) an extension of the Rado-Hall theorem applied to column-partitioned matrices into a two-dimensional transversal theorem for block matrices and (2) a combinatorial result on sequences of block matrices. =========================================================================== Vertices of Degree k in Random Maps --------------------------------------------------------------------------- Authors: Daniel Johannsen (Max-Planck-Institute for Informatics) Konstantinos Panagiotou (Max-Planck-Institute for Informatics) Topics: Combinatorics, Graph Theory, Probability, Random Graphs, Random Structures --------------------------------------------------------------------------- This work is devoted to the study of the typical structure of a random map. Maps are planar graphs embedded in the plane, and are commonly used to describe the topology of geometric arrangements. In particular, the class of all 3-connected planar maps is combinatorially equivalent to the class of all 3-dimensional convex polyhedra. Since the pioneering work of Tutte (Canadian Journal of Mathematics, 1963), maps have become very popular combinatorial objects, and in the meantime a rich theory studying various aspects of maps has evolved. However, much less is known about statistical properties of random maps, i.e., maps drawn uniformly at random from the class of all maps with a given number of edges. A major achievement in this context is the precise description of the so-called core-size of a random map, which was provided by Banderier, Flajolet, Schaeffer, and Soria (Random Structures & Algorithms, 2001). Among several other results, they showed that a random map contains typically a giant (i.e., linear-size) biconnected submap. In this work we study the degree sequences of random maps from families of a certain type, which, among others, includes fundamental map classes like those of biconnected maps, 3-connected maps, and triangulations. In particular, we develop a general framework that allows us to derive relations and exact asymptotic expressions for the expected number of vertices of degree k in random maps from these classes, and also provide accompanying large deviation statements. Extending the work of Gao and Wormald (Combinatorica, 2003) on random general maps, we obtain as results of our framework precise information about the number of vertices of degree k in random biconnected, 3-connected, loopless, and bridgeless maps. =========================================================================== Bidimensionality and Kernels --------------------------------------------------------------------------- Authors: Fedor V. Fomin (Department of Informatics, University of Bergen, Norway) Daniel Lokshtanov (Department of Informatics, University of Bergen, Norway) Saket Saurabh (Department of Informatics, University of Bergen, Norway) Dimitrios M. Thilikos (Department of Mathematics, National and Kapodistrian University of Athens) Topics: Combinatorics, Graph Algorithms, Graph Theory --------------------------------------------------------------------------- Bidimensionality theory appears to be a powerful framework in the development of meta-algorithmic techniques. It was introduced by Demaine et al. [J. ACM 2005] as a tool to obtain sub-exponential time parameterized algorithms for bidimensional problems on $H$-minor free graphs. Demaine and Hajiaghayi [SODA 2005] extended the theory to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this paper, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of {\sl polynomial kernels} for parameterized problems. In parameterized complexity, each problem instance comes with a parameter $k$ and the parameterized problem is said to admit a {\it polynomial kernel} if there is a polynomial time algorithm, called a {\em kernelization} algorithm, that reduces the input instance to an equivalent instance (called {\em kernel}) with size bounded by a polynomial in $k$. We show that ``essentially'' all bidimensioanl problems not only have sub-exponential time algorithms and PTASs but they {\em also} have polynomial kernels, partially answering an open question from [J. ACM 2005] where the existence of linear kernels was conjectured for the first time. In particular, we prove that every minor (resp. contraction) bidimensional problem that satisfies the separation property and is of finite integer index, admits a quadratic kernel for classes of graphs that exclude a fixed graph (resp. an apex graph $H$) $H$ as a minor. Recently, Bodlaender et al.~[FOCS 2009] laid the foundation for obtaining meta-algorithmic results for kernelization and showed that various problems satisfying some logical and compactness properties have polynomial, even linear kernels on graphs of bounded genus. With the use of bidimensionality and hypergraph-based combinatorial arguments, we are able to extended some of these results to minor-free and apex-minor-free graphs. Our results imply that multitude of bidimensional problems, which include {\sc Dominating Set}, {\sc Feedback vertex set}, {\sc Edge Dominating set}, {\sc Vertex Cover}, {\sc $r$-Dominating Set}, {\sc Connected Dominating Set}, {\sc Cycle Packing}, {\sc connected vertex cover}, {\sc Almost Constant Treewidth}, and many other vertex covering and packing problems, admit quadratic kernels on the corresponding graph classes. For most of these problems no polynomial kernels on $H$-minor-free graphs were know prior to our work. =========================================================================== Flow-Cut Gaps for Integer and Fractional Multiflows --------------------------------------------------------------------------- Authors: Chandra Chekuri (University of Illinois, Urbana-Champaign) Bruce Shepherd (McGill University) Christophe Weibel (McGill University) Topics: Graph Theory, Optimization --------------------------------------------------------------------------- Consider a routing problem instance consisting of a demand graph H=(V,E(H)) and a supply graph G=(V,E(G)). If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there exists a feasible multiflow for H if each edge of G is given capacity C. It is well-known that the flow-cut gap may be greater than 1 even in the case where G is the (series-parallel) graph K_{2,3}. In this paper we are primarily interested in the "integer" flow-cut gap. What is the minimum value C such that there exists a feasible integer valued multiflow for H if each edge of G is given capacity C? We formulate a conjecture that states that the integer flow-cut gap is quantitatively related to the fractional flow-cut gap. In particular this strengthens the well-known conjecture that the flow-cut gap in planar and minor-free graphs is O(1) to suggest that the integer flow-cut gap is O(1). We give several technical tools and results on non-trivial special classes of graphs to give evidence for the conjecture and further explore the "primal" method for understanding flow-cut gaps; this is in contrast to and orthogonal to the highly successful metric embeddings approach. Our results include the following: * Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is semi-compliant if its endpoints are joined by a directed path in the resulting oriented graph. We show that if the cut condition holds for a semi-compliant instance and G+H is Eulerian, then an integral routing of H exists. This result includes as a special case, routing on a ring but is not a special case of the Okamura-Seymour theorem. * Using the above result, we show that the integer flow-cut gap in series-parallel graphs is 5. We also give an explicit class of routing instances that shows via elementary calculations that the flow-cut gap in series-parallel graphs is at least 2; this is motivated by and simplifies the proof by Lee and Raghavendra. * The integer flow-cut gap in k-Outerplanar graphs is c^{O(k)} for some fixed constant c. * A very simple proof that the flow-cut gap is O(\log k^*) where k^* is the size of a vertex cover in H; this was previously shown by Günlük via a more intricate proof. =========================================================================== Testing monotone high-dimensional distributions --------------------------------------------------------------------------- Authors: Michal Adamaszek (University of Warwick) Artur Czumaj (University of Warwick) Christian Sohler (TU Dortmund) Topics: Property Testing --------------------------------------------------------------------------- We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution D with infinite or uncountable support. Our goal is to test whether D has a given distribution or it is \epsilon-far from it (in the statistical distance, with the L_1-distance measure). It is not difficult to see that for many natural distributions on infinite or uncountable domains, no testing algorithm can exist and the central objective of our study is to understand if there are any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no testing algorithm that tests if a given probability distribution on [0,1] is uniform. We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions on Boolean n-dimensional cubes by Rubinfeld and Servedio (STOC’2005) to the case of continuous [0,1]^n cubes. We show that if a distribution D on [0,1]^n is monotone, then one can test if D is uniform with the sample complexity O(n/\epsilon^2). This result is optimal up to a polylogarithmic factor. =========================================================================== The rank of diluted random graphs --------------------------------------------------------------------------- Authors: bordenave (CNRS - Univ. Toulouse) lelarge (INRIA - ENS) Topics: Graph Algorithms, Probability, Random Graphs, Random Structures --------------------------------------------------------------------------- We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs converging locally to a tree, we give new formulas for the asymptotic of the multiplicity of the eigenvalue $0$. In particular, the result depends only on the limiting tree structure, showing that the normalized rank is 'continuous at infinity'. Our work also gives a new formula for the mass at zero of the spectral measure of a Galton-Watson tree. Our techniques of proofs borrow ideas from analysis of algorithms, random matrix theory, statistical physics and analysis of Schr\"odinger operators on trees. =========================================================================== Utilitarian Mechanism Design for Multi-Objective Optimization --------------------------------------------------------------------------- Authors: Fabrizio Grandoni (Universita di Roma Tor Vergata) Piotr Krysta (University of Liverpool) Stefano Leonardi (Sapienza Universita di Roma) Carmine Ventre (University of Liverpool) Topics: Approximation Algorithms, Economics, Game Theory, Internet and Network Algorithms, Mechanism Design, Optimization --------------------------------------------------------------------------- In a classic optimization problem the complete input data is assumed to be known to the algorithm. This assumption may not be true anymore in optimization problems motivated by the Internet where part of the input data is private knowledge of independent selfish agents. The goal of algorithmic mechanism design is to provide (in polynomial time) a solution to the optimization problem and a set of incentives for the agents such that disclosing the input data is a dominant strategy for the agents. In case of NP-hard problems, the solution computed should also be a good approximation of the optimum. In this paper we focus on mechanism design for multi-objective optimization problems. In this setting we are given a main objective function, and a set of secondary objectives which are modeled via budget constraints. Multi-objective optimization is a natural setting for mechanism design as many economical choices ask for a compromise between different, partially conflicting, goals. The main contribution of this paper is showing that two of the main tools for the design of approximation algorithms for multiobjective optimization problems, namely approximate Pareto curves and Lagrangian relaxation, can lead to truthful approximation schemes. By exploiting the method of approximate Pareto curves, we devise truthful FPTASs for multiobjective optimization problems whose exact version admits a pseudo-polynomial-time algorithm, as for instance the multi-budgeted versions of minimum spanning tree, shortest path, maximum (perfect) matching, and matroid intersection. Our construction also applies to multi-dimensional knapsack and multi-unit combinatorial auctions. Our FPTASs compute a (1 + epsilon)-approximate solution violating each budget constraint by a factor (1 + epsilon). For the case of (non-perfect) matchings we also present a PTAS (not violating any constraint), which combines the approach above with a novel monotone way to guess the heaviest edges in the optimum solution. Finally, we present a universally truthful Las Vegas PTAS for minimum spanning tree with a single budget constraint. This result is based on the Lagrangian relaxation method, in combination with our monotone guessing step and with a random perturbation step (ensuring low expected running time in a way similar to the smoothed analysis of algorithms). All the mentioned results match the best known approximation ratios, which are however obtained by non-truthful algorithms. =========================================================================== Property Testing and Parameter Testing for Permutations --------------------------------------------------------------------------- Authors: Carlos Hoppen (IME, USP, São Paulo, Brazil) Yoshiharu Kohayakawa (IME, USP, São Paulo, Brazil) Carlos G. T. de A. Moreira (IMPA, Rio de Janeiro, Brazil) Rudini M. Sampaio (DC, UFC, Fortaleza, Brazil) Topics: Combinatorics, Probability, Property Testing, Random Structures, Sublinear Algorithms --------------------------------------------------------------------------- There has been great interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size. These problems are called property testing and parameter testing, where a property or parameter is said to be testable if it can be estimated accurately in this way. The algorithmic appeal is evident, as this leads to reliable constant-time randomized estimators. Our paper addresses property testing and parameter testing for permutations. We give a permutation counterpart of a famous result by Alon and Shapira stating that every monotone graph property is testable. Moreover, we develop a theory of convergence of permutation sequences, which is used to characterize testable permutation parameters along the lines of the work of Borgs et al. in the case of graphs. This theory is interesting for its own sake, as it describes the closure of the set of all permutations as a special class of Lebesgue measurable functions in $[0,1]^2$, which in turn may be used to define a new model of random permutations. =========================================================================== Monotonicity in Bargaining Networks --------------------------------------------------------------------------- Authors: Yossi Azar Nikhil Devanur Kamal Jain Yuval Rabani Topics: Algorithm Analysis, Economics, Game Theory --------------------------------------------------------------------------- We study bargaining networks, discussed in a recent paper of Kleinberg and Tardos \cite{KT}, from the perspective of cooperative game theory. In particular we examine two solution concepts, the nucleolus and the core center. Both solution concepts define unique solutions, so they provide testable predictions. In general coalitional games, both solutions are weakly monotone, but they are not strongly monotone. We define a new monotonicity property that is a natural axiom of any bargaining game solution, and we prove that both the nucleolus and the core center satisfy this monotonicity property. Our proofs are based on a primal-dual argument (for the nucleolus) and on the FKG inequality (for the core center). We further observe some qualitative differences between the two solution concepts. In particular, there are cases where a strict version of our monotonicity property is a natural axiom, but only the core center satisfies it. On the other hand, the nucleolus is easy to compute, whereas computing the core center is \#P-hard (yet it can be approximated in polynomial time). =========================================================================== A Lower Bound for Succinct Rank Queries --------------------------------------------------------------------------- Authors: Mihai Patrascu (AT&T Labs) Topics: Complexity, Compression, Data Structures, Information Theory --------------------------------------------------------------------------- The rank problem in succinct data structures is to preprocess an array A[1..n] of bits into a data structure using as close to n bits as possible, and answer queries of the form rank(k) = Sum_{i=1..k} A[i]. The problem has been intensely studied, and features as a subroutine in a majority of succinct data structures. We show that in the cell probe model with w-bit cells, if rank takes t time, the space of the data structure must be at least n + n/w^O(t) bits. This redundancy/query trade-off is essentially optimal, matching our upper bound from [FOCS'08]. =========================================================================== Amplified Hardness of Approximation for VCG-Based Mechanisms --------------------------------------------------------------------------- Authors: Shaddin Dughmi (Stanford University) Hu Fu (Cornell University) Robert Kleinberg (Cornell University) Topics: Approximation Algorithms, Complexity, Economics, Game Theory, Mechanism Design --------------------------------------------------------------------------- If a two-player social welfare maximization problem does not admit a PTAS, we prove that any maximal-in-range truthful mechanism that runs in polynomial time cannot achieve an approximation factor better than 1/2. Moreover, for the k-player version of the same problem, the hardness of approximation improves to 1/k under the same two-player hardness assumption. (We note that 1/k is achievable by a trivial deterministic maximal-in-range mechanism.) This hardness result encompasses not only deterministic maximal-in-range mechanisms, but also all universally-truthful randomized maximal in range algorithms, as well as a class of strictly more powerful truthful-in-expectation randomized mechanisms recently introduced by Dobzinski and Dughmi. Our result applies to any class of valuation functions that satisfies some minimal closure properties. These properties are satisfied by the valuation functions in all well-studied APX-hard social welfare maximization problems, such as coverage, submodular, and subadditive valuations. We also prove a stronger result for universally-truthful maximal-in-range mechanisms. Namely, even for the class of budgeted additive valuations, which admits an FPTAS, no such mechanism can achieve an approximation factor better than 1/k in polynomial time. =========================================================================== On the possibility of faster SAT algorithms --------------------------------------------------------------------------- Authors: Mihai Patrascu (IBM Almaden) Ryan Williams (Institute for Advanced Study) Topics: Complexity, Geometry, Graph Algorithms --------------------------------------------------------------------------- We investigate the prospects for an algorithm for Boolean CNF satisfiability (CNF-SAT) that runs in $O^*(2^{\delta n})$ time for some $\delta < d =" \Omega(\log"> \log n$. In particular, since the hypercube has strong local expansion properties, (ii) and (iii) imply that RW-MARK and RW-R-RANK mark whp all nodes of an n-node hypercube in $O(n)$ steps. More generally, our results imply that on many important graph classes, random walks which are allowed to mark (cover) neighbors, have the same cover time as the corresponding centralized coupon collecting process. =========================================================================== A Model of Computation for MapReduce --------------------------------------------------------------------------- Authors: Howard Karloff (AT&T Labs) Siddharth Suri (Yahoo! Research) Sergei Vassilvitskii (Yahoo! Research) Topics: Distributed and Parallel Computing, Internet and Network Algorithms --------------------------------------------------------------------------- In recent years the MapReduce framework has emerged as one of the most widely used parallel computing platforms for processing data on the terabyte and petabyte scales. Used daily at companies such Yahoo!, Google, Amazon, and Facebook and adopted more recently by several universities, it allows for easy parallelization of data intensive computations over many machines. One key feature of MapReduce that differentiates it from previous models of parallel computation is that it interleaves sequential and parallel computation. We propose a model of efficient computation using the MapReduce paradigm. Our model allows each machine to perform sequential computations in time polynomial in the size of the input that machine receives. Moreover, since MapReduce is designed for computations over massive data sets, our model limits the number of machines and the memory per machine to be (substantially) sublinear in the size of the input. We compare MapReduce to the PRAM model of computation. We prove a simulation lemma showing that a large class of PRAM algorithms can be efficiently simulated via MapReduce. The strength of MapReduce, however, lies in the fact that it uses both sequential and parallel computation. We show how algorithms can take advantage of this fact to compute an MST of a dense graph in only two rounds, as opposed to O(log(n)) rounds needed by a standard PRAM. We also show to evaluate a wide class of functions using the MapReduce framework. We conclude by applying this result to show how to compute many basic algorithmic problems such as undirected connectivity in the MapReduce framework. =========================================================================== Fast SDP Algorithms for Constraint Satisfaction Problems --------------------------------------------------------------------------- Authors: David Steurer (Princeton University) Topics: Algorithm Analysis, Approximation Algorithms, Mathematical Programming, Optimization, Probability --------------------------------------------------------------------------- The class of constraint satisfactions problems (CSPs) contains many fundamental combinatorial optimization problems such as MaxCut and Max3SAT. Recently, Raghavendra (STOC`08) showed that a certain semidefinite programming relaxation gives the best possible approximation for any CSP, assuming Khot's Unique Games Conjecture. Raghavendra and Steurer (FOCS`09) show that independent of the truth of the Unique Games Conjecture the integrality gap of this relaxation cannot be improved even by adding a large class of valid inequalities. We present an algorithm that finds an approximate solution to this relaxation in near-linear time. Combining this algorithm with a rounding scheme of Raghavendra and Steurer (FOCS`09) yields an approximation algorithm for any CSP that runs in near-linear time and has an approximation guarantee that matches the integrality gap, which is optimal assuming the Unique Games Conjecture Our algorithm employs a framework of Arora and Kale (STOC`07) for solving semidefinite programs. In this framework, the crucial step is to design an efficient width-bounded separation oracle. We show how to implement this oracle by solving a sequence of local linear programs. We also generalize the framework of Arora and Kale in order to deal with irregular instances more efficiently. =========================================================================== Lower bounds for Edit Distance and Product Metrics via Poincare-Type Inequalities --------------------------------------------------------------------------- Authors: Alexandr Andoni (MIT) T.S. Jayram (IBM Almaden) Mihai Patrascu (IBM Almaden) Topics: Complexity, Geometry, Metric Embeddings --------------------------------------------------------------------------- We prove that any sketching protocol for edit distance achieving a constant approximation requires nearly logarithmic (in the strings' length) communication complexity. This is an exponential improvement over the previous, doubly-logarithmic, lower bound of [Andoni-Krauthgamer, FOCS'07]. Our lower bound also applies to the Ulam distance (edit distance over non-repetitive strings). In this special case, it is polynomially related to the recent upper bound of [Andoni-Indyk-Krauthgamer, SODA'09]. From a technical perspective, we prove a direct-sum theorem for sketching product metrics that is of independent interest. We show that, for any metric X that requires sketch size which is a sufficiently large constant, sketching the max-product metric \ell_\infty^d(X) requires \Omega(d) bits. The conclusion, in fact, also holds for arbitrary two-way communication. The proof uses a novel technique for information complexity based on Poincar\'e inequalities and suggests an intimate connection between non-embeddability, sketching and communication complexity. =========================================================================== Shape Replication Through Self-Assembly and RNase Enzymes --------------------------------------------------------------------------- Authors: Zachary Abel (Harvard University) Nadia Benbernou (Massachusetts Institute of Technology) Mirela Damian (Villanova University) Erik Demaine (Massachusetts Institute of Technology) Robin Flatland (Siena College) Skott Kominers (Harvard University) Robert Schweller (University of Texas Pan American) Martin Demaine (Massachusetts Institute of Technology) Topics: Bioinformatics, Geometry --------------------------------------------------------------------------- We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus 0 shapes can be replicated infinitely many times with O(1) distinct tile types and O(1) stages. Further, we show how to replicate precisely n copies of a shape using either O(log n) stages or O(log n) tile types. =========================================================================== Universal $\epsilon$-approximators for integrals --------------------------------------------------------------------------- Authors: Michael Langberg (The Open University of Israel) Leonard J. Schulman (Caltech) Topics: Geometry, Learning --------------------------------------------------------------------------- Let $X$ be a space and $F$ a family of ${0,1}$-valued functions on $X$. Vapnik and Chervonenkis showed that if $F$ is "simple" (finite VC dimension), then for every probability measure $\mu$ on $X$ and $\e>0$ there is a finite set $S$ such that for all $f \in F$, $\sum_{x \in S} f(x)/|S| = [\int f(x) d\mu(x)] \pm \e$. Think of $S$ as a "universal $\epsilon$-approximator" for integration in $F$. $S$ can actually be obtained w.h.p. just by sampling a few points from $\mu$. This is a mainstay of computational learning theory. It was later extended by other authors to families of bounded (e.g., $[0,1]$-valued) real functions. In this work we establish similar "universal $\epsilon$-approximators" for families of unbounded nonnegative real functions --- in particular, for the families over which one optimizes when performing data classification. In this case the $\epsilon$-approximation is multiplicative. =========================================================================== A 1.4-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model --------------------------------------------------------------------------- Authors: Bahman Bahmani (Stanford University) Aranyak Mehta (Google, Inc.) Rajeev Motwani (Stanford University) Topics: Algorithm Analysis, Graph Algorithms, Online problems --------------------------------------------------------------------------- A classic theorem by Vizing proves that if the maximum degree of a graph is $\Delta$, then it is possible to color its edges, in polynomial time, using at most $\Delta+1$ colors. However, this algorithm is offline, i.e., it assumes the whole graph is known in advance. A natural question then is how well we can do in the online setting, where the edges of the graph are revealed one by one, and we need to color each edge as soon as it is added to the graph. Online edge coloring has an important application in fast switch scheduling. Here, a natural model is that edges arrive online, but in a random permutation. Even in the random permutations model, the best known analysis for any algorithm is factor 2, which comes from the simple greedy algorithm (which is factor 2 even in the worst case online model). The algorithm of Aggarwal et al. (FOCS 03) provides a 1+o(1) factor algorithm, but for the case of multigraphs, when $\Delta = \Omega(n^2)$, where $n$ is the number of vertices. In this paper, we show that for graphs with $\Delta = \Omega(polylog(n))$, it is possible to color the graph with $1.4\Delta+o(\Delta)$ colors in the online random order model. Our algorithm is inspired by a 1.6 factor distributed offline algorithm of Panconesi and Srinivasan (SICOMP'97), which we extend by reusing colors online in multiple rounds. =========================================================================== Orthogonal Ham-Sandwich Theorem in R3 --------------------------------------------------------------------------- Authors: Sergey Bereg (University of Texas at Dallas) Topics: Geometry, Topological Problems --------------------------------------------------------------------------- The ham-sandwich theorem states that, given $d\ge 2$ measures in $\R^d$, it is possible to divide all of them in half with a single $(d-1)$-dimensional hyperplane. We study an orthogonal version of the ham-sandwich theorem and define an orthogonal cut using at most $d$ hyperplanes orthogonal to coordinate axes. For example, a hyperplane orthogonal to a coordinate axis is an orthogonal cut. We prove that any three measures in $\R^3$ can be divided in half each with a single orthogonal cut. Applied to point measures, it implies that any three finite sets of points in $\R^3$ can be simultaneously bisected by an orthogonal cut. We present an algorithm for computing an orthogonal ham-sandwich cut in $O(n\log n)$ time. =========================================================================== Bounding Variance and Expectation of Longest Path Length in DAGs from Variance and Expectation of Edge Lengths --------------------------------------------------------------------------- Authors: Jeff Edmonds (York University) Supratik Chakraborty (Indian Institute of Technology Bombay) Topics: Graph Algorithms, Probability --------------------------------------------------------------------------- We consider the problem of computing bounds on the variance and expectation of the longest path length in a DAG from knowledge of variance and expectation of edge lengths. We focus primarily on the case where all edge lengths are non-negative and the DAG has a single source and sink node. We present analytic bounds for various simple DAG structures, and present a new algorithm to compute bounds for more general DAG structures. Our algorithm is motivated by an analogy with balance of forces in a network of "strange" springs. We present some experimental results showing the effectiveness of this algorithm for computing bounds in variance and expectation of circuit delays from variance and expectation of gate delays

اٍے حسن حقیقی نُور اذل

اٍے حسن حقیقی نُور اذل۔۔۔۔
تینوں واجب تے امکان کہوں

تینوں خالق ذات قدیم کہوں
تینوں حادث خلق جہان کہوں

تینوں مطلق محض وجود کہوں
تینوں علمیہ اعیان کہوں۔۔۔۔

ارواح نفوس عقول مثال
اشباح عیان نہان کہوں

تینوں عین حقیقت ماہیت
تینوں عرض صفت تے شان کہوں

انواع کہوں اوضاع کہوں
اطوار کہوں اوذان کہوں۔۔

تینوں عرش کہوں افلاک کہوں
تینوں ناذ نعیم جنان کہوں۔۔۔۔

تینوں تَت جماد نبات کہوں
حیوان کہوں انسان کہوں

تینوں مسجد مندر دیر کہوں
تینوں پوتھی تے قرآن کہوں

تسبیح کہوں زنار کہوں
تینوں کفر کہوں ایمان کہوں

تینوں بادل برکھا گاج کہوں
تینوں بجلی تے باران کہوں

تینوں آب کہوں تے خاک کہوں
تینوں باد کہوں نیران کہوں

تینوں دسرت لچھمن رام کہوں
تینوں سیتا جی جانان کہوں

بلدیو جسودا نند کہوں
تینوں کشن کنیھا کان کہوں

تینوں برما بشن گنیش کہوں
مہادیو کہوں بھگوان کہوں

تینوں گیت گرنتھ تے بید کہوں
تینوں گیاں کہوں اگیاں کہوں

تینوں آدم حوا شیت کہوں
تینوں نوح کہوں طوفان کہوں

تینوں ابراہیم خلیل کہوں
تینوں موسیَ بن عمران کہوں

تینوں ہر دل دا دلدار کہوں
تینوں احمد عالی شان کہوں

تینوں شاہد ملک حجاز کہوں
تینوں باعث کون مکان کہوں

تینوں ناز کہوں انداز کہوں
تینوں حور پری غلمان کہوں

تینوں نوک کہوں تینوں ٹوک کہوں
تینوں سرخی بیڑا پان کہوں۔۔۔۔۔۔

تینوں طبلہ تے طنبور کہوں۔۔
تینوں ڈھولک تے سر بان کہوں

تینوں حسن تے ہار سنگھار کہوں
تینوں عشوہ غمزہ آن کہوں۔۔۔۔

تینوں عشق کہوں تینوں علم کہوں
تینوں وہم یقین گمان کہوں۔۔۔۔۔۔۔

تینوں حسن قوی ادراک کہوں
تینوں ذوق کہوں وجدان کہوں

تینوں سکر کہوں سکران کہوں
تینوں حیرت تے حیران کہوں

تسلیم کہوں تلوین کہوں
تمکین کہوں عرفان کہوں

تینوں سنبل سوسن سرو کہوں
تینوں نرگس نافرمان کہوں

تینوں لالہ داغ تے باغ کہوں
گلزار کہوں بستان کہوں

تینوں خنجر تیر تفنگ کہوں
تینوں برچھا بانک سنان کہوں

تینوں تیر خدنگ کمان کہوں
سوفار کہوں پیکان کہوں

بے رنگ کہوں بے مثل کہوں
بے صورت ہر ہر آن کہوں

سبوح کہوں قدوس کہوں
رحمان کہوں سبحان کہوں

کر توبہ ترت فرید سدا
ہر شے نوں پر نقصان کہوں

اسے پاک الکھ بے عیب کہوں
اسے حق بے نام نشان کہوں

خواجہ غلام فرید۔۔

Nami danam keh aakhir choon dam-e-deedar mi raqsam

نمی دانم کہ آخر چوں دم دیدار می رقصم مگر نازم یہ آں ذوق کہ پیش یار می رقصم

Nami danam keh aakhir choon dam-e-deedar mi raqsam

magar nazm ba aan zouq keh pesh-e-yaar mi raqsam

کہ عشق دوست ہر ساعت دوروں نار می رقصم

گاہےبر خاک می غلتم , گاہے بر خار می رقصم

keh ishq-e-doost her sa’at duroon-e-naar mi raqsam

gahey ber khaak mi ghaltam, gahey ber khaar mi raqsam

بیا جاناں تماشا کن کہ درانبوہ جانبازاں

بصد سامان رسوائی سر بازار می رقصم

beya jana tamasha kun keh der amboh-e-jaan bazaan

basad saman-e-ruswai sar-e-bazaar mi raqsam

خوش آ رندی کہ پامالش کنم صد پارسائی را

زہے تقویٰ کہ من با جبّہ و دستار می رقصم

khusha rindi keh pamalash kunam sad parsai ra

zahey taqwa keh mun ba jubba o dastar mi raqsam

تاوان قاتل کہ از بحر تماشے خون -من ریزی

منم بسمل کہ زیر خنجر خونخوار می رقصم

tawan qatil keh az bahr-e-tamasha khoon-e-man rezi

manam bismil keh zer-e-khanjar-e-khoon-khwar mi raqsam

منم عثمان مروندی اویار شیخ منصورم

ملامت می کند خلقے او من بردار می رقصم

manam Usman-e-Marwandi o yaar-e-Sheikh-e-Mansoor-am

malamat mi kunad khalqey o man bar daar mi raqsam

- Sheikh Usman Marwandi (Lal Shahbaz Qalandar)

How is it that at mere sight I am enraptured?

But it is only proper; it is for love I dance

And it is love that in eternal hellfire I am ecstatic

In dust I bathe, on thorns I dance

O life, see me amidst hordes of your fearless lovers

Shouldering my shame before their eyes, I dance

Blessed insolence that I grind to dust a hundred virtues

For piety is when in clerical robes, I dance

Such display may cause my killer to lust for my blood

And meek under the thirsty blade, I dance

For I am Usman of Marwand, apostle of Mansoor the Wise

Creation chides and condemns, and on the gallows, I dance.

Thanks to Google India team for Indic Transliteration (Urdu)!

Square root of three

A cool poem by David Feinberg from movie “Harold and Kumar: Escape from Guantanamo Bay”

I fear that I will always be
A lonely number like root three

The three is all that’s good and right,
Why must my three keep out of sight
Beneath the vicious square root sign,
I wish instead I were a nine

For nine could thwart this evil trick,
with just some quick arithmetic

I know I’ll never see the sun, as 1.7321
Such is my reality, a sad irrationality

When hark! What is this I see,
Another square root of a three

As quietly co-waltzing by,
Together now we multiply
To form a number we prefer,
Rejoicing as an integer

We break free from our mortal bonds
With the wave of magic wands

Our square root signs become unglued
Your love for me has been renewed!

Teray Bandiyan di Bandary aan!

Poetry is from Khawaja Fareed. The First line was originally written as :

Mein Muthri Nit Jaan Balab.,,. Oo taan khush wasda wich mulk arab

Nusrat Fateh Ali Khan used to recite it on annual celebrations of Khawaja Suleman in Tounsa Shareef. Khawajja Moeen once heard those words, stopped the reciter and asked to change the verse to:

Mein Muthri Nit Jaan Balab.,,. Soohnra khush wasda wich mulk arab

Since then it has been changed in almost all literature forms to the newer version; following is not my the most favorite recitation but I could not find any other on internet; enjoy the love pouring out of each phoneme recited byMuhammad Afzal Tahir Golaravi!

Muthu awarded Excellence in Graduate Teaching for 2009

Professor Muthu Muthukrishnan has been awarded Award for Excellence in Graduate Teaching for 2009. I was very lucky to attend both of the courses that he offered during academic year 2008-2009.

http://www.cs.rutgers.edu/common/apps/webarch/data/yKmgMPLqzFEfXMsCPvLf/intro.whtml

Before meeting Muthu, I used to believe that problems are divided into two disjoint subsets: the interesting problems and the (asymptotically life-sized) boring ones. Thanks to Muthu I now know that there is always something very interesting in the most boring looking topic, you just need to view it from Muthu's angle. To have an eye for interesting parts in not-so-interesting sounding problems, is one the most basic requirement of (modern) problem solving. If I have any such thing, its because of Muthu.

Warm Congratulations to Muthu!

Poetry by Erdos

Joel Spencer was here at DIMACS the other day for Ramsey Theory workshop. He shared with us following lines by Erdos

It is six in the morning.
The house is asleep.
Nice music is playing.
I prove and conjecture.

Erdos wrote these lines in a letter to Vera Sos. For most people it might nothing more than a unconvincing chatter and yet for some it is a master piece of poetry!

mudassir, rutgers

Friends

Few days back in a mail to a friend I wrote:

----
sorry to bother but it arbitrarily came to my mind, thought should share with you.,i hope you remember once you asked who do I consider a real friend, and I could not really answer it. I think I have the answer now.

Imagine yourself in a court being charged for some big crime say robbery or murder, there is all the evidences, and witnesses and everything,.and the whole world believes you are guilty,.you go to your friend and tell him that you have not committed the thing, and he believes you straight away...

i believe he is a real friend,.i don't have more than 3 of the kind, but i think it is enough to have even one... :)
------

Save your breath, I have already been told that it is lousy but I still appreciate the value of trust. But today my trust was so very tested.
In reply to some stupid comment by a guy, I called this guy "a ***k sucking mother f**king son of a b***h..."on a public mailing list.
Everyone was quite angry at my note, and I was told to "refrain from spreading such abuse around and grow up".

I ran back to my the best friend and here is his response
"
u did it Perfectly alrite

STAMPED

infact very gud

"
While his stamp is good enough for me to believe that I am innocent, lets assume that it is not so, and that I really did something wrong, and that all the people are in right to call me the bad guy; isn't it good to have at least one person who is on your side even if you are wrong? no?

Oh please...

The 2009 RUSENIX Security Symposium

Yesterday, we had this small software security conference here at rutgers. Abstracts of the papers presented are available here.

Overall, it was very nice experience, within very small amount of time, and with very little exposure to existing security literature, works presented were quite impressive, and above all people managed to summarize all their work within 15mins time alloted to each time. While everyone deserves to be patted on the back for hardwork they put (honestly it was amazing), but I believed Huijun Xiong and Qiang Ma work on Social Anti-Spam was perhaps voted best most probably because it was in true spirit of research, and very well presented.

Text of the Nizam-e-Adl Regulation 2009

Text of the Nizam-e-Adl Regulation 2009

To provide for Nifaz-e-Nizam-e-Sharia’h through Courts in the provincially Administered Tribal Areas for the North-West Frontier Province, except the Tribal Areas adjoining Mansehra district and the former State of Amb in the Hazara division.

It is expedient to provide for Nifaz-e-Nizam-e-Sharia’h through courts in the Provincial Administered Tribal Areas of the North-West Frontier Province except the Tribal areas adjoining Mansehra district and the former State of Amb; 

Clause (3) of Article 247 of the Constitution of the Islamic Republic of Pakistan provides that no Act of Majlis-e-Shoora (parliament) or a Provincial Assembly Shall apply to a provincially Administered Tirbal Areas, or any part thereof, unless the governor of the province in which the Tribal Areas is situated, with the approval of the President, so directs, and in giving such direction with respect to any law, the Governor may direct that the law shall, in its application to a Tribal Area, or to a specified part thereof, have effect subject to such exceptions and modifications as may be specified in the direction;

Clause (4) of Article 247 of the Constitution of the Islamic Republic of Pakistan provides that the governor of a province, with the prior approval of the President may, with respect to any matter within the legislative competence of the Provincial Assembly, make regulations for the peace and good governance of Provincially Administered Tribal Areas or any part thereof;

In exercise of the powers aforesaid, the North-West Frontier Province governor, with the approval of the president, is pleased to make the following Regulation:

1: Short title, extent and commencement: 

(1) This Regulation may be called the Sharia Nizam-e-Adl Regulation, 2009.

(2) It shall extend to the provincially Administered Tribal Areas of the North-West Frontier Province, except the Tribal Areas adjoining Mansehra district and the former State of Amb, hereinafter referred to as the said area.

(3) It shall come into force at once.

Definitions: 

(4) In this Regulation, unless there is anything repugnant in the subject or context,

(a) “Court” means the court of competent jurisdiction established and designated as such under this Regulation, and includes a court of appeal or, as the case may be, a court of revision;

(b) “Dar-ul-Dar-ul-Qaza” means the final appellate or revisional court, in the said area, designated as such, under this Regulation in pursuance of clause (2) of Article 183 of the Constitution of the Islamic republic of Pakistan;

(c) “Dar-ul-Qaza” means appellate or revisional Court constituted by Governor of North West Frontier Province in the said area, under clause (4) of the Article 198 of the Constitution of the Islamic Republic of Pakistan;

(d) “Government” means the Government of the NWFP;

(e) “Paragraph” means a paragraph of this regulation; “recognised institution” means the Shariah Academy established under International Islamic University Ordinance, 1985 (XXX of 1985) or any institution imparting training in Uloom-e-Shariah and recognised as such by government; 

(f) “Prescribed’ means prescribed by rules made under this Regulation;

(g) “Qazi” means a duly appointed judicial officer as specified and designated in column (3) of Schedule II;

(h) “Recognised institution” means the Shariah Academy established under International Islamic University Ordinance, 1985 (XXX of 1985) or any institution imparting training in Uloom-e-Shariah and recognised as such by government;

(i) “Schedule” means a Schedule to this Regulation;

(j) “Sharia’h” means the injunctions of Islam as laid down in the holy Quran and Sunnah, Ijma and Qias.

Explanation: 

In the application to the personal law of any Muslim sect, the expression “the holy Quran and Sunnah” shall mean the Quran and Sunnah-e-Nabvi (PBUH) as interpreted by that sect.

(1) All other expressions, not expressly defined in this Regulations, shall have the same meanings as assinged to them in any other law for the time being in force in the said area.

(2) All other expressions, not expressly defined in this Regulation, shall have the same meanings as assigned to them in any other law for the time being in force in the said area.

(3) Application of certain laws. (1) The laws specified in column (2) of Schedule-I, as in force in the NWFP immediately before the commencement of this Regulation, and so far as may be, all rules, notifications and orders made or issued there under, shall apply to the said area.

(4) All the laws applicable to the said area, including the laws mentioned in sub-paragraph (1) shall so apply subject to such exceptions and modifications as specified in this Regulation.

4: Certain laws to cease to operate:

If, immediately before the commencement of this Regulation, there was in force in the said area any law, instrument, custom or usage having the force of law not corresponding to the Injunctions of Quran Majeed and Sunnah or provisions of any of the laws applied to the said area by this Regulation, such law, instruments, custom or usage, as the case may be, shall upon such commencement, cease to have effect in the said area.

5: Courts: 

Besides, Dar-ul-Dar-ul-Qaza and Dar-ul- Qaza, there shall be following courts of competent jurisdiction, in the said area:

(a) Court of Zilla Qazi;

(b) Court of Izafi Zilla Qazi;

(c) Court of Aa’la Illaqa Qazi;

(d) Court of Illaqa Qazi; and

(e) Court of Executive Magistrate.

6: Qazis and their powers and functions: 

(1) Any person to be appointed as Illaqa Qazi in the said area shall be a person who is a duly appointed judicial officer in the North-west Frontier Province and preference shall be given to those judicial officers who have completed Shariah course from a recognised institution.

(2) In relation to proceedings and conducting the criminal or cases, all powers, functions and duties conferred, assigned or imposed on Judicial officers in the North-West Frontier Province under any law for the time being in force shall, subject to application of such law in the said area and established principles of Sharia’h, be exercised, performed or discharged by them as designated in column of Schedule-II.

(3) Subject to the general supervision of the principal seat of Dar-ul-Qaza, a Zilla qazi shall supervise the work of subordinate courts and, through the District Police Officer concerned, the process serving staff, with in the local limits of his jurisdiction.

7: Executive Magistrate: 

(1) In each district or protected area, there shall be a District. Magistrate, Additional District Magistrates, Sub Divisional Magistrates and other Executive Magistrates as the Government may deem necessary to appoint.

(2) The District Magistrate and all other Executive Magistrates shall discharge their functions, responsibilities and exercise their powers according to the established principles of Shariah and other laws for the time being in force in the said area.

(3) Keeping peace, maintaining order, enforcing the executive authority of the Government and “Sadd-e-Zara-e-Jinayat” shall be the duty, responsibility and power of the District Magistrate. For this purpose he may take action against an individual under the established principles of Shariah.

(4) The cases included in Schedule III to this Regulation shall be exclusively triable by Executive Magistrates.

EXPLANATION: The expression “Sadd-e-Zara-e-Jinayat” means and includes all actions and steps taken under the Shariah laws and any other law in force for the time being for the control of crimes.

8: Submission of Challan to Qazi or Executive Magistrate: 

It shall be the duty of every officer-in-charge of a police station to ensure that complete challan in each criminal case is submitted to the concerned Court with in fourteen days from the date of lodging the first information report, except in a case in which the concerned Qazi or Executive Magistrate has granted special extension of time for a specified period for reasons to be recorded:

Provided that if any officer-in- charge of police station or investigation officer fails to submit complete challan within specified period, the Qazi or Executive Magistrate concerned shall refer the matter to competent authority for disciplinary action against the police officer responsible for such delay and necessary disciplinary action shall be taken against him forthwith and shall be duly communicated to the referring Qazi or Executive Magistrate.

(2) The officer-in-charge of a police station shall submit a copy of the first information report to concerned Qazi or Executive Magistrate within twenty four hours of its lodging, and inform the concerned Qazi and Executive Magistrate, from time to time, about the position and further progress of investigation of the case.

9: Proceedings to be in accordance with Shariah: 

(1) A Qazi or Executive Magistrate shall seek guidance from Quran Majeed, Sunna-e-Nabvi (PBUH), Ijma and Qiyas for the purposes of procedure and proceedings for conduct and resolution of cases and shall decide the same in accordance with Shariah. While expounding and interpreting the Quran Majeed and Sunna-e-Nabvi (PBUH) the Qazi and Executive Magistrate shall follow the established principles of exposition and interpretation of Quran Majeed and Sunna-e-Nabvi (PBUH) and, for this purpose, shall also consider the expositions and opinions of recognised Fuqaha of Islam.

(2) No court shall entertain a suit unless the plaintiff or, as the case may be, the complainant verifies that copies of the plaint along with supporting documents have been sent, through registered post with acknowledge due to all defendants, except in case of a suit for perpetual injunction accompanied by an application for temporary injunction.

(3) The pleadings shall be accompanied by copies of all relevant documents and affidavits of all the unofficial witnesses duly attested by an oath commissioner. The affidavits so submitted shall be treated as examination-in-chief of such witness:

Provided that if, after submission of pleadings, in the opinion of court, any new issue arises, party to proceedings may be allowed to submit afresh copies of relevant documents and affidavits of unofficial witness attested in the manner aforesaid, for arriving at just conclusion of case.

(4) In all cases of civil nature written statement shall be submitted within seven days and where the defendant fails to do so his defence shall be struck off:

Provided that the court may extend time for filing of written statement in extraordinary circumstances for an additional period of seven days. The time so allowed shall’ not be extended further on any ground whatsoever.

(5) After completion of evidence, the court shall ask the parties to argue, either verbally or in writing, on the adjourned date and, if either of the party fails to do so on the date so, fixed, the court shall pronounce judgment on merits without any further adjournment for arguments:

Provided that it shall be the duty of the court to make list of relevant reported judgments, referred to by any party as precedent, which shall form part of judicial record.

(6) No adjournment shall be granted to either party in any civil or criminal proceedings, except where the court is satisfied that adjournment is unavoidable. In such case the requesting party shall deposit the costs in court, which shall not be less than two thousand rupees.

10: Observance of time schedule: 

(1) A period of not more than six months for disposal of a civil case, and a period of not more than four months for disposal of a criminal case, shall be standard time schedule excluding the time spent for proceedings.

(2) A Qazi shall finalize a case within the time schedule prescribed under sub-paragraph (1) and, in case of any delay in disposal of any case beyond such schedule, shall report the cause and reasons of such delay to the Zilla Qazi, or, as the case may be, to the presiding officer of the principal seat of Dar-ul-Qaza, and shall act on the directions issued by such court in this behalf.

(3) An Executive Magistrate shall also finalize a case within the time schedule prescribed under sub-paragraph (1) and, in case of any delay in disposal of any case beyond such schedule, shall report the case and reasons of such delay to the District Magistrate and shall act on the directions issued by him in this behalf.

(4) If the Zilla Qazi or, as the case may be, the presiding officer of the principal seat of Dar-ul-Qaza in relation to proceedings in the court of Qazi, upon examination of causes of delay, is of the opinion that the delay has been’ caused due to the delaying tactics of a party, it shall impose a cost to be recovered from the defaulter party and direct the court concerned to dispose of the case within an extended period of not more than one month.

(5) If the District Magistrate, in relation to proceedings in the court of Executive Magistrate, upon examination of causes of delay, is of the opinion that the delay has been caused due to the delaying tactics of a party, it shall impose*a cost to be recovered from the defaulter party and direct the court concerned to dispose of the case within an extended period of not more than one month.

(6) If in the opinion of Zilla Qazi or, as .the case may be, of the presiding officer of the principal seat of the Dar-ul-Qaza, the Qazi or Executive Magistrate, dealing with the case or proceedings is responsible for delay in its disposal, the Zilla Qazi or, as the case may be, the presiding officer of the principal seat of Dar-ul-Qaza may

(a) in the case of Qazi, deliver upon him a letter of displeasure. If a Qazi is served with three letters of displeasure in a year, then the Zilla Qazi or as the case may be, presiding officer of the principal seat of Dar-ul-Qaza, after providing him an opportunity of being heard, may make an entry in his service record; and

(b) in the case of Executive Magistrate, inform the District Magistrate about such delay and recommend for disciplinary action, provided in clause (a) and the District Magistrate shall act on the recommendations accordingly.

(7) In criminal cases, the Investigating Officer shall prepare copies of the case file in triplicate, in addition to judicial file, so that the trial court may retain the judicial file for regular trial, and the remaining two files, may be sent to the court concerned when requisitioned.

(8) An appeal or revision under this Regulation shall be filed within thirty days from the date of the decision in the respective case, after sending its copies, through registered post with acknowledge due,to the opposite part, and the appellate or revisional court shall decide the same within thirty days, without remanding it on any ground whatsoever:

Provided that such court shall have the power to rectify any illegality or irregularity of omission.

(9) Any decree shall be executed either by the court, which passed it, or by the court it is sent for execution, within two months.

11: Establishment of courts:

(1) As soon as may be after the commencement of this Regulation, Government shall take necessary steps to establish as many courts as may be necessary to ensure expeditious dispensation of justice with in prescribed time schedule.

(2) Where the number of pending case^ at. a time exceeds more than one hundred and fifty in a court of Zilla Qazi, District Magistrate, or, as the case may be , Izafi Zilla Qazi, or exceeds more than two hundred cases in a court of Aa’la Ilaqa Qazi, Executive Magistrate, or, as the case may be, Illaqa Qazi, it shall be necessary for the Government to establish a new court and provide it all related facilities to ensure dispensation of justice within prescribed time schedule.

12: Appeal and revision: 

Subject to the Constitution of the Islamic Republic of Pakistan, appeal or revision against the orders, judgment or decrees of the Dar-ul Qaza shall lie to the Dar-ul-Dar-ul-Qaza established for the purposes of this Regulation.

13: Power to appoint musleh: 

(1) Any civil or criminal case, subject to mutual consent of the parties, may be. referred by a court to Musleh or, as the case may be, musleheen before recording of evidence, either on the agreement of the parties regarding the names of such musleh or musleheen, or in case of their disagreement, to such musleh or musleheen whose names appear on the list maintained by the court for such purpose:

Provided that the cases falling within the purview of Hudood laws and cases by or against the Federal Government or Provincial Government or any statutory body or persons under legal disabilities shall not be referred for sul’h. 

(2) The musleheen shall record their opinion with regard to a dispute referred to them with reasons thereof. 

(3) Where a musleh or, as the case may be, musleheen, to whom a dispute has been referred for resolution, either fail or refuse to resolve it, or the Court is of the opinion that unnecessary delay has been caused, without sufficient reason, in resolving it, the Court, may, on the application of a party or suo ‘moto, for reasons to be recorded, withdraw the order of such reference and, after such withdrawal, it shall resolve the dispute in accordance with Sharia’h as if it were not referred for sul’h:

Provided that, in no circumstances a case shall remain with a musleh or, as the case may be, musleheen for a period of more than ^.fifteen days, but the court may, in extraordinary circumstances, for reasons to be recorded in writing, extend the time for fifteen days and, on the expiry of the aforesaid period, it shall stand withdrawn to the court for further proceedings.

(4) The Musleh or, as the case may be, the musleheen, appointed for such resolution of the dispute, after hearing the parties and their witnesses, if any, perusing the relevant document, if any, and inspecting the spot, if need be, shall form opinion about resolution of the dispute, with reasons therefor, and submit a report of their opinion to the concerned court without delay: 

Provided that in case the opinion is not unanimous, the opinion of the majority members and the opinion of each dissenting member, separately or jointly, with reasons thereof shall be so submitted.

(5) The Court shall, if it is satisfied that the opinion in a case referred to for sul’h under sub-paragraph (1) is in accordance with Sharia’h, make it the rule of the Court, and shall announce it as such, but, if the court comes to the conclusion that the opinion is not in accordance with Sharia’h, it shall declare the opinion, for reasons to be recorded, as null and void and shall start its proceedings for decision of such dispute in accordance with Sharia’h as if it were not referred for sul’h.

(6) The court shall, before proceeding further, provide an opportunity to the parties to submit objections, if any, to such report, and, if any, objections are so made, the court shall, after hearing the parties, decide about the correctness or otherwise of the objections.

(7) The court shall, keeping in view the actual expenses incurred by the musleh or musleheen, on travelling to, and stay at, the place other than the place of his or, as the case may be, their residence, and the time spent, in dealing with the case, in particular circumstances of each case, fix the remuneration of such musleh or musleheen, to be paid by each party in such proportion as may be determined by the court.

14: Conduct of Judicial Officers and Executive Magistrates: 

(1) The conduct and character of each Judicial Officer and Executive Magistrate shall be in accordance with the Islamic principles.

(2) Notwithstanding anything contained in any law for the time being in force/ all cases, suits, inquires, matters and proceedings in courts, pertaining to the said area, shall be decided by the courts concerned in accordance with Sharia’h: Provided that cases of non-Muslims in matters of adoption, divorce, dower, inheritance, marriage, usages and wills shall be conducted and decided in accordance with their respective personal laws. 

(3) Government may, from time to time, take such measures for the purposes of sub-paragraph (1), as it may deem necessary.

15: Aid and assistance to courts:

(1) All executive authorities in the said area, including members of law enforcing agencies and members of other service’s of Pakistan, shall act in aid and assistance of the courts, and shall implement their judicial decisions and orders.

(2) The Government may, where necessary, issue such directions to any law enforcing agency as are necessary in relation to service of court processes on the parties, witnesses or any other person, and, for any general or specific purposes, in order to ensure the conduct of such law enforcing agency in aid and assistance of the courts.

16: Language of the Court and its record: 

All the processes and proceedings of the court, including the pleadings, evidence, arguments, orders and judgments shall be recorded and conducted in Urdu, Pushto or in English and the record of the Court shall also be maintained in the said language.

17: Power to make rules: 

The Government may, by notification in the official Gazette, make rules for carrying out the purposes of this Regulation.

18: Regulation to override other laws: 

The provisions of this Regulation shall have effect notwithstanding anything to the contrary contained in any other law for the time being in force in the said area.

19: Repeal: 

(1) The Provincially Administered Tribal Areas Shari Nizam-e-Adl Regulation, 1999 (NWFP Reg. I of 1999), and rules made there under are hereby repealed.

(2) The Code of Criminal Procedure (Amendment) Ordinance, 2001 (XXXVII of 2001), applied to the said area vide Home and Tribal Affairs Department’s Notification No. 1/93-SOS^I.I (HD)/2001, dated the 27th April 2002, is hereby repealed.

(3) Notwithstanding the repeal of the Regulation under sub-paragraph (1), or cessation of any law, instrument, custom or usage under paragraph 4, the repeal or cessation, as the case may be, shall not

(a) revive anything not in force or existing at the time at which the repeal or cessation takes effect; 

(b) affect the previous operation of the law, instrument, custom or usage or anything duly done or suffered there under;

(c) affect any right, privilege, obligation or liability acquired, accrued or incurred under the law, instrument, custom or usage;

(d) affect any penalty, forfeiture or punishment incurred in respect of any offence committed against the law, instrument, custom or usage; of” 

(e) affect any investigation, legal proceeding or remedy in respect of any such right, privilege, obligation,, liability, penalty, forfeiture or punishment; and any such investigation, legal proceeding or remedy may be instituted, continued or enforced, and any such penalty, forfeiture or punishment may be imposed, as if the law, instrument, custom or usage had not been repealed or ceased to have effect, as the case may be.

(See Paragraph 3 (1)

S.N. Nomenclature of laws (1) (2)

1. The West Pakistan Historical Mosques and Shrines Fund Cess Ordinance, 1960 (W.P.Ord.y of 1960).

2. The Family Courts Act, 1964 (W.P.Act XXXV of 1964).

3. The Pakistan Arms Ordinance,1965 (W.P.Ord.XX of 1965).

4. The Law Reforms Ordinance, 1972 (Ord.XII of 1972).

5. The Code of Civil Procedure (Amendment) Act, 1976, (XV of 1976).

6. The Law Reforms (Amendment) Ordinance, 1976 (Ord. XXI of 1976).

7. The North-West Frontier Province Suppression of Crimes .Ordinance, 1978 (NWFP Ord. Ill of 1978).

8. The North-West Frontier Province Prevention of Gambling Ordinance, 1978 (N.W.F.P. Ord. V of 1978)

9. The Code of Civil Procedure (Amendment) Ordinance, 1980 (Ord. X of 1980).

10. The Offences Against Properties (Enforcement of -Hudood) (Amendment) Ordinance, 1980 (Ord. XIX of 1980).

11. The Offence of Zina (Enforcement of Hudood) (Amendment) Ordinance,.1980 (Ord. XX of 1980).

12. The Offence, of Qazf (Enforcement of Hadd) (Amendment) Ordinance 1980 (XXI of 1980).

13. The Ehtram-e-Ramzan Ordinance, 1981 (Ord. XXIII of 1981).

14. The Offences Against Property (Enforcement of Hudood) (Amendment) Ordinance, 1982 (Ord. II of 1982).

15. The Zakat and Ushr (Amendment) Ordinance, 1983 (Ord.VII of 1983).

16. The Zakat and Ushr (Second Amendment) Ordinance 1983 (Ord. X of 1983).

17. The Zakat and Ushr (Third Amendment) Ordinance, 1983 (Ord. XXVI of 1983).

18. The Anti-Islamic Activities of Qadianis Group, Lahore Group and Ahmadis (Prohibition and Punishment) Ordinance, 1984 (Ord. XX of 1984.

19. The Zakat and Ushr (Amendment) Ordinance, 1984 (Ord. XLVI of 1984).

20. The North-West Frontier Province (Enforcement of Certain Provisions of Laws) Act, 1989 (NWFP Act II of 1980).

21. The Code of Civil Procedure (Amendment) Act, 1989 (IV of 1990).

22. The Zakat and Ushr (Amendment) Act, 19991 (XXIII of 1991).

23. The Enforcement of Sharia’h Act, 1991 (X of 1991).

24. The Pakistan Bait-ul-Mal¦ Act, 1992 (I of 1992).

25. The Code of Civil Procedure (Amendment) Act, 1992 (VI of 1992).

26. The NWFP Shari Act, 2003 (NWFP Act No II of 2003).

27. The NWFP Waqf Ordinance, 1979 (Ord. I of 1979).

28. The NWFP Consumer Protection Act, 1997 (Act VI of 1997).

29. The Pakistan Environmental Protection Act, 1997 (Act XXXIV of 1997).

30. The Civil Law (Reforms) Act, 1994 (Act XIV of 1994).

31. The Fatal Accident Act, 1855 (Act XIII of 1855).

32. The Partition Act, 1893 (Act IV of 1893).

33. The Antiquities Act, 1975 (Act VII of 1976).

34. The Essential Article (Control). Act, 1958).

35. The North-West Frontier Province Orphanages (Supervision and Control) Act, 1976 (Act XIV of 1976).

36. The West Pakistan Suppression of Prostitution Ordinance, 1961 (Ord. II of 1961).

37. The Price Control and Prevention of Profiteering and Hoarding Act, 1977 (XXIX of 1977).

38. The West Pakistan Regulation and Control of Loud Speaker and Sound Amplifiers Ordinance, 1965 (Ord. II of 1965).

39. The Prevention of Gambling Act, 1977 (Act XXVIII of 1977).

40. The Indecent Advertisement Prohibition Act, 1963 (Act XII of 1963).

41. The Travel Agencies Act, 197 6 (Act XXX of 1976).

42. The Employment of Children Act, 1991 (Act V of 1991).

43. The North-West Frontier Province Registration and Functions of Private Educational Institutions (Amendment) Ordinance, 2002 (Ord XLVI of 2002).

44. The NWFP the Punjab Minor Canals (Amendment) Ordinance, 2002 (Ord. LVIII of 2002).

45. The NWFP Local Government (Amendment) Act, 2005 (Act X of 2005).

46. The NWFP Housing Authority Act, 2005 (Act XI of 2005).

47. The NWFP Consumers Protection (Amendment) Act, 2005 (Act II of 2005).

48. The NWFP Local Government (Second Amendment) Act, 2006 (Act II of 2006).

49. The NWFP Societies Registration (Amendment) Act, 2006 (Act III of 2006).

50. The NWFP Prohibition of Kite Flying Activities Act, 2006 (Act IV of 2006).

51. The NWFP Interest of Personal Loans Prevention Act, 2007.

52. The NWFP Agriculture and Livestock Produce Markets Act, 2007.

53. The North-West Frontier Province Forest Ordinance, 2002 (Ord. XIX of 2002).

54. The Anti-Terrorism (Second Amendment) Ordinance, 1999 (Ord. XIII of 1999). 

55. The Anti-Terrorism (Third Amendment) Ordinance, 1999 (Ord. XX of 1999).

56. The Juvenile Justice System Ordinance, 2000 (Ord. XXII of 2000).

57. The Anti-Terrorism (Amendment) Ordinance, 2000 (Ord. XXIX of 2000) .

58. The National Highway Safety Ordinance, 2000 (Ord. XL of 2000).

59. The Zakat and Ushr (Amendment) Ordinance, 2000 (Ord. XXI of 2001).

60. The Patents Ordinance, 2000 (Ord. LXI of 2001).

61. The Control of Narcotic Substances (Amendment) Ordinance, 2000 (Ord. LXVI of 2000).

62. The Zakat and Ushr (Amendment) Ordinance, 2001 (Ord. XXI of 2001).

63. The Arms Laws (Amendment) Ordinance, .2001 (Ord. LXVI of 2001).

64. The Code of Civil Procedure (Amendment) Ordinance, 2002 (Ord. XXXIV of 2002).

65. The General Clauses (Amendment) Ordinance, 2002 (Ord. XXXIII of 2002).

66. The Representation of People (Amendment) Ordinance, 2002 (Ord. XXVIII of 2002).

67. The Representation of People (Amendment)’ Ordinance, 2002 (Ord. XXXVI of 2002).

68. The Representation of People (Third Amendment) Ordinance, 2002 (Ord. XLV of 2002).

69. The Zakat and Ushr (Amendment) Ordinance, 2002 (Ord. XXV of 2002).

70. The Zakat and Ushr (Amendment) Ordinance, 2 002 (Ord. XXXVIII of 2002).

71. The National Commission for Human Development Ordinance, 2002 (Ord. No. XXIX of 2002).

72. The Pakistan. Electronic Media Regulatory Authority Ordinance, 2002 (Ord. No. XIII of 2002).

73. The Prevention and Control of Human Trafficking Ordinance, 2002 (LIX of 2002).

74. The Probation of Offenders*. (Amendment) Ordinance, 2002 (LXVI of 2002).

75. The Prohibition of Smoking and Protection of Non-Smokers Health Ordinance, 2002 (Ord. LXXIV of 2002) .

76. The Freedom of Information Ordinance, 2002 (Ord. XCVI of 2 002).

77. The Press Council of Pakistan Ordinance, 2002 (Ord. XCVII of 2002).

78. The Press, Newspaper, News Agencies and Book Registration Ordinance, 2002 (Ord. XCVIII of 2002).

79. The Monopolies and Restrictive Trade Practices (Control and Prevention) Ordinance, 2002 (Ord. CI of 2002).

80. The Drugs (Amendment) Ordinance, 2002 (Ord. XXVIII of 2002).

81. The Local Government, Election Laws (Amendment) Ordinance, 2002.

82. The Political Parties Order, 2002 (C.E.O. 18 of 2002).

83. The Political Parties (Amendment) Order, 2002 (C.E.O. .20 of 2002).

84. The Police. (Amendment) Order, 2002 (C.E.O. 36 of 2002).

85. The Contempt of Court Ordinance, 2003 (Ord. V of 2003.).

86. The Political Parties (Amendment) Act, 2004 (Act III of 2004).

87. The Code of Civil Procedure (Amendment) Act, 2004 (Act VIII of 2004).

88. The Defamation (Amendment) Act, 2004 (Act IX of 2004).

89. The Anti-terrorism (Amendment) Act, 2004 (Act X of 2004).

90. The Illegal Dispossession Act, 2005 (Act XI of 2005).

91. The Marriage Functions (Prohibition of Ostentatious Displays and Wasteful Expenses) (Amendment) Act, 2006.

92. The Pakistan Electronic Media Regulatory Authority (Amendment) Act, 2007 (II of 2007).

93. The Prevention of Electronic Crimes Ordinance, 2008.

94. The Control of Narcotics Substances Act, 1997 (XXV of 1997) .

SCHEDULE II 

(See paragraphs 2 (1) (g) , 6(2)]

S.NO. Designation of judges and Judicial Officers in the NWFP except PATA

Designation of judges and Judicial Officers in the PATA

1 2 3

1. District and Sessions Judge – Zilla Qazi

2. Additional District and. Sessions Judge – Izafi Zilla Qazi

3. Senior Civil Judge/Judicial – Aa’la Illaqa Qazi 

30 of Criminal Procedure Code,1898 (Act V of 1898) Aa’la Illaqa Qazi

4. Civil Judge/Judicial Magistrate Illaqa Qazi

SCHEDULE III

(See paragraph 7(4)]

S. No. Description of Offences

1. All offences under Pakistan Penal Code punishable with imprisonment up to three years with or without fine.

2. All” offences punishable under Local and Special Laws punishable up to three years with or without fine.

3. Cases for prevention of breach of peace and public nuisances under the Pakistan Penal Code and the Code of Criminal Procedure, 1898.

4. Cases pertaining to deviations of licences and permits under relevant laws applicable to the said area.

(OWAIS AHMED GHANI)

Governor.