A note on the Consecutive Ones Submatrix problem

A binary matrix has the Consecutive Ones Property (C1P) for columns if there exists a permutation of its rows that leaves the 1's consecutive in every column. The problem of Consecutive Ones Property for a matrix is a special variant of Consecutive Ones Submatrix problem in which a positive integer K is given and we want to know if there exists a submatrix B of A consisting of K columns of A with C1P property. This paper presents an error in the proof of NP-completeness for this problem in the reference cited in text by Garey and Johnson [Computers and Intractability, A Guide to the Theory of NP-Completeness, 1979].     

Efficient and practical resource block allocation for LTE-based D2D network via graph coloring

In this paper, we construct a practical framework for efficiently allocating long term evolution (LTE) resource blocks (RB) among the users in a device-to-device (D2D) network. For such network that presumably operates under the LTE cellular network, our aim is to improve the overall throughput of D2D connections using opportunistic or fairness-based approach. Taking the practical considerations into account, our proposed framework allows a number of connections to share a single RB whenever possible, thus utilizing the radio resources. To do so, our solution first identifies a superior set of the interference-free D2D reuse groups via graph modeling and graph coloring approach. In particular, we model a D2D network with a two-overlapping disk graph for which a suitable coloring algorithm is proposed and its performance bound is calculated. Once the reuse groups are known, our solution optimizes the RB allocation among these groups based on their reported channel condition as well as the scheduling criterion, whether it is fairness-based or opportunistic. Through numerical experiments, we show that our solution can significantly improve the throughput performance of a D2D network.     

On a Local Protocol for Concurrent File Transfers

We study a very natural local protocol for a file transfer problem. Consider a scenario where several files, which may have varied sizes and get created over a period of time, are to be transferred between pairs of hosts in a distributed environment. Our protocol assumes that while executing the file transfers, an individual host does not use any global knowledge; and simply subdivides its I/O resources equally among all the active file transfers at that host at any point in time. This protocol is motivated by its simplicity of use and its applications to scheduling map-reduce workloads. Here we study the problem of deciding the start times of individual file transfers to optimize QoS metrics like average completion time or MakeSpan. To begin with, we show that these problems are NP-hard. We next argue that the ability of scheduling multiple concurrent file transfers at a host makes our protocol stronger than previously studied protocols that schedule a sequence of matchings, in which no two active file transfers share a host at any time. We then generalize the approach of Queyranne and Sviridenko (J. Algorithms 45:202–212, 2002) and Gandhi et al. (ACM Trans. Algorithms 4(1), 2008) that relates the MakeSpan and completion time objectives and present constant factor approximation algorithms.     

ℓ 2 2 Spreading Metrics for Vertex Ordering Problems

We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of $O(\sqrt{\log n}\log\log n)We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) , O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) , and O(?{logT}loglogT)O(\sqrt{\log T}\log\log T) , respectively, the last running in time polynomial in T (T being the sum of execution times). The technical contribution of our paper is to introduce “ℓ ₂² spreading metrics” (that can be computed by semidefinite programming) as relaxations for both undirected and directed “permutation metrics,” which are induced by permutations of {1,2,…,n}. The techniques introduced in the recent work of Arora, Rao and Vazirani (Proc. of 36th STOC, pp. 222–231, 2004) can be adapted to exploit the geometry of such ℓ ₂² spreading metrics, giving a powerful tool for the design of divide-and-conquer algorithms. In addition to their applications to approximation algorithms, the study of such ℓ ₂² spreading metrics as relaxations of permutation metrics is interesting in its own right. We show how our results imply that, in a certain sense we make precise, ℓ ₂² spreading metrics approximate permutation metrics on n points to a factor of O(?{logn}loglogn)O(\sqrt{\log n}\log\log n) .     

Local Search Algorithms for the Red-Blue Median Problem

In this paper, we consider the following red-blue median problem which is a generalization of the well-studied k-median problem. The input consists of a set of red facilities, a set of blue facilities, and a set of clients in a metric space and two integers k _r ,k _b ≥0. The problem is to open at most k _r red facilities and at most k _b blue facilities and minimize the sum of distances of clients to their respective closest open facilities.     

Euclidean Prize-Collecting Steiner Forest

In this paper, we consider Steiner forest and its generalizations, prize-collecting Steiner forest and k-Steiner forest, when the vertices of the input graph are points in the Euclidean plane and the lengths are Euclidean distances. First, we present a simpler analysis of the polynomial-time approximation scheme (PTAS) of Borradaile et?al. (Proceedings of the 49th annual IEEE symposium on foundations of computer science, FOCS, pp.?115–124, 2008) for the Euclidean Steiner forest problem. This is done by proving a new structural property and modifying the dynamic programming by adding a new piece of information to each dynamic programming state. Next we develop a PTAS for a well-motivated case, i.e., the multiplicative case, of prize-collecting and budgeted Steiner forest. The ideas used in the algorithm may have applications in design of a broad class of bicriteria PTASs; see Sect.?1.3. At the end, we demonstrate why PTASs for these problems can be hard in the general Euclidean case (and thus for PTASs we cannot go beyond the multiplicative case). In fact, this conjecture was later proved by Bateni, Hajiaghayi and Marx?(1006.4339 [abs], 2009).