Improved analysis of the greedy algorithm for stochastic matching

The stochastic matching problem with applications in online dating and kidney exchange was introduced by Chen et al. (2009) [1] together with a simple greedy strategy. They proved it is a 4-approximation, but conjectured that the greedy algorithm is in fact a 2-approximation. In this paper we confirm this hypothesis.     

A note on compressed sensing and the complexity of matrix multiplication

We consider the conjectured O(N2+?) time complexity of multiplying any two N×N matrices A and B. Our main result is a deterministic Compressed Sensing (CS) algorithm that both rapidly and accurately computes A⋅B provided that the resulting matrix product is sparse/compressible. As a consequence of our main result we increase the class of matrices A, for any given N×N matrix B, which allows the exact computation of A⋅B to be carried out using the conjectured O(N2+?) operations. Additionally, in the process of developing our matrix multiplication procedure, we present a modified version of Indyk's recently proposed extractor-based CS algorithm [P. Indyk, Explicit constructions for compressed sensing of sparse signals, in: SODA, 2008] which is resilient to noise.     

An algorithm for partitioning trees augmented with sibling edges

We investigate a special case of the graph partitioning problem: the partitioning of a sibling graph which is an ordered tree augmented with edges connecting consecutive nodes that share a common parent. We describe the algorithm, XS, and present a proof of its correctness.     

On mimicking networks representing minimum terminal cuts

Given a capacitated undirected graph G=(V,E)$G=(V,E)$ with a set of terminals K⊂V$K\subset V$, a mimicking network   is a smaller graph H=(_VH,_EH)$H=(V_H,E_H)$ which contains the set of terminals K   and for every bipartition [U,K−U]$[U,K-U]$ of the terminals, the cost of the minimum cut separating U   from K−U$K-U$ in G is exactly equal to the cost of the minimum cut separating U   from K−U$K-U$ in H.     

A variant of the Ford-Johnson algorithm that is more space efficient

A variant of the Ford-Johnson or merge insertion sorting algorithm that we called four Ford-Johnson (₄FJ, for short) is presented and proved to execute exactly the same number of comparisons than the Ford-Johnson algorithm. The main advantage of our algorithm is that, instead of recursively working over lists of size the half of the input, as the Ford-Johnson algorithm does, ₄FJ recursively works over lists of size the quarter of the input. This allows for implementations of data structures for coordinating the recursive calls of size only 33% of the ones needed for the Ford-Johnson algorithm.     

A simple approximation algorithm for the weighted matching problem

We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259-269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.     

