A 54 algorithm for two-dimensional packing

This paper proposes a new algorithm for a two-dimensional packing problem first studied by Baker, Coffman, and Rivest (SIAM J. Comput.9, No. 4(1980), 846–855). In their model, a finite list of rectangles is to be packed into a rectangular bin of finite width but infinite height. The model has applications to certain scheduling and stock-cutting problems. Since the problem of finding an optimal packing is NP-hard, previous work has been directed at finding polynomial approximation algorithms for the problem, i.e., algorithms which come within a constant times the height used by an optimal packing. For the algorithm proposed in this paper, the ratio of the height obtained by the algorithm and the height used by an optimal packing is asymptotically bounded by $\text{5}\text{4}$. This bound is an improvement over the bound of $\text{4}\text{3}$ achieved by the best previous algorithm.     

Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

We develop a Las Vegas-randomized algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse polynomial interpolation algorithm for the complex field developed by M. Ben-Or and P. Tiwari (1988, in “Proceedings of the 20th ACM Symposium on the Theory of Computing,” pp. 301–309, Assoc. Comput. Mach., New York) to the case of finite fields. It improves upon a previous result by D. Y. Grigoriev, M. Karpinski, and M. F. Singer (1990, SIAM J. Comput.19, 1059–1063) and is by far the most time efficient algorithm (time and processor efficient parallel algorithm) for the problem when the finite field is large. As applications, we obtain Monte Carlo-randomized parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves upon that of the previously known algorithms for the respective problems.     

Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet Routing

We propose asymptotically optimal algorithms for the job shop scheduling and packet routing problems. We propose a fluid relaxation for the job shop scheduling problem in which we replace discrete jobs with the flow of a continuous fluid. We compute an optimal solution of the fluid relaxation in closed form, obtain a lower bound C_max to the job shop scheduling problem, and construct a feasible schedule from the fluid relaxation with objective value at most where the constant in the O( · ) notation is independent of the number of jobs, but it depends on the processing time of the jobs, thus producing an asymptotically optimal schedule as the total number of jobs tends to infinity. If the initially present jobs increase proportionally, then our algorithm produces a schedule with value at most C_max + O(1). For the packet routing problem with fixed paths the previous algorithm applies directly. For the general packet routing problem we propose a linear programming relaxation that provides a lower bound C_max and an asymptotically optimal algorithm that uses the optimal solution of the relaxation with objective value at most Unlike asymptotically optimal algorithms that rely on probabilistic assumptions, our proposed algorithms make no probabilistic assumptions and they are asymptotically optimal for all instances with a large number of jobs (packets). In computational experiments our algorithms produce schedules which are within 1% of optimality even for moderately sized problems.     

New branch-and-bound algorithms for k-cardinality tree problems

Given an undirected graph, the k-cardinality tree problem (KCTP) is the problem of finding a subtree with exactly k edges whose sum of weights is minimum. In this paper we present a lower bound for KCTP based on the work by Kataoka et al. [Kataoka, S., N. Araki and T. Yamada, Upper and lower bounding procedures for the minimum rooted k-subtree problem, European Journal of Operational Research, 122 (2000), 561–569]. This new bound is the basis for the development of a branch-and-bound algorithm for the problem. Experiments carried out on instances from KCTLib revealed that the new exact algorithm largely outperforms the previous approach.     

The average-case analysis of some on-line algorithms for bin packing

In this paper we give tighter bounds than were previously known for the performance of the bin packing algorithms Best Fit and First Fit when the inputs are uniformly distributed on [0, 1]. We also give a general lower bound for the performance of any on-line bin packing algorithm on this distribution. We prove these results by analyzing optimal matchings on points randomly distributed in a unit square. We give a new lower bound for the up-right matching problem. A preliminary version of this paper appeared inProc. 25th IEEE Symposium on Foundations of Computer Science, 193–200. This research was done while the author was at the Massachusetts Institute of Technology Dept. of Mathematics and was supported by a NSF Graduate Fellowship and by Air Force grant OSR-82-0326.     

Fast algorithms for fragmentable items bin packing

