Inverse 1-median problem on trees under weighted Hamming distance

The inverse 1-median problem consists in modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. A linear time algorithm is first proposed for the inverse problem under weighted l _?? norm. Then two polynomial time algorithms with time complexities O(n log n) and O(n) are given for the problem under weighted bottleneck-Hamming distance, where n is the number of vertices. Finally, the problem under weighted sum-Hamming distance is shown to be equivalent to a 0-1 knapsack problem, and hence is ${\mathcal{NP}}$ -hard.     

Binary tree algebraic computation and parallel algorithms for simple graphs

In this paper we define the binary tree algebraic computation (BTAC) problem and develop an efficient parallel algorithm for solving this problem. A variety of graph problems (minimum covering set, minimum r-dominating set, maximum matching set, etc.) for trees and two terminal series parallel (TTSP) graphs can be converted to instances of the BTAC problem. Thus efficient parallel algorithms for these problems are obtained systematically by using the BTAC algorithm. The parallel computation model is an exclusive read exclusive write PRAM. The algorithms for tree problems run in O(log n) time with O(n) processors. The algorithms for TTSP graph problems run in O(log m) time with O(m) processors where n (m) is the number of vertices (edges) in the input graph. These algorithms are within an O(log n) factor of optimal.     

A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times

Consider an m-machine production line for processing identical parts served by a mobile robot. The problem is to find the minimum cycle time for 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. This work treats a special case of the 2-cyclic robot scheduling problem when the robot route is given and the operation durations are to be chosen from prescribed intervals. The problem was previously proved to be polynomially solvable in O(m⁸log m) time. This paper proposes an improved algorithm with reduced complexity O(m⁴).     

An asymptotically exact algorithm for the high-multiplicity bin packing problem

The bin packing problem consists of finding the minimum number of bins, of given capacity D, required to pack a set of objects, each having a certain weight. We consider the high-multiplicity version of the problem, in which there are only C different weight values. We show that when C=2 the problem can be solved in time O( log D). For the general case, we give an algorithm which provides a solution requiring at most C−2 bins more than the optimal solution, i.e., an algorithm that is asymptotically exact. For fixed C, the complexity of the algorithm is O(poly( log D)), where poly(·) is a polynomial function not depending on C.     

Enclosing a Set of Objects by Two Minimum Area Rectangles

In this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose anO(nα(n)log n) worst-case time algorithm, where α( ) is the inverse Ackermann's function, for finding, given a setMof points, segments and polygons defined bynvertices, a pair of axis-parallel rectangles (s, t) such thats∪tencloses all objects inMand area(s)+area(t) is minimum. The algorithm works inO(nα(n) log log n) worst-case space. Moreover, we prove an Ω(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case timeO(n log n), using worst-case spaceO(n log log n).     

Localized and compact data-structure for comparability graphs

We show that every comparability graph of any two-dimensional poset over n elements (a.k.a. permutation graph) can be preprocessed in O(n) time, if two linear extensions of the poset are given, to produce an O(n) space data-structure supporting distance queries in constant time. The data-structure is localized and given as a distance labeling, that is each vertex receives a label of O(logn) bits so that distance queries between any two vertices are answered by inspecting their labels only. This result improves the previous scheme due to Katz, Katz and Peleg [M. Katz, N.A. Katz, D. Peleg, Distance labeling schemes for well-separated graph classes, Discrete Applied Mathematics 145 (2005) 384-402] by a log n factor.As a byproduct, our data-structure supports all-pair shortest-path queries in O(d) time for distance-d pairs, and so identifies in constant time the first edge along a shortest path between any source and destination.More fundamentally, we show that this optimal space and time data-structure cannot be extended for higher dimension posets. More precisely, we prove that for comparability graphs of three-dimensional posets, every distance labeling scheme requires Ω(n^1/3) bit labels.     

A Baby Steps/Giant Steps Probabilistic Algorithm for Computing Roadmaps in Smooth Bounded Real Hypersurface

We consider the problem of constructing roadmaps of real algebraic sets. This problem was introduced by Canny to answer connectivity questions and solve motion planning problems. Given s polynomial equations with rational coefficients, of degree D in n variables, Canny’s algorithm has a Monte Carlo cost of sⁿlog(s)D^O(n2)s^{n}\log(s)D^{O(n^{2})} operations in ℚ; a deterministic version runs in time sⁿlog(s)D^O(n4)s^{n}\log(s)D^{O(n^{4})} . A subsequent improvement was due to Basu, Pollack, and Roy, with an algorithm of deterministic cost s^d+1D^O(n2)s^{d+1}D^{O(n^{2})} for the more general problem of computing roadmaps of a semi-algebraic set (d≤n is the dimension of an associated object).     

On the parity of the partition function

Let N be the set of all positive integers and D a subset of N. Let p(D,n) be the number of partitions of n with parts in D and let |D(x)| denote the number of elements of D not exceeding x. It is proved that if D is an infinite subset of N such that p(D,n) is even for all n?n₀, then |D(x)|?logx/log2−logn₀/log2. Moreover, if D is an infinite subset of N such that p(D,n) is odd for all n?n₀ and , then |D(x)|?logx/log2−logn₀/log2. These lower bounds are essentially the best possible.     

Dynamic programming algorithms for picture comparison

