On a dual version of the one-dimensional bin packing problem

The NP-hard problem of packing items from a given set into bins so as to maximize the number of bins used, subject to the constraint that each bin be filled to at least a given threshold, is considered. Approximation algorithms are presented that provide guarantees of , , and the optimal number, at running time costs of O(n), O(nlogn), and O(nlog²n), respectively, and the average case behavior of these algorithms is explored via empirical tests on randomly generated sets of items.     

Efficient 2 and 3-Flip Neighborhood Search Algorithms for the MAX SAT: Experimental Evaluation

For problems SAT and MAX SAT, local search algorithms are widely acknowledged as one of the most effective approaches. Most of the local search algorithms are based on the 1-flip neighborhood, which is the set of solutions obtainable by flipping the truth assignment of one variable. In this paper, we consider r-flip neighborhoods for r = 2, 3, and examine their effectiveness by computational experiments. In the accompanying paper, we proposed new implementations of these neighborhoods, and showed that the expected size of 2-flip neighborhood is O(n + m) and that of 3-flip neighborhood is O(m + t ² n), compared to their original size O(n ²) andO(n ³), respectively, where n is the number of variables, m is the number of clauses and t is the maximum number of appearances of one variable. These are used in this paper under the framework of tabu search and other metaheuristic methods, and compared with other existing algorithms with 1-flip neighborhood. The results exhibit good prospects of larger neighborhoods.     

Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions

The combinatorial complexity of the Voronoi diagram ofnlines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to beO(n²α(n)log n), where α(n) is a slowly growing inverse of the Ackermann function. There are arrangements ofnlines where this complexity can be as large as Ω(n²α(n)).     

3-coloring in time

We consider worst case time bounds for several NP-complete problems, based on a constraint satisfaction (CSP) formulation of these problems: (a,b)-CSP instances consist of a set of variables, each with up to a possible values, and constraints disallowing certain b-tuples of variable values; a problem is solved by assigning values to all variables satisfying all constraints, or by showing that no such assignment exist. 3-SAT is equivalent to (2,3)-CSP while 3-coloring and various related problems are special cases of (3,2)-CSP; there is also a natural duality transformation from (a,b)-CSP to (b,a)-CSP. We show that n-variable (3,2)-CSP instances can be solved in time O(1.3645ⁿ), that satisfying assignments to (d,2)-CSP instances can be found in randomized expected time O((0.4518d)ⁿ); that 3-coloring of n-vertex graphs can be solved in time O(1.3289ⁿ); that 3-list-coloring of n-vertex graphs can be solved in time O(1.3645ⁿ); that 3-edge-coloring of n-vertex graphs can be solved in time O(2^n/2), and that 3-satisfiability of a formula with t 3-clauses can be solved in time O(n^O(1)+1.3645^t).     

An Improved Bound on the Number of Unit Area Triangles

We show that the number of unit-area triangles determined by a set of n points in the plane is O(n ^9/4+ε ), for any ε>0, improving the recent bound O(n ^44/19) of Dumitrescu et al.     

Composite Integers n for Which φ（n）｜n- 1

In this note, we show that the number of composite integers n ≤ x such that φ（n）｜n - 1 is at most O（x^1/2（loglog x）^1/2）, thus improving earlier results by Pomerance and by Shan.     

Hit-and-run mixes fast

It is shown that the “hit-and-run” algorithm for sampling from a convex body K (introduced by R.L. Smith) mixes in time O ^*(n ² R ²/r ²), where R and r are the radii of the inscribed and circumscribed balls of K. Thus after appropriate preprocessing, hit-and-run produces an approximately uniformly distributed sample point in time O ^*(n ³), which matches the best known bound for other sampling algorithms. We show that the bound is best possible in terms of R,r and n. Received January 26, 1998 / Revised version received October 26, 1998?Published online July 19, 1999     

Efficient generation of random nonsingular matrices

