We consider a well studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and an integer d >= 1, in the maximum diameter-bounded subgraph problem (MaxDBS for short), the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d=1, this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n^{1-epsilon}, for any epsilon > 0. Moreover, it is known that, for any d >= 2, it is NP-hard to approximate MaxDBS within a factor n^{1/2 - epsilon}, for any epsilon > 0. In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems and several geometric properties of unit disk graphs.

An obstacle representation of a graph is a mapping of the vertices onto points in the plane and a set of connected regions of the plane (called obstacles) such that the straight-line segment connecting the points corresponding to two vertices does not intersect any obstacles if and only if the vertices are adjacent in the graph. The obstacle representation and its plane variant (in which the resulting representation is a plane straight-line embedding of the graph) have been extensively studied with the main objective of minimizing the number of obstacles. Recently, Biedl and Mehrabi [Therese C. Biedl and Saeed Mehrabi, 2017] studied non-blocking grid obstacle representations of graphs in which the vertices of the graph are mapped onto points in the plane while the straight-line segments representing the adjacency between the vertices is replaced by the L_1 (Manhattan) shortest paths in the plane that avoid obstacles. In this paper, we introduce the notion of geodesic obstacle representations of graphs with the main goal of providing a generalized model, which comes naturally when viewing line segments as shortest paths in the Euclidean plane. To this end, we extend the definition of obstacle representation by allowing some obstacles-avoiding shortest path between the corresponding points in the underlying metric space whenever the vertices are adjacent in the graph. We consider both general and plane variants of geodesic obstacle representations (in a similar sense to obstacle representations) under any polyhedral distance function in R^d as well as shortest path distances in graphs. Our results generalize and unify the notions of obstacle representations, plane obstacle representations and grid obstacle representations, leading to a number of questions on such representations.

Given $n$ pairs of points, $\mathcal{S} = \{\{p_1, q_1\}, \{p_2, q_2\}, \dots, \{p_n, q_n\}\}$, in some metric space, we study the problem of two-coloring the points within each pair, red and blue, to optimize the cost of a pair of node-disjoint networks, one over the red points and one over the blue points. In this paper we consider our network structures to be spanning trees, traveling salesman tours or matchings. We consider several different weight functions computed over the network structures induced, as well as several different objective functions. We show that some of these problems are NP-hard, and provide constant factor approximation algorithms in all cases.

In this paper, we study the problem of data gathering in ad-hoc sensor networks using a mobile entity called mule. The mule traverses the children of failed sensors, to prevent loss of data. Our objective is to define the optimal communication tree and the mule's placement such that the mule's overall traveling distance is minimized. We explore this problem in several network topologies including: unit disc graph on a line (UDL), general unit disc graph (UDG), and a complete graph with failing probabilities on the nodes (CGFP). We provide an optimal solution for the UDL problem and two approximation algorithms for the UDG problem. For the CGFP problem we outline the two possible structures of an optimal solution and provide near optimal approximation algorithms.

Motivated by applications to graph morphing, we consider the following compatible connectivity-augmentation problem: We are given a labelled n-vertex planar graph, G, that has r ≥ 2 connected components, and k ≥ 2 isomorphic planar straight-line drawings, G1, …, G2, of G. We wish to augment G by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to G1, …, G2 as points and straight-line segments, respectively, to obtain k planar straight-line drawings isomorphic to the augmentation of G. We show that adding Θ(nr1–1/k) edges and vertices to G is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all r ∊ {2, …, n} and k ≥ 2 and is achievable by an algorithm whose running time is O(nr1–1/k) for k = O(1) and whose running time is O(kn2) for general values of k. The lower bound holds for all r ∊ {2, …, n/4} and k ≥ 2.

We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using "t-spanning" routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t-spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time.

We consider a geometric optimization problem that arises in network design. Given a set P of n points in the plane, source and destination points s,t ∈ P, and an integer k > 0, one has to locate k Steiner points, such that the length of the longest edge of a bottleneck path between s and t is minimized. In this paper, we present an O(n log2 n)-time algorithm that computes an optimal solution, for any constant k. This problem was previously studied by Hou et al. [Hou10], who gave an O(n2log n)-time algorithm. We also study the dual version of the problem, where a value λ > 0 is given (instead of k), and the goal is to locate as few Steiner points as possible, so that the length of the longest edge of a bottleneck path between s and t is at most λ.

The phylogenetic diversity (PD) of a set of species is a measure of their evolutionary distinctness based on a phylogenetic tree. PD is increasingly being adopted as an index of biodiversity in ecological conservation projects. The Noah's Ark Problem (NAP) is an NP-Hard optimization problem that abstracts a fundamental conservation challenge in asking to maximize the expected PD of a set of taxa given a fixed budget, where each taxon is associated with a cost of conservation and a probability of extinction. Only simplified instances of the problem, where one or more parameters are fixed as constants, have as of yet been addressed in the literature. Furthermore, it has been argued that PD is not an appropriate metric for models that allow information to be lost along paths in the tree. We therefore generalize the NAP to incorporate a proposed model of feature loss according to an exponential distribution and term this problem NAP with Loss (NAPL). In this paper, we present a pseudopolynomial time approximation scheme for NAPL.