An LP rounding algorithm for approximating uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP, for short) in which each client can be either assigned to some opened facility or rejected by paying a penalty. Existing approaches [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, p. 642] and [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003) 795] for this variant of facility location problem are all based on primal-dual method. In this paper, we present an efficient linear programming (LP) rounding based approach to show that LP rounding techniques are equally capable of solving this variant of facility location problem. Our algorithm uses a two-phase filtering technique (generalized from Lin and Vitter's [?-approximation with minimum packing constraint violation, in: Proc. 24th Annual ACM Symp. on Theory of Computing, 1992, p. 771]) to identify those to-be-rejected clients and open facilities for the remaining ones. Our approach achieves an approximation ratio of 2+2/e (≈2.736) which is worse than the best approximation ratio of 2 achieved by the much more sophisticated dual fitting technique [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003) 795], but better than the approximation ratio of 3 achieved by the primal-dual method [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, p. 642]. Our algorithm is simple, natural, and can be easily integrated into existing LP rounding based algorithms for facility location problem to deal with outliers.     

The reverse greedy algorithm for the metric k-median problem

The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the total distance to the remaining facilities. It stops when k facilities remain. We prove that, if the distance function is metric, then the approximation ratio of RGreedy is between Ω(logn/loglogn) and O(logn).     

A faster parameterized algorithm for set packing

We present an efficient parameterized algorithm for the (k,t)-set packing problem, in which we are looking for a collection of k disjoint sets whose union consists of t elements. The complexity of the algorithm is O(²O(t)nNlogN). For the special case of sets of bounded size, this improves the O(k(ck)n) algorithm of Jia et al. [J. Algorithms 50 (1) (2004) 106].     

Solving a system of difference constraints with variables restricted to a finite set

An algorithm is given for the solution of a system of difference constraints where the variables must take on values from a given finite set of real numbers.     

A note on maximizing the spread of influence in social networks

We consider the spread maximization problem that was defined by Domingos and Richardson (2001, 2002) [7] and [22]. In this problem, we are given a social network represented as a graph and are required to find the set of the most “influential” individuals that by introducing them with a new technology, we maximize the expected number of individuals in the network, later in time, that adopt the new technology. This problem has applications in viral marketing, where a company may wish to spread the rumor of a new product via the most influential individuals in popular social networks such as Myspace and Blogsphere.The spread maximization problem was recently studied in several models of social networks (Kempe et al. (2003, 2005) [14] and [15], Mossel and Roch (2007) [20]). In this short paper we study this problem in the context of the well studied probabilistic voter model. We provide very simple and efficient algorithms for solving this problem. An interesting special case of our result is that the most natural heuristic solution, which picks the nodes in the network with the highest degree, is indeed the optimal solution.     

On the density and discrepancy of a 2D point set with applications to thermal analysis of VLSI chips

In this era of giga-scale integration, thermal analysis has become one of the hot topics in VLSI chip design. Active thermal sources may be abstracted as a set of weighted points on a 2D chip-floor. The conventional notion of discrepancy that deals with the congestion properties of a set of scattered points may not be able to capture properly all real-life instances in this context. In this paper, we have introduced a new concept, called the density of a region to study some of the properties of the distribution of these weighted points. We prove several counter-intuitive results concerning the properties of the regions that have maximum or minimum density. We then outline algorithms for recognizing these regions. We also compare the attributes of density with the existing concept of discrepancy.     

Resource constrained scheduling on multiple machines

This paper is devoted to Resource Constrained Scheduling. An instance for this problem is given by a set of n jobs with lengths and weights and a set of m machines with capacities. At every time each machine can run arbitrary many jobs in parallel but the total weight of these jobs must not exceed the capacity of the machine. Furthermore the m machines work in parallel and we wish to find a schedule that minimizes the makespan or the sum of completion times. Thus load balancing on a cluster of servers is a typical application for scheduling under resource constraints. For both measures the problem is -complete even for m=1. We show that the problem is approximable within factors of 2 (makespan) and 14.85 (sum of completion times) for arbitrary m.     

A tree-covering problem arising in integrity of tree-structured data

We introduce and solve a problem motivated by integrity verification in third-party data distribution: Given an undirected tree, find a minimum-cardinality set of simple paths that cover all the tree edges and, secondarily, have smallest total path lengths. We give a linear time algorithm for this problem.     

Optimal algorithm for a special point-labeling problem

A special class of map labeling problem is studied. Let P={p₁,p₂,…,p_n} be a set of point sites distributed on a 2D map. A label associated with each point p_i is an axis-parallel rectangle r_i of specified width. The height of all are same. The placement of r_i must contain p_i at its top-left or bottom-left corner, and it does not obscure any other point in P. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. We first consider a simple model for this problem. Here, for each point p_i, the corner specification (i.e., whether the point p_i would appear at the top-left or bottom-left corner of the label) is known a priori. We show that the time complexity of this problem is , and then propose an algorithm for this problem which runs in O(nlogn) time. If the corner specifications of the points in P are not known, our algorithm is a 2-approximation algorithm. Here we propose an efficient heuristic algorithm that is easy to implement. Experimental evidences show that it produces optimal solutions for most of the randomly generated instances and for all the standard benchmarks available in http://www.math-inf.uni-greifswald.de/map-labeling/.     

New results on the time complexity and approximation ratio of the Broadcast Incremental Power algorithm

The Broadcast Incremental Power (BIP) algorithm is the most frequently cited method for the minimum energy broadcast routing problem. A recent survey concluded that BIP has O(³|V|) time complexity, and that its approximation ratio is at least 4.33. We strengthen these results to O(²|V|) and 4.598, respectively.     

Enhanced algorithms for Local Search

Let G=(V,E) be a finite graph, and be any function. The Local Search problem consists in finding a local minimum of the function f on G, that is a vertex v such that f(v) is not larger than the value of f on the neighbors of v in G. In this note, we first prove a separation theorem slightly stronger than the one of Gilbert, Hutchinson and Tarjan for graphs of constant genus. This result allows us to enhance a previously known deterministic algorithm for Local Search with query complexity , so that we obtain a deterministic query complexity of , where n is the size of G, d is its maximum degree, and g is its genus. We also give a quantum version of our algorithm, whose query complexity is of . Our deterministic and quantum algorithms have query complexities respectively smaller than the algorithm Randomized Steepest Descent of Aldous and Quantum Steepest Descent of Aaronson for large classes of graphs, including graphs of bounded genus and planar graphs.