We present an efficient algorithm for generating an n × n nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time M(n) + O(n²), where M(n) is the time needed to multiply two n × n matrices, and the expected number of random bits it uses is n² + 3. (Over other finite fields we use n² + O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random n × n matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have nonzero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant. © 1993 John Wiley & Sons, Inc.     

Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem

The dynamic programming algorithm of [12.] for the bandwidth minimization problem is improved. It is shown that, for all k > 1, BANDWIDTH(k) can be solved in O(n^k) steps and simultaneous O(n^k) space, where n is the number of vertices in the graph, and that each such problem is in NSPACE(log n). The same improved dynamic programming algorithm approach works to show that the MINCUT LINEAR ARRANGEMENT problem restricted to the fixed value k, denoted by MINCUT(k), is solvable in O(n^k) steps and simultaneous O(n^k) space and is in the class NSPACE(log n).     

Codes And Xor Graph Products

What is the maximum possible number, f₃(n), of vectors of length n over {0,1,2} such that the Hamming distance between every two is even? What is the maximum possible number, g³(n), of vectors in {0,1,2}ⁿ such that the Hamming distance between every two is odd? We investigate these questions, and more general ones, by studying Xor powers of graphs, focusing on their independence number and clique number, and by introducing two new parameters of a graph G. Both parameters denote limits of series of either clique numbers or independence numbers of the Xor powers of G (normalized appropriately), and while both limits exist, one of the series grows exponentially as the power tends to infinity, while the other grows linearly. As a special case, it follows that f₃(n) = Θ(2ⁿ) whereas g₃(n)=Θ(n). * Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. † Research partially supported by a Charles Clore Foundation Fellowship.     

Kinetic Spanners in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

We present a new (1+ε)-spanner for sets of n points in ℝ ^d . Our spanner has size O(n/ε ^d−1) and maximum degree O(log  ^d n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming that the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n ²/ε ^d−1), and using a supporting data structure of size O(nlog  ^d n), we can handle events in time O(log  ^d+1 n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in ℝ ^d whose performance does not depend on the spread of the point set.     

On The Correlation Of Binary M-sequences

We obtain the upper bound O(2^14n/15 n^−1/5) on the number of distinct values of all possible correlation functions between M-sequences of order n .     

Ray Shooting Amidst Convex Polygons in 2D

We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log² m log² n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m²+n)log m) andO((m²+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]¹⁺ log² n) time, for any >0.     

Incremental algorithms for minimal length paths

We consider the problem of maintaining on-line a solution to the All Pairs Shortest Paths Problem in a directed graph G = (V,E) where edges may be dynamically inserted or have their cost decreased. For the case of integer edge costs in a given range [1…C], we introduce a new data structure which is able to answer queries concerning the length of the shortest path between any two vertices in constant time and to trace out the shortest path between any two vertices in time linear in the number of edges reported. The total time required to maintain the data structure under a sequence of at most O(n²) edge insertions and at most O(Cn²) edge cost decreases is O(Cn³ log(nC)) in the worst case, where n is the total number of vertices in G. For the case of unit edge costs, the total time required to maintain the data structure under a sequence of at most O(n²) insertions of edges becomes O(n³ logn) in the worst case. The same bounds can be achieved for the problem of maintaining on-line longest paths in directed acyclic graphs. All our algorithms improve previously known algorithms and are only a logarithmic factor away from the best possible bounds.     

Minimum Range Balanced Cuts via Dynamic Subset Sums

We find the balanced cut in a graph that minimizes the maximum difference between edge lengths in timeO(m + n² log n), improving a previousO(m + n^2.5) bound. We use subroutines for solving a dynamic subset sum problem in timeO(l log l log n) per operation in the fully dynamic setting, or in timeO(l log n) per operation in thesemi-onlinesetting in which one can predict a superset of future deletions.     

Finding intersection of rectangles by range search

