Search

The spanning ratio and maximum detour of a graph G embedded in a metric space measure how well G approximates the minimum complete graph containing G and metric space, respectively. In this paper we show that computing the spanning ratio of a rectilinear path P in L1 space has a lower bound of Ώ(n logn) in the algebraic computation tree model and describe a deterministic O(n log2n) time algorithm. On the other hand, we give a deterministic O(n log2n) time algorithm for computing the maximum detour of a rectilinear path P in L1 space and obtain an O(n) time algorithm when P is a monotone rectilinear path. [ABSTRACT FROM AUTHOR]

In this paper we consider bi-criteria geometric optimization problems, in particular, the minimum diameter minimum cost spanning tree problem and the minimum radius minimum cost spanning tree problem for a set of points in the plane. The former problem is to construct a minimum diameter spanning tree among all possible minimum cost spanning trees, while the latter is to construct a minimum radius spanning tree among all possible minimum cost spanning trees. The graph-theoretic minimum diameter minimum cost spanning tree (MDMCST) problem and the minimum radius minimum cost spanning tree (MRMCST) problem have been shown to be NP-hard. We will show that the geometric version of these two problems, GMDMCST problem and GMRMCST problem are also NP-hard. We also give two heuristic algorithms, one MCST-based and the other MDST-based for the GMDMCST problem and present some experimental results. [ABSTRACT FROM AUTHOR]

In the paper we consider a generalized version of three well-known problems: Selection Problem in computer science, Slope Selection Problem in computational geometry and Maximum-Density Segment Problem in bioinformatics. Given a sequence A = (a1, w1),(a2, w2) ,..., (an, wn) of n ordered pairs (ai,wi) of real numbers ai and wi > 0 for each 1 ≤ i ≤ n, two nonnegative real numbers ℓ, u with ℓ ≤ u and a positive integer k, the Density Selection Problem is to find the consecutive subsequence A(i*,j*) over all O(n2) consecutive subsequences A(i,j) satisfying width constraint ]> such that the rank of its density ]> is k. We will give a randomized algorithm for density selection problem that runs in optimal expected O(n logn) time. [ABSTRACT FROM AUTHOR]

In this paper, we consider a map labeling problem to maximize the number of independent labels in the plane. We first investigate the point labeling model that each label can be placed on a given set of anchors on a horizontal line. It is known that most of the map labeling decision models on a single line (horizontal or slope line) can be easily solved. However, the label number maximization models are more difficult (like 2SAT vs. MAX-2SAT). We present an O(nlogΔ) time algorithm for the four position label model on a horizontal line based on dynamic programming and a particular analysis, where n is the number of the anchors and Δ is the maximum number of labels whose intersection is nonempty. As a contrast to Agarwal et al.'s result [Comput. Geom. Theory Appl. 11 (1998) 209-218] and Chan's result [Inform. Process. Letters 89(2004) 19-23] in which they provide (1 + 1/k)-factor PTAS algorithms that run in O(nlogn + n2k − 1) time and O(nlogn + nΔk − 1) time respectively for the fixed-height rectangle label placement model in the plane, we extend our method to improve their algorithms and present a (1 + 1/k)-factor PTAS algorithm that runs in O(nlogn + knlog4Δ + Δk − 1) time using O(kΔ3 log4Δ + kΔk − 1) storage. [ABSTRACT FROM AUTHOR]

Many real-life scheduling, routing and location problems can be formulated as combinatorial optimization problems whose goal is to find a linear layout of an input graph in such a way that the number of edge crossings is minimized. In this paper, we study a restricted version of the linear layout problem where the order of vertices on the line is fixed, the so-called fixed linear crossing number problem (FLCNP). We show that this $\mathcal{NP}$-hard problem can be reduced to the well-known maximum cut problem. The latter problem was intensively studied in the literature; efficient exact algorithms based on the branch-and-cut technique have been developed. By an experimental evaluation on a variety of graphs, we show that using this reduction for solving FLCNP compares favorably to earlier branch-and-bound algorithms. [ABSTRACT FROM AUTHOR]