This work presents a new radio paths computation frame-work especially designed for complex indoor RF field prediction. We propose a new algorithm utilizing a geometric visibility graph of a building to traverse all possible bounded radio paths. These paths are needed to compute the signal strength as received at given receiver location. We have implemented the suggested algorithm and performed a set of experiments testing the radio paths over complex buildings. The main conclusion is that the new algorithm is both (i) Accurate: predicts the signal strength within complex buildings, (ii) Runtime efficient: can compute all relevant radio paths even on relatively complex structures comprised of thousands of walls in a matter of seconds.

A power assignment is an assignment of transmission power to each of the nodes of a wireless network, so that the induced communication graph has some desired properties. The cost of a power assignment is the sum of the powers. The energy of a transmission path from node u to node v is the sum of the squares of the distances between adjacent nodes along the path. For a constant t > 1, an energy t-spanner is a graph G', such that for any two nodes u and v, there exists a path from u to v in G', whose energy is at most t times the energy of a minimum-energy path from a ton in the complete Euclidean graph. In this paper, we study the problem of finding a power assignment, such that (i) its induced communication graph is a 'good' energy spanner, and (ii) its cost is 'low'. We show that for any constant t > 1, one can find a power assignment, such that its induced communication graph is an energy t-spanner, and its cost is bounded by some constant times the cost of an optimal power assignment (where the sole requirement is strong connectivity of the induced communication graph). This is a very significant improvement over the best current result due to Shpungin and Segal, presented in last year's conference.

We examine bounds on the locality of routing. A local routing algorithm makes a sequence of distributed forwarding decisions, each of which is made using only local information. Specifically, in addition to knowing the node for which a message is destined, an intermediate node might also know a) the subgraph corresponding to all network nodes within k hops of itself, for some value of k, b) the node from which the message originated, and c) which of its neighbours last forwarded the message. Our objective is to determine which of these parameters are necessary and/or sufficient to permit local routing as k varies on a network modelled by a connected undirected graph. In particular, we establish tight bounds on k for the feasibility of deterministic k-local routing for various combinations of these parameters, as well as corresponding bounds on dilation (the worst-case ratio of actual route length to shortest path length).

We address the following problem: Given a complete k-partite geometric graph K whose vertex set is a set of n points in $\mathbb{R}^d$, compute a spanner of K that has a “small” stretch factor and “few” edges. We present two algorithms for this problem. The first algorithm computes a $(5+\epsilon)$-spanner of K with $O(n)$ edges in $O(n\log n)$ time. The second algorithm computes a $(3+\epsilon)$-spanner of K with $O(n\log n)$ edges in $O(n \log n)$ time. The latter result is optimal: We show that for any $2\leq k\leq n-\Theta(\sqrt{n\log n})$, spanners with $O(n\log n)$ edges and stretch factor less than 3 do not exist for all complete k-partite geometric graphs.

Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms which do not leak unnecessary information. Specifically, we are interested in private approximation algorithms -- efficient algorithms whose output does not leak information not implied by the optimal solutions to the search problems. Privacy requirements add constraints on the approximation algorithms; in particular, known approximation algorithms usually leak a lot of information.For functions, [Feigenbaum et al., ICALP 2001] presented a natural requirement that a private algorithm should not leak information not implied by the original function. Generalizing this requirement to search problems is not straightforward as an input may have many different outputs. We present a new definition that captures a minimal privacy requirement from such algorithms -- applied to an input instance, it should not leak any information that is not implied by its collection of exact solutions. Although our privacy requirement seems minimal, we show that for well studied problems, as vertex cover and 3SAT, private approximation algorithms are unlikely to exist even for poor approximation ratios. Similar to [Halevi et al., STOC 2001], we define a relaxed notion of approximation algorithms that leak (little) information, and demonstrate the applicability of this notion by showing near optimal approximation algorithms for 3SAT that leak little information.

We consider the problem of balancing the load among several service-providing facilities, while keeping the total cost low. Let D be the underlying demand region, and let p1, …, pm be m points representing m facilities. We consider the following problem: Subdivide D into m equal-area regions R1, …, Rm, so that region Ri is served by facility pi, and the average distance between a point q in D and the facility that serves q is minimal.We present constant-factor approximation algorithms for this problem, with the additional requirement that the resulting regions must be convex. As an intermediate result we show how to partition a convex polygon into m=2k equal-area convex subregions so that the fatness of the resulting regions is within a constant factor of the fatness of the original polygon. We also prove that our partition is, up to a constant factor, the best one can get if one's goal is to maximize the fatness of the least fat subregion.We also discuss the structure of the optimal partition for the aforementioned load balancing problem: indeed, we argue that it is always induced by an additive-weighted Voronoi diagram for an appropriate choice of weights.