Two-dimensional arrays can be compared by a generalization of dynamic programming algorithms for string comparison. Earlier algorithms have computational complexity O(N⁶) for comparison of two N × N arrays. The computational complexity is reduced to O(N⁴) in general and O(N²) algorithms are pointed out for the range limited case. An example is given to illustrate the lack of knowledge of mathematical properties of these algorithms. The problem of finding an algorithm to compute the minimum number of insertions, deletions, and substitutions to transform one array into another remains open.     

A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function

Consider the resource allocation problem:minimize ∑ⁿ_i=1 f_i(x_i) subject to ∑ⁿ_i=1 x_i = N and x_i's being nonnegative integers, where each f_i is a convex function. The well-known algorithm based on the incremental method requires O(N log n + n) time to solve this problem. We propose here a new algorithm based on the Lagrange multiplier method, requiring O[n²(log N)²] time. The latter is faster if N is much larger than n. Such a situation occurs, for example, when the optimal sample size problem related to monitoring the urban air pollution is treated.     

Analysis of an algorithm for composition of binary quadratic forms

This note presents an algorithm which composes two reduced properly primitive binary quadratic forms of the same nonquadratic determinant D in O(M(log∥D∥)log log∥D∥) elementary operations.     

The two-machine no-wait general and proportionate open shop makespan problem

We consider the two-machine no-wait open shop minimum makespan problem in which the determination of an optimal solution requires an optimal pairing of the jobs followed by the optimal sequencing of the job pairs. We show that the required enumeration can be curtailed by reducing the pair sequencing problem for a given pair set to a traveling salesman problem which is equivalent to a two-machine no-wait flow shop problem solvable in O(n log n) time. We then propose an optimal O(n log n) algorithm for the proportionate problem with equal machine speeds in which each job has the same processing time on both machines. We show that our O(n log n) algorithm also applies to the more general proportionate problem with equal machine speeds and machine-specific setup times. We also analyze the proportionate problem with unequal machine speeds and conclude that the required enumeration can be further curtailed (compared to the problem with arbitrary job processing times) by eliminating certain job pairs from consideration.     

Difference sets and shifted primes

We show that if A is a subset of {1, …, n} which has no pair of elements whose difference is equal to p ? 1 with p a prime number, then the size of A is O(n(log log n)^{?c(log log log log log n)}) for some absolute c > 0.     

A locally optimal fast obstacle-avoiding path-planning algorithm

Two algorithms to compute the shortest collision-free paths in the Euclidean plane are presented. The ƒ obstacles assumed to be described by disjoint convex polygons having N vertices in total. After preprocessing time O(N+flogN), a suboptimal shortest path between two arbitrary query points can be found in O(f+NlogN) time using Dijkstra's algorithm and in Θ(N) time using the A¹ algorithm. The space complexity is O(N+f).     

On finding shortest paths in nonnegative networks

A modification of Dantzig's algorithm for the all pairs shortest paths problem is given. The new algorithm applies only to graphs with nonnegative arc lengths. For an N-node complete graph it has a worst case running time of $\text{2}\text{3}\text{N}{}^3$ triple operations of the form D_ij: = min(D_ij, D_ik + D_kj) and N² log N other comparisons. This contrasts with a lower bound of N(N ? 1) (N ? 2) triples in any pure triple operation algorithm, and seems to be the first algorithm in which no operation need be repeated N³ times. Sparsity and some other conditions may also be utilized.     

On the distribution of the roots of certain congruences and a problem for additive arithmetic functions

The asymptotic distribution of the roots of the congruence ax ≡ b (mod D), 1 ≤ x ≤ D, as D varies, is investigated. Quantitative estimates are obtained by means of exponential sums combined with sieve methods. As an application of the results it is shown that if an additive arithmetic function satisfies f(an + b) ? f(cn + d) = O(1) for all positive integers n, ad ≠ bc, then f(n) = O((log n)³) must hold. This result is apparently the first bound of any kind in such a situation.     

On the complexity of calculating factorials

It is shown that n! can be evaluated with time complexity O(log log nM (n log n)), where M(n) is the complexity of multiplying two n-digit numbers together. This is effected, in part, by writing n! in terms of its prime factors. In conjunction with a fast multiplication this yields an O(n(log n log log n)²) complexity algorithm for n!. This might be compared to computing n! by multiplying 1 times 2 times 3, etc., which is ω(n² log n) and also to computing n! by binary splitting which is O(log nM(n log n)).     

On rectangular visibility

Given a set of n points in the plane, two points are said to be rectangularly visible if the orthogonal rectangle with the two points as opposite vertices has no other point of the set in its interior. In this paper it is shown that all pairs of rectangularly visible points in a set of size n can be determined in O(n log n + k) time, where k is the number of reported pairs, using O(n) space. Also, we consider the query problem: Given a set V of points and an arbitrary point p, determine those points in V that are rectangularly visible from p. A dynamic data structure is described that uses O(n log n) space, has a query time of O(k + log²n) and an update time of O(log³ n). Additionally, we extend the results to the 3-dimensional case.     

Stable minimum space partitioning in linear time

In the stable0–1 sorting problem the task is to sort an array ofn elements with two distinct values such that equal elements retain their relative input order. Recently, Munro, Raman and Salowe gave an algorithm which solves this problem inO(n log*n) time and constant extra space. We show that by a modification of their method the stable0–1 sorting is possible inO(n) time andO(1) extra space. Stable three-way partitioning can be reduced to stable0–1 sorting. This immediately yields a stable minimum space quicksort, which sorts multisets in asymptotically optimal time with high probability.     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).