Three related rectangle intersection problems in k-dimensional space are considered: (1) find the intersections of a rectangle with a given set of rectangles, (2) find the intersecting pairs of rectangles as they are inserted into or deleted from an existing set of rectangles, and (3) find the intersecting pairs of a given set of rectangles. By transforming these problems into range search problems, one need not divide the intersection problem into two subproblems, namely, the edge-intersecting problem and the containment problem, as done by many previous studies. Furthermore, this approach can also solve these subproblems separately, if required. For the first problem the running time is O((log n)^2k−1 + s), where s is the number of intersecting pairs of rectangles. For the second problem the time needed to generate and maintain n rectangles is O(n(log n)^2k) and the time for each query is O((log n)^2k−1 + s). For the third problem the total time is O(n log n + n(log n)^2(k−1) + s) for k ≥ 1.     

Character table of a controlling association scheme defined by the general orthogonal groupO(3,q).

LetN _m (q) be the set of nonisotropic lines in the vector space of dimensionm over a finite field of orderq. In a paper by Bannai, Hao, Song and Wei, it was shown that the association scheme character tableP(Sp(2n, q),N _2n (q)), withn 3 andq odd, is controlled byP(Sp(4,q),N ₄(q)) which is in turn controlled byP(O(3,q),O(3,q)/O ⁺ (2,q)). Our purpose in this paper is to compute the entries in the character tableP(O(3,q), O(3,q)/O ⁺ (2,q)) explicitly, which is left open in that paper.     

Text Indexing and Dictionary Matching with One Error

The indexing problem is where a text is preprocessed and subsequent queries of the form “Find all occurrences of pattern P in the text” are answered in time proportional to the length of the query and the number of occurrences. In the dictionary matching problem a set of patterns is preprocessed and subsequent queries of the form “Find all occurrences of dictionary patterns in text T” are answered in time proportional to the length of the text and the number of occurrences.There exist efficient worst-case solutions for the indexing problem and the dictionary matching problem, but none that find approximate occurrences of the patterns, i.e., where the pattern is within a bound edit (or Hamming) distance from the appropriate text location.In this paper we present a uniform deterministic solution to both the indexing and the general dictionary matching problem with one error. We preprocess the data in time O(n log² n), where n is the text size in the indexing problem and the dictionary size in the dictionary matching problem. Our query time for the indexing problem is O(m log n log log n + tocc), where m is the query string size and tocc is the number of occurrences. Our query time for the dictionary matching problem is O(n log³ d log log d + tocc), where n is the text size and d the dictionary size. The time bounds above apply to both bounded and unbounded alphabets.     

Gossip is synteny: Incomplete gossip and the syntenic distance between genomes

The syntenic distance between two genomes is given by the minimum number of fusions, fissions, and translocations required to transform one into the other, ignoring the order of genes within chromosomes. Computing this distance is NP-hard. In the present work, we give a tight connection between syntenic distance and the incomplete gossip problem, a novel generalization of the classical gossip problem. In this problem, there are n gossipers, each with a unique piece of initial information; they communicate by phone calls in which the two participants exchange all their information. The goal is to minimize the total number of phone calls necessary to inform each gossiper of his set of relevant gossip which he desires to learn. As an application of the connection between syntenic distance and incomplete gossip, we derive an O(2^O(nlogn)) algorithm to exactly compute the syntenic distance between two genomes with at most n chromosomes each. Our algorithm requires O(n²+2^O(dlogd)) time when this distance is d, improving the O(n²+2^O(d2)) running time of the best previous exact algorithm.     

Lower bounds for the condition number of Vandermonde matrices

Summary We derive lower bounds for the -condition number of then×n-Vandermonde matrixV _n(x) in the cases where the node vectorx _T=[x₁, x₂,...,x_n] has positive elements or real elements located symmetrically with respect to the origin. The bounds obtained grow exponentially inn. withO(2ⁿ) andO(2^n/2), respectively. We also compute the optimal spectral condition numbers ofV _n(x) for the two node configurations (including the optimal nodes) and compare them with the bounds obtained.Dedicated to the memory of James H. WilkinsonSupported, in part, by the National Science Foundation under grant CCR-8704404