Bin packing with fragmentable items is a variant of the classic bin packing problem where items may be cut into smaller fragments. The objective is to minimize the number of item fragments, or equivalently, to minimize the number of cuts, for a given number of bins. Models based on packing fragmentable items are useful for representing finite shared resources. In this article, we present improvements to approximation and metaheuristic algorithms to obtain an optimality-preserving optimization algorithm with polynomial complexity, worst-case performance guarantees and parametrizable running time. We also present a new family of fast lower bounds and prove their worst-case performance ratios. We evaluate the performance and quality of the algorithm and the best lower bound through a series of computational experiments on representative problem instances. For the studied problem sets, one consisting of 180 problems with up to 20 items and another consisting of 450 problems with up to 1024 items, the lower bound performs no worse than 5 / 6. For the first problem set, the algorithm found an optimal solution in 92 % of all 1800 runs. For the second problem set, the algorithm found an optimal solution in 99 % of all 4500 runs. No run lasted longer than 220 ms.     

Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1.We present a complete solution to this problem: For every bin size b1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.     

An approximation algorithm for sorting by reversals and transpositions

Genome rearrangement algorithms are powerful tools to analyze gene orders in molecular evolution. Analysis of genomes evolving by reversals and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, the problem of finding a shortest sequence of reversals and transpositions that sorts one genome into the other. In this paper we present a 2k-approximation algorithm for sorting by reversals and transpositions for unsigned permutations where k is the approximation ratio of the algorithm used for cycle decomposition. For the best known value of k our approximation ratio becomes 2.8386+δ for any δ>0. We also derive a lower bound on reversal and transposition distance of an unsigned permutation.     

New upper bounds for online strip packing

In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into one or more strips of width 1 and infinite height so as to minimize the required height of the packing. By analyzing a two-phase shelf algorithm, we derive a new upper bound 6.4786 on the competitive ratio for online one strip packing. This result improves the best known upper bound of 6.6623. We also extend this algorithm to online multiple strips packing and present some numeric upper bounds on their competitive ratios which are better than the previous bounds.     

Local search algorithms for the rectangle packing problem with general spatial costs

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms. Key words.rectangle packing – sequence pair – general spatial cost – dynamic programming – metaheuristicsMathematics Subject Classification (1991):20E28, 20G40, 20C20     

Faster algorithms for computing longest common increasing subsequences

We present algorithms for finding a longest common increasing subsequence of two or more input sequences. For two sequences of lengths n and m, where m?n, we present an algorithm with an output-dependent expected running time of and O(m) space, where ? is the length of an LCIS, σ is the size of the alphabet, and Sort is the time to sort each input sequence. For k?3 length-n sequences we present an algorithm which improves the previous best bound by more than a factor k for many inputs. In both cases, our algorithms are conceptually quite simple but rely on existing sophisticated data structures. Finally, we introduce the problem of longest common weakly-increasing (or non-decreasing) subsequences (LCWIS), for which we present an -time algorithm for the 3-letter alphabet case. For the extensively studied longest common subsequence problem, comparable speedups have not been achieved for small alphabets.     

On symmetric algorithms for bilinear forms over finite fields

In this paper we study the computation of symmetric systems of bilinear forms over finite fields via symmetric bilinear algorithms. We show that, in general, the symmetric complexity of a system is upper bounded by a constant multiple of the bilinear complexity; we characterize symmetric algorithms in terms of the cosets of a specific cyclic code, and we show that the problem of finding an optimal symmetric algorithm is equivalent to the maximum-likelihood decoding problem for this code.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

The two-dimensional cutting stock problem revisited

In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k=2 stages cannot guarantee any bounded asymptotic performance ratio. k=3 stages lead to asymptotic performance ratios arbitrarily close to 1.69103; this bound is tight. Finally, k=4 stages yield asymptotic performance ratios arbitrarily close to 1.Steve Seiden died in a tragic accident on June 11, 2002. This paper resulted from a number of email discussions between the authors in spring 2002.     

Randomized Algorithms over Finite Fields for the Exact Parity Base Problem

