Search

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]

Inferring a graph from path frequency has been studied as an important problem which has a potential application to drug design. Given a multiple set g of strings of labels with length at most K, the problem asks to find a vertex-labeled graph G that attains a one-to-one correspondence between g and the set of sequences of labels along all paths of length at most K in G. In this paper, we prove that the problem with K=1 can be formulated as a problem of finding a loopless and connected detachment, based on which an efficient algorithm for solving the problem is derived. Our algorithm also solves the problem with an additional constraint such that every vertex is required to have a specified degree. [ABSTRACT FROM AUTHOR]

We consider model based estimates for set-up time. The general setting we are interested in is the following: given a disk and a sequence of read/write requests to certain locations, we would like to know the total time of transitions (set-up time) when these requests are served in an orderly fashion. The problem becomes nontrivial when we have, as is typically the case, only the counts of requests to each location rather then the whole input, in which case we can only hope to estimate the required time. Models that estimate the set-up time have been suggested and heavily used as far back as the sixties. However, not much theory exists to enable a qualitative understanding of such models. To this end we introduce several properties through which we can study different models such as (i) super-additivity which means that the set-up time estimate decreases as the input data is refined (ii) monotonicity which means that more activity produces more set-up time, and (iii) an approximation guarantee for the estimate with respect to the worst possible time. We provide criteria for super-additivity and monotonicity to hold for popular models such as the independent reference model (IRM). The criteria show that the estimate produced by these models will be monotone for any reasonable system. We also show that the IRM based estimate functions, upto a factor of 2, as a worst case estimate to the actual set-up time. To establish our theoretical results we use the theory of finite metric spaces, and en route show a result of independent interest in that theory, which is a strengthening of a theorem of Kelly [4] about the properties of metrics that are formed by concave functions on the line. [ABSTRACT FROM AUTHOR]

The enumerate-and-expand paradigm for solving NP-hard problems has been introduced and applied to some Vertex Cover variants in a recently published preliminary paper. In this paper we improve on the runtime for Connected Vertex Cover, obtaining a bound of O*(2.7606k),The O*-notation is equivalent to the well-known Landau notation, except that polynomial factors may be suppressed. For instance, 2kk2n3=O*(2k). and use the technique in order to gain the fastest known method for counting the number of vertex covers in a graph, which takes O*(1.3803k) time. [ABSTRACT FROM AUTHOR]

Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires Θ(n log n) time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(nα(n, n)) time in the worst case, where α(n, n) is the inverse Ackermann function. [ABSTRACT FROM AUTHOR]

We define a language to be overlap-free if any two distinct strings in the language do not overlap with each other. We observe that overlap-free languages are a proper subfamily of infix-free languages and also a proper subfamily of comma-free languages. Based on these observations, we design a polynomial-time algorithm that determines overlap-freeness of a regular language. We consider two cases: A language is specified by a nondeterministic finite-state automaton and a language is described by a regular expression. Furthermore, we examine the prime overlap-free decomposition of overlap-free regular languages and show that the prime overlap-free decomposition is not unique. [ABSTRACT FROM AUTHOR]

Interval graphs play important roles in analysis of DNA chains in Benzer [1], restriction maps of DNA in Waterman and Griggs [11] and other related areas. In this paper, we study a new combinatorial optimization problem, named as the minimum clique partition problem with constrained weight, for interval graphs. For a weighted interval graph G and a bound B, partition the weighted intervals of this graph G into the smallest number of cliques, where each clique, consisting of some intervals whose intersection on a real line is not empty, has its weight not beyond B. We obtain the following results: (1) This problem is NP-hard in the strong sense, and it cannot be approximated within a ratio $\frac{3}{2}-\varepsilon$ in polynomial-time for any ε> 0; (2) We design some approximation algorithms with different constant ratios to this problem; (3) For the case where all intervals have the same weight, we also design an optimal algorithm to solve the problem in linear time. Keywords: Interval graph, cliques, approximation algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider an interesting variant of the well-known Steiner tree problem: Given a complete graph G = (V,E) with a cost function c:E →R+ and two subsets R and R′ satisfying $R'\subset R\subseteq V$, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R′ cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we show that the problem is MAX SNP-hard even when the costs of all edges in the input graph are restricted to either 1 or 2. We also present an approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

In this paper we present approximation results for the class constrained bin packing problem that has applications to Video-on-Demand Systems. In this problem we are given bins of capacity B with C compartments, and n items of Q different classes. The problem is to pack the items into the minimum number of bins, where each bin contains items of at most C different classes and has total items size at most B. We present several approximation algorithms for off-line and online versions of the problem. [ABSTRACT FROM AUTHOR]

While the complexity of min-max and min-max regret versions of most classical combinatorial optimization problems has been thoroughly investigated, there are very few studies about their approximation. For a bounded number of scenarios, we establish a general approximation scheme which can be used for min-max and min-max regret versions of some polynomial problems. Applying this scheme to shortest path and minimum spanning tree, we obtain fully polynomial-time approximation schemes with much better running times than the ones previously presented in the literature. Keywords: min-max, min-max regret, approximation, fptas, shortest path, minimum spanning tree. [ABSTRACT FROM AUTHOR]

A planar polyomino of size n is an edge-connected set of n squares on a rectangular 2-D lattice. Similarly, a d-dimensional polycube (for d ≥2) of size n is a connected set of n hypercubes on an orthogonal d-dimensional lattice, where two hypercubes are neighbors if they share a (d-1)-dimensional face. There are also two-dimensional polyominoes that lie on a triangular or hexagonal lattice. In this paper we describe a generalization of Redelmeier's algorithm for counting two-dimensional rectangular polyominoes [Re81], which counts all the above types of polyominoes. For example, our program computed the number of distinct 3-D polycubes of size 18. To the best of our knowledge, this is the first tabulation of this value. Keywords: Polycubes, lattice animals, subgraph counting. [ABSTRACT FROM AUTHOR]