Incremental labeling in closed-2PM model

We consider an incremental optimal label placement in a closed-2PM map containing points each attached with a label. Labels are assumed to be axis-parallel square-shaped and have to be pairwise disjoint with maximum possible length each attached to its corresponding point on one of its horizontal edges. Such a labeling is denoted as optimal labeling. Our goal is to efficiently generate a new optimal labeling for all points after each new point being inserted in the map. Inserting each point may require several labels to flip or all labels to shrink. We present an algorithm that generates each new optimal labeling in O(lgn+k) time where k is the number of required label flips, if there is no need to shrink the label lengths, or in O(n) time when we have to shrink the labels and flip some of them. The algorithm uses O(n) space in both cases. This is a new result on this problem.     

A new approximation algorithm for labeling points with circle pairs

We study the NP-hard problem of labeling points with maximum-radius circle pairs: given n point sites in the plane, find a placement for 2n interior-disjoint uniform circles, such that each site touches two circles and the circle radius is maximized. We present a new approximation algorithm for this problem that runs in time and O(n) space and achieves an approximation factor of (≈1.486+ε), which improves the previous best bound of 1.491+ε.     

Labeling points with given rectangles

In this paper, we consider the following problem: Given n pairs of a point and an axis-parallel rectangle in the plane, place each rectangle at each point in order that the point lies on the corner of the rectangle and the rectangles do not intersect. If the size of the rectangles may be enlarged or reduced at the same factor, maximize the factor. This paper generalizes the results of Formann and Wagner [Proc. 7th Annual ACM Symp. on Comput. Geometry (SoCG'91), 1991, pp. 281-288]. They considered the uniform squares case and showed that there is no polynomial time algorithm less than 2-approximation. We present a 2-approximation algorithm of the non-uniform rectangle case which runs in O(n²logn) time and takes O(n²) space. We also show that the decision problem can be solved in O(nlogn) time and space in the RAM model by transforming the problem to a simpler geometric problem.     

Optimal 2-constraint satisfaction via sum-product algorithms

We show that for a given set of m pairwise constraints over n variables, a variable assignment that satisfies maximally many m constraints (MAX-2-CSP) can be found in time, where d is the maximum number of states per variable, and ω<2.376 is the matrix product exponent over a ring; the notation O^∗ suppresses factors polylogarithmic in m and n. As a corollary, MAX-2-SAT can be solved in O^∗(nmn^1.732) time. This improves on a recent result by Williams [R. Williams, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoret. Comput. Sci. 348 (2-3) (2005) 357-365] by reducing the polynomial factor from nm³ to about nm.     

A simple factor-3 approximation for labeling points with circles

In this paper we present a simple factor-(3+ε), 0<ε<1, approximation algorithm, which runs in O(nlogn+n(1/ε)^O(1/ε2)log(D₃/εD₂)) time, for the problem of labeling a set P of n distinct points with uniform circles. (D₂ is the closest pair of P and D₃ is the minimum diameter of all subsets of P with size three.) This problem is known to be NP-hard. Our bound improves the previous factor of 3.6+ε.     

Optimal shift partitioning of pharmacies

The pharmacy service requires that some pharmacies are always available and shifts have to be organized: a shift corresponds to a subset of pharmacies that must be open 24 hours a day on a particular week. Under the requirement that each pharmacy belongs to exactly one shift and the assumption that users minimize the distance to the closest open pharmacy during each shift, we want to determine a partition of the pharmacies into a given number of shifts, such that the total distance covered by users is minimized. It may be also required that shift cardinalities are balanced. We discuss different versions and the related computational complexity, showing that the problem is NP-hard in general. A set packing formulation is presented and solved by branch-and-price, together with a fast solution technique based on a tabu search. They have been applied to real and random instances showing that (i) the set packing formulation is very tight and often exhibits no integrality gap; (ii) the branch-and-price solves problems of practical relevance to optimality in a reasonable amount of time (order of minutes); (iii) the tabu search finds optimal or near-optimal solutions in order of seconds.     

Optimal direct sum results for deterministic and randomized decision tree complexity

A Direct Sum Theorem holds in a model of computation, when for every problem solving some k input instances together is k times as expensive as solving one. We show that Direct Sum Theorems hold in the models of deterministic and randomized decision trees for all relations. We also note that a near optimal Direct Sum Theorem holds for quantum decision trees for boolean functions.     

Optimal strong primes

We clarify the notion of a strong prime by supplying a precise definition and a characterization for an optimal strong prime. We present a conjecture regarding the distribution and density of optimal strong primes, allowing one to predict in advance the time needed to compute one optimal strong prime of a given bit length. Based on these results, we develop an algorithm to compute optimal strong primes. Some experimental results are also included.     

Optimal state-space lumping in Markov chains

We prove that the optimal lumping quotient of a finite Markov chain can be constructed in O(mlgn) time, where n is the number of states and m is the number of transitions. Our proof relies on the use of splay trees (designed by Sleator and Tarjan [J. ACM 32 (3) (1985) 652-686]) to sort transition weights.     

On the intrinsic complexity of point finding in real singular hypersurfaces

In previous work we designed an efficient procedure that finds an algebraic sample point for each connected component of a smooth real complete intersection variety. This procedure exploits geometric properties of generic polar varieties and its complexity is intrinsic with respect to the problem. In the present paper we introduce a natural construction that allows to tackle the case of a non-smooth real hypersurface by means of a reduction to a smooth complete intersection.     

Optimal Solutions for the Temporal Precedence Problem

Abstract. In this paper we refer to the Temporal Precedence Problem on Pure Pointer Machines . This problem asks for the design of a data structure, maintaining a set of stored elements and supporting the following two operations: insert and precedes . The operation insert (a) introduces a new element a in the structure, while the operation precedes (a,b) returns true iff element a was inserted before element b temporally. In [11] a solution was provided to the problem with worst-case time complexity O (log log n ) per operation and O(n log log n) space, where n is the number of elements inserted. It was also demonstrated that the precedes operation has a lower bound of Ω (log log n ) for the Pure Pointer Machine model of computation. In this paper we present two simple solutions with linear space and worst-case constant insertion time. In addition, we describe two algorithms that can handle the precedes (a,b) operation in O (log log d ) time, where d is the temporal distance between the elements a and b .     

Optimal algorithm for a special point-labeling problem

A special class of map labeling problem is studied. Let P={p₁,p₂,…,p_n} be a set of point sites distributed on a 2D map. A label associated with each point p_i is an axis-parallel rectangle r_i of specified width. The height of all are same. The placement of r_i must contain p_i at its top-left or bottom-left corner, and it does not obscure any other point in P. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. We first consider a simple model for this problem. Here, for each point p_i, the corner specification (i.e., whether the point p_i would appear at the top-left or bottom-left corner of the label) is known a priori. We show that the time complexity of this problem is , and then propose an algorithm for this problem which runs in O(nlogn) time. If the corner specifications of the points in P are not known, our algorithm is a 2-approximation algorithm. Here we propose an efficient heuristic algorithm that is easy to implement. Experimental evidences show that it produces optimal solutions for most of the randomly generated instances and for all the standard benchmarks available in http://www.math-inf.uni-greifswald.de/map-labeling/.     

On the P versus NP intersected with co-NP question in communication complexity

We consider the analog of the P versus NP∩co-NP question for the classical two-party communication protocols where polynomial time is replaced by poly-logarithmic communication: if both a boolean function f and its negation ¬f have small (poly-logarithmic in the number of variables) nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition model of communication this question was answered by Aho, Ullman and Yannakakis in 1983: here P=NP∩co-NP.We show that in the best partition model of communication the situation is entirely different: here P is a proper subset even of RP∩co-RP. This, in particular, resolves an open question raised by Papadimitriou and Sipser in 1982.     

Improving the labeling accuracy by a new probabilistic relaxation labeling

The updating rule of probabilistic relaxation labeling (PRL) is analyzed. A new updating rule is derived by replacing a simplifying assumption used in the derivation of the conventional updating rule with a more relevant one. The PRL with the new updating rule does not show the labeling degradation phase which appears in the conventional PRL.     

On the query complexity of finding a local maximum point

We calculate the minimal number of queries sufficient to find a local maximum point of a function on a discrete interval, for a model with M parallel queries, M?1. Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers.     

There are no pure relational width 2 constraint satisfaction problems

In this note, we show that every constraint satisfaction problem that has relational width 2 has also relational width 1. This is achieved by means of an obstruction-like characterization of relational width which we believe to be of independent interest.     

On the parameterized complexity of d-dimensional point set pattern matching

Deciding whether two n-point sets A,B∈Rd are congruent is a fundamental problem in geometric pattern matching. When the dimension d is unbounded, the problem is equivalent to graph isomorphism and is conjectured to be in FPT.When |A|=m<|B|=n, the problem becomes that of deciding whether A is congruent to a subset of B and is known to be NP-complete. We show that point subset congruence, with d as a parameter, is W[1]-hard, and that it cannot be solved in O(mno(d))-time, unless SNP⊂DTIME(²o(n)). This shows that, unless FPT=W[1], the problem of finding an isometry of A that minimizes its directed Hausdorff distance, or its Earth Mover's Distance, to B, is not in FPT.     

Nearly-perfect hypergraph packing is in NC

Answering a question of Rödl and Thoma, we show that the Nibble Algorithm for finding a collection of disjoint edges covering almost all vertices in an almost regular, uniform hypergraph with negligible pair degrees can be derandomized and parallelized to run in polylog time on polynomially many parallel processors. In other words, the nearly-perfect packing problem on this class of hypergraphs is in the complexity class NC.