Search

We study the generalized minimum Manhattan network (GMMN) problem: given a set P of pairs of points in the Euclidean plane R 2 , we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the L 1 metric (a so-called Manhattan path) for each pair in P . This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in P , and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach. [ABSTRACT FROM AUTHOR]

In a weighted undirected graph, a spanning/Steiner shallow-light tree (SLT) simultaneously approximates: 1) shortest distances from a root to the other vertices and 2) the minimum tree weight. The Steiner SLT has been proved to be exponentially lighter than the spanning one. In this paper, we propose a novel Steiner SLT construction method called Steiner SLT (SALT), which is efficient and has the tightest bound over all the state-of-the-art general-graph SLT algorithms. Applying SALT to Manhattan space offers a smooth tradeoff between rectilinear Steiner minimum tree and rectilinear Steiner minimum arborescence for VLSI routing. The adaption also reduces the time complexity from ${O}$ (${n} ^{2}$) to ${O}$ (${n}$ log ${n}$). Besides, several effective post-processing methods, including safe refinement and shallowness-constrained edge substitution, are proposed to further improve the result. The experimental results show that SALT can achieve not only short path lengths and wirelength but also small delay, compared to both classical and recent routing tree construction methods. [ABSTRACT FROM AUTHOR]

In this paper we deal with the planar location problem with forbidden regions. We consider the median objective with block norms and show that this problem is APX-hard, even when considering the Manhattan metric as distance function and polyhedral forbidden areas. As direct consequence, the problem cannot be approximated in polynomial time within a factor of 1.0019, unless P = N P . In addition, we give a dominating set that contains at least one optimal solution. Based on this result an approximation algorithm is derived. For special instances it is possible to improve the algorithm. These instances include problems with bounded forbidden areas and a special structure as interrelation between the new facilities. For uniform weights, this algorithm becomes an FPTAS. [ABSTRACT FROM AUTHOR]

The p -center problem is finding the location of p facilities among a set of n demand points such that the maximum distance between any demand point and its nearest facility is minimized. In this paper, we study this problem in the context of uncertainty, that is, the location of the demand points may change in a region like a disk or a segment, or belong to a finite set of points. We introduce Max- p -center and Min- p -center problems which are the worst and the best possible solutions for the p -center problem under such locational uncertainty. We propose approximation and parameterized algorithms to solve these problems under the Euclidean metric. Further, we study the MinMax Regret 1-center problem under uncertainty and propose a linear-time algorithm to solve it under the Manhattan metric as well as an O (n 4) time algorithm under the Euclidean metric. [ABSTRACT FROM AUTHOR]