We present an efficient reduction mapping undirected graphs G with n = 2k vertices for integers k to tables of partially specified Boolean functions g: {0,1}4k+1 →{0,1,⊥} so that for any integer m, G has a vertex colouring using m colours if and only if g has a consistent ordered binary decision diagram with at most (2m + 2)n2 + 4n decision nodes. From this it follows that the problem of finding a minimum-sized consistent OBDD for an incompletely specified truth table is NP-hard and also hard to approximate. [ABSTRACT FROM AUTHOR]

Several studies have reported that the linear program relaxation of integer multi-commodity network flow problems often provides integer optimal solutions. We explore this phenomenon with a 0-1 multi-commodity network with mutual arc capacity constraints. Characteristics of basic solutions in the linear programming relaxation problem of the 0-1 multi-commodity problem are identified. Specifically, necessary conditions for a linear programming relaxation to have a non-integer solution are presented. Based on the observed characteristics, a simple illustrative example problem is constructed to show that its LP relaxation problem has integer optimal solutions with a relatively high probability. Furthermore, to investigate whether or not and under what conditions this tendency applies to large-sized problems, we have carried out computational experiments by using randomly generated problem instances. The results of our computational experiment indicate that there exists a narrow band of arc density in which the 0-1 multi-commodity problems possess no integer optimal solutions. [ABSTRACT FROM AUTHOR]

We consider the problem of drawing a directed graph in two dimensions with a minimum number of crossings such that for every node the incoming edges appear consecutively in the cyclic adjacency lists. We show how to adapt the planarization method and the recently devised exact crossing minimization approach in a simple way. We report experimental results on the increase in the number of crossings involved by this additional restriction on the set of feasible drawings. It turns out that this increase is negligible for most practical instances. [ABSTRACT FROM AUTHOR]

Kolmogorov introduced a combinatorial measure of the information I(x : y) about the unknown value of a variable y conveyed by an input variable x taking a given value x. The paper extends this definition of information to a more general setting where ‘x = x′ may provide a vaguer description of the possible value of y. As an application, the space ${\cal P}(\{0,1\}^n)$ of classes of binary functions f:[n]→{0,1}, [n] = {1..., n}, is considered where y represents an unknown function t∈{0,1}[n] and as input, two extreme cases are considered: $\mathsf{x} = x_{{\mathcal M}_d}$ and $\mathsf{x} = x_{{\mathcal M}_d}$ which indicate that t is an element of a set $G\subseteq\{0,1\}^n$ that satisfies a property ${\mathcal M}_d$ or ${\mathcal M}_d$ respectively. Property ${\mathcal M}_d$ (or ${\mathcal M}_d$) means that there exists an $E\subseteq[n]$, E = d, such that trE(G) = 1 (or 2d) where trE(G) denotes the trace of G on E. Estimates of the information value $I(x_{{\mathcal M}_d}:t)$ and $I(x_{{\mathcal M}_d}:t)$ are obtained. When d is fixed, it is shown that $I(x_{{\mathcal M}_d}:t)\approx d$ and $I(x_{{\mathcal M}_d}:t)\approx 1$ as n→∞. Keywords: Information theory, combinatorial complexity, VC-dimension. [ABSTRACT FROM AUTHOR]

Given a pair of integers 2≤s ≤k, define gs(k) to be the minimum integer such that, for any regular multiple hypergraph H =({1..., k}, {e1..., em}) with edge size at most s, there is a permutation π on {1..., m} (or edge ordering eπ(1)..., eπ(m)) such that $g(H, \pi) =\max\{ \max \{d_{H_j}(u) - d_{H_j}(v) : u, v\in e_{\pi(j+1)}\} : j = 0, \dots, m-1\} \le g_s(k)$, where Hj = ({1..., k}, {eπ(1)..., eπ(j)}). The so-called edge ordering problem is to determine the value of gs(k) and to find a permutation π such that g(H, π)≤gs(k). This problem was raised from a switch box design problem, where the value of gs(k) can be used to design hyper-universal switch boxes and an edge ordering algorithm leads to a routing algorithm. In this paper, we show that (1) g2(k) = 1 for all k≥3, (2) gs(k) = 1 for 3≤s≤k≤6, and (3) gs(k) ≤2k for all k≥7. We give a heuristic algorithm for the edge ordering and conjecture that there is a constant C such that gs(k) ≤C for all k and s. [ABSTRACT FROM AUTHOR]