We present three randomized pseudo-polynomial algorithms for the problem of finding a base of specified value in a weighted represented matroid subject to parity conditions. These algorithms, the first two being an improved version of those presented by P. M. Camerini et al. (1992, J. Algorithms13, 258–273) use fast arithmetic working over a finite field chosen at random among a set of appropriate fields. We show that the choice of a best algorithm among those presented depends on a conjecture related to the best value of the so-called Linnik constant concerning the distribution of prime numbers in arithmetic progressions. This conjecture, which we call the C-conjecture, is a strengthened version of a conjecture formulated in 1934 by S. Chowla. If the C-conjecture is true, the choice of a best algorithm is simple, since the last algorithm exhibits the best performance, either when the performance is measured in arithmetic operations, or when it is measured in bit operations and mild assumptions hold. If the C-conjecture is false we are still able to identify a best algorithm, but in this case the choice is between the first two algorithms and depends on the asymptotic growth of m with respect to those of U and n, where 2n, 2m, U are the rank, the number of elements, and the maximum weight assigned to the elements of the matroid, respectively.     

Triangles in space or building (and analyzing) castles in the air

We show that the total combinatorial complexity of all non-convex cells in an arrangement ofn (possibly intersecting) triangles in 3-space isO(n ^7/3 logn) and that this bound is almost tight in the worst case. Our bound significantly improves a previous nearly cubic bound of Pach and Sharir. We also present a (nearly) worst-case optimal randomized algorithm for calculating a single cell of the arrangement and an alternative less efficient, but still subcubic algorithm for calculating all non-convex cells, analyze some special cases of the problem where improved bounds (and faster algorithms) can be obtained, and describe applications of our results to translational motion planning for polyhedra in 3-space.Work on this paper by the first author has been supported by an AT&T Bell Laboratories PhD Scholarship. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, the IBM Corporation, and by a research grant from the NCRD — the Israeli National Council for Research and Development. A preliminary version of this paper has appeared inProc. 4th ACM Symp. on Computational Geometry, Urbana, Illinois, 1988.     

All-Pairs Small-Stretch Paths

Let G = (V, E) be a weighted undirected graph. A path between u, v  V is said to be of stretch t if its length is at most t times the distance between u and v in the graph. We consider the problem of finding small-stretch paths between all pairs of vertices in the graph G.It is easy to see that finding paths of stretch less than 2 between all pairs of vertices in an undirected graph with n vertices is at least as hard as the Boolean multiplication of two n × n matrices. We describe three algorithms for finding small-stretch paths between all pairs of vertices in a weighted graph with n vertices and m edges. The first algorithm, STRETCH₂, runs in Õ(n^3/2m^1/2) time and finds stretch 2 paths. The second algorithm, STRETCH_7/3, runs in Õ(n^7/3) time and finds stretch 7/3 paths. Finally, the third algorithm, STRETCH₃, runs in Õ(n²) and finds stretch 3 paths.Our algorithms are simpler, more efficient and more accurate than the previously best algorithms for finding small-stretch paths. Unlike all previous algorithms, our algorithms are not based on the construction of sparse spanners or sparse neighborhood covers.     

The discrete plateau problem: Convergence results

We solve the problem of finding and justifying an optimal fully discrete finite element procedure for approximating minimal, including unstable, surfaces. In a previous paper we introduced the general framework and some preliminary estimates, developed the algorithm and give the numerical results. In this paper we prove the convergence estimate.

     

Algorithms for Leader Election by Cellular Automata

We present two cellular algorithms, in O(n) and respectively in O(w²), for the leader election problem on finite connected rings F and respectively finite connected subsets of ^d, of eccentricity w, for any fixed d. The problem consists of finding an algorithm such that when setting the elements of F to a special state, and all the others to a state #, the cellular automaton iterates a finite number of steps and sets only one precise element of F to a special state called leader state, and all the others to a different state. We describe the algorithms in detail, give their proofs and complexities, and discuss the possible extensions.     

On non-permutation solutions to some two machine flow shop scheduling problems

In this paper, we study two versions of the two machine flow shop scheduling problem, where schedule length is to be minimized. First, we consider the two machine flow shop with setup, processing, and removal times separated. It is shown that an optimal solution need not be a permutation schedule, and that the problem isNP-hard in the strong sense, which contradicts some known results. The tight worst-case bound for an optimal permutation solution in proportion to a global optimal solution is shown to be 3/2. An O(n) approximation algorithm with this bound is presented. Secondly, we consider the two machine flow shop with finite storage capacity. Again, it is shown that there may not exist an optimal solution that is a permutation schedule, and that the problem isNP-hard in the strong sense.