Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane

An intersection graph of rectangles in the (x, y)-plane with sides parallel to the axes is obtained by representing each rectangle by a vertex and connecting two vertices by an edge if and only if the corresponding rectangles intersect. This paper describes algorithms for two problems on intersection graphs of rectangles in the plane. One is an O(n log n) algorithm for finding the connected components of an intersection graph of n rectangles. This algorithm is optimal to within a constant factor. The other is an O(n log n) algorithm for finding a maximum clique of such a graph. It seems interesting that the maximum clique problem is polynomially solvable, because other related problems, such as the maximum stable set problem and the minimum clique cover problem, are known to be NP-complete for intersection graphs of rectangles. Furthermore, we briefly show that the k-colorability problem on intersection graphs of rectangles is NP-complete.     

Asymptotic enumeration of two-dimensional posets

In this paper we show that the number of pairwise nonisomorphic two-dimensional posets with n elements is asymptotically equivalent to 1/2n!. This estimate is based on a characterization, in terms of structural decomposition, of two-dimensional posets having a unique representation as the intersection of two linear extensions.     

Matrix elements of vertex operators of the deformed W A n -algebra and the Harish-Chandra solutions to Macdonald's difference equations

In this paper we prove that certain matrix elements of vertex operators of the deformed W A _n -algebra satisfy Macdonald's difference equations and form a natural (n + 1)!-dimensional space of solutions. These solutions are the analogues of the Harish-Chandra solutions of the radial parts of the Laplace-Casimir operators on noncompact Riemannian symmetric spaces G/K with prescribed asymptotic behavior. We obtain formulas for analytic continuation of our Harish-Chandra type solutions as a consequence of braiding properties (obtained earlier by Y. Asai, M. Jimbo, T. Miwa, and Y. Pugay) of certain vertex operators of the deformed W A _n -algebra.     

AVLSI partition algorithm

A VLSI sorter of sizeO(n) can sortn elements in linear time when the input and output time are taken into account. If the input contains more thann elements, some prepocessing has to be performed. A VLSI partition algorithm that provides a solution to this problem is presented. The algorithm partitions the input data into two smaller parts as the quicksort algorithm does. That is, the elements of the first part will be smaller than the elements of the second part. The partition is repeated until the parts are small enough to fit in the sorter. It is shown that the average number of times each element must go through the partitioner isO(logk) for a data file of sizekn wheren is the size of the sorter. In the worst case where the partitioner fails to divide the input evenly, the elements must goO(k) times through the partitioner like in the quicksort algorithm. The partitioner can also be used, with simple modifications, as a sorter, a stack, a queue, or as a priority queue. Other advantages of the VLSI algorithm are also discussed.     

Functional optimization by variable-basis approximation schemes

This is a summary of the author’s PhD thesis, supervised by Marcello Sanguineti and defended on April 2, 2009 at Università degli Studi di Genova. The thesis is written in English and a copy is available from the author upon request. Functional optimization problems arising in Operations Research are investigated. In such problems, a cost functional Φ has to be minimized over an admissible set S of d-variable functions. As, in general, closed-form solutions cannot be derived, suboptimal solutions are searched for, having the form of variable-basis functions, i.e., elements of the set span _n   G of linear combinations of at most n elements from a set G of computational units. Upper bounds on inf_{f ? S ?spann G}F(f)-inf_{f ? S}F(f){\inf_{f \in S \cap {\rm span}_n\, G}\Phi(f)-\inf_{f \in S}\Phi(f)} are obtained. Conditions are derived, under which the estimates do not exhibit the so-called “curse of dimensionality” in the number n of computational units, when the number d of variables grows. The problems considered include dynamic optimization, team optimization, and supervised learning from data.     

Approximation Schemes for Functional Optimization Problems

Approximation schemes for functional optimization problems with admissible solutions dependent on a large number d of variables are investigated. Suboptimal solutions are considered, expressed as linear combinations of n-tuples from a basis set of simple computational units with adjustable parameters. Different choices of basis sets are compared, which allow one to obtain suboptimal solutions using a number n of basis functions that does not grow “fast” with the number d of variables in the admissible decision functions for a fixed desired accuracy. In these cases, one mitigates the “curse of dimensionality,” which often makes unfeasible traditional linear approximation techniques for functional optimization problems, when admissible solutions depend on a large number d of variables. Marcello Sanguineti was partially supported by a PRIN grant from the Italian Ministry for University and Research (project “Models and Algorithms for Robust Network Optimization”).     

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.     

Symmetry of solutions for quasimonotone second-order elliptic systems in ordered Banach spaces

We consider symmetry properties of solutions to nonlinear elliptic boundary value problems defined on bounded symmetric domains of \mathbb Rⁿ{\mathbb R^n} . The solutions take values in ordered Banach spaces E, e.g. E=\mathbb R^N{E=\mathbb R^N} ordered by a suitable cone. The nonlinearity is supposed to be quasimonotone increasing. By considering cones that are different from the standard cone of componentwise nonnegative elements we can prove symmetry of solutions to nonlinear elliptic systems which are not covered by previous results. We use the method of moving planes suitably adapted to cover the case of solutions of nonlinear elliptic problems with values in ordered Banach spaces.     

Asymptotic properties of combinatorial optimization problems in <Emphasis Type="Italic">p</Emphasis>-adic space

In this article we consider two well known combinatorial optimization problems (travel-ling salesman and minimum spanning tree), when n points are randomly distributed in a unit p-adic ball of dimension d. We investigate an asymptotic behavior of their solutions at large number of n. It was earlier found that the average lengths of the optimal solutions in both problems are of order n ^1−1/d . Here we show that standard deviations of the optimal lengths are of order n ^1/2−1/d if d > 1, and prove that large number laws are valid only for special subsequences of n.     

A dual approach to detect polyhedral intersections in arbitrary dimensions

This paper presents a dual approach to detect intersections of hyperplanes and convex polyhedra in arbitrary dimensions. Ind dimensions, the time complexities of the dual algorithms areO(2 ^d logn) for the hyperplane-polyhedron intersection problem, andO((2d) ^d–1 log ^d–1 n) for the polyhedron- polyhedron intersection problem. These results are the first of their kind ford > 3. In two dimensions, these time bounds are achieved with linear space and preprocessing. In three dimensions, the hyperplane-polyhedron intersection problem is also solved with linear space and preprocessing; quadratic space and preprocessing, however, is required for the polyhedron-polyhedron intersection problem. For generald, the dual algorithms require space and preprocessing. All of these results readily extend to unbounded polyhedra.This is an extended and revised version of a paper presented at the 25th Annual Allerton Conference on Communication, Control, and Computing (October 1987). Our work was sponsored by the U.S. Army Research Office (research contract DAAG29-85-0223) and, in the case of the first author, by graduate fellowships from the IBM corporation and the German National Scholarship Foundation.     

An optimal algorithm for generating equivalence relations on a linear array of processors

We describe a cost-optimal parallel algorithm for enumerating all partitions (equivalence relations) of the set {1, ...,n}, in lexicographic order. The algorithm is designed to be executed on a linear array of processors. It usesn processors, each having constant size memory and each being responsible for producing one element of a given set partition. Set partitions are generated with constant delay leading to anO(B _n) time solution, whereB _n is the total number of set partitions. The same method can be generalized to enumerate some other combinatorial objects such as variations. The algorithm can be made adaptive, i.e. to run on any prespecified number of processors. To illustrate the model of parallel computation, a simple case of enumerating subsets of the set {1, ...,n}, having at mostm (n) elements is also described.The research is partialy supported by NSERC operating grant OGPIN 007.     

Optimizing a constrained convex polygonal annulus

In this paper we give solutions to several constrained polygon annulus placement problems for offset and scaled polygons, providing new efficient primitive operations for computational metrology and dimensional tolerancing. Given a convex polygon P and a planar point set S, the goal is to find the thinnest annulus region of P containing S. Depending on the application, there are several ways this problem can be constrained. In the variants that we address the size of the polygon defining the inner (respectively, outer) boundary of the annulus is fixed, and the annulus is minimized by minimizing (respectively, maximizing) the outer (respectively, inner) boundary. We also provide solutions to a related known problem: finding the smallest homothetic copy of a polygon containing a set of points. For all of these problems, we solve for the cases where smallest and largest are defined by either the offsetting or scaling of a polygon. We also provide some experimental results from implementations of several competing approaches to a primitive operation important to all the above variants: finding the intersection of n copies of a convex polygon.     

Strong Version of the Basic Deciding Algorithm for the Existential Theory of Real Fields

Let U be a real algebraic variety in the n-dimensional affine space that is a set of all zeros of a family of polynomials of degree less than d. In the case where U is bounded (this is the main case), an algorithm of polynomial complexity is described for constructing a subset of U with the number of elements bounded from above by dⁿ that has the following property: for every s, this set has a nonempty intersection with every d-dimensional cycle with coefficients from s of the closure of the set of smooth points of dimension s of U. Bibliography: 16 titles.     

Massively parallel tabu search for the quadratic assignment problem

A new heuristic algorithm to perform tabu search on the Quadratic Assignment Problem (QAP) is developed. A massively parallel implementation of the algorithm on the Connection Machine CM-2 is provided. The implementation usesn ² processors, wheren is the size of the problem. The elements of the algorithm, calledPar_tabu, include dynamically changing tabu list sizes, aspiration criterion and long term memory. A new intensification strategy based on intermediate term memory is proposed and shown to be promising especially while solving large QAPs. The combination of all these elements gives a very efficient heuristic for the QAP: the best known or improved solutions are obtained in a significantly smaller number of iterations than in other comparative studies. Combined with the implementation on CM-2, this approach provides suboptimal solutions to QAPs of bigger dimensions in reasonable time.     

Preventing redundant solutions in partial enumeration algorithms

Many algorithms for discrete problems use a variation of the tree-search enumeration technique as a basis for the algorithm. If a solution is the assignment of an attribute from a set ofm attributes to every variable in a set ofn variables, then redundant solutions can be generated if either the attributes or the variables contain some indistinguishable elements. A series of necessary and sufficient techniques are developed to eliminate the production of redundant solutions during enumeration. These techniques can be used to form the foundation of any partial enumeration algorithm where redundant solutions can be produced.     

Circuits and Cocircuits in Regular Matroids

A classical result of Dirac's shows that, for any two edges and any n−2 vertices in a simple n-connected graph, there is a cycle that contains both edges and all n−2 of the vertices. Oxley has asked whether, for any two elements and any n−2 cocircuits in an n-connected matroid, there is a circuit that contains both elements and that has a non-empty intersection with all n−2 of the cocircuits. By using Seymour's decomposition theorem and results of Oxley and Denley and Wu, we prove that a slightly stronger property holds for regular matroids.     

Average-case results on heapsort

A new algorithm for rearranging a heap is presented and analysed in the average case. The average case upper bound for deleting the maximum element of a random heap is improved, and is shown to be less than [logn]+0.299+M(n) comparisons, *) whereM(n) is between 0 and 1. It is also shown that a heap can be constructed using 1.650n+O(logn) comparisons with this algorithm, the best result for any algorithm which does not use any extra space. The expected time to sortn elements is argued to be less thann logn+0.670n+O(logn), while simulation result points at an average case ofn log n+0.4n which will make it the fastest in-place sorting algorithm. The same technique is used to show that the average number of comparisons when deleting the maximum element of a heap using Williams' algorithm for rearrangement is 2([logn]–1.299+L(n)) whereL(n) also is between 0 and 1, and the average cost for Floyd-Williams Heapsort is at least 2nlogn–3.27n, counting only comparisons. An analysis of the number of interchanges when deleting the maximum element of a random heap, which is the same for both algorithms, is also presented.     

Extremal problems for numerical series

In this paper, we consider extremal problems for numerical positive series. The terms of these series are pairwise products of the elements of two sequences, one of which is fixed and the other varies within a given set of sequences. We obtain exact solutions for a number of such problems. As one of the possible applications of the results obtained, we find solutions of some extremal problems related to best n-term approximations of periodic functions.     

Set systems without a 3-simplex

A 3-simplex is a collection of four sets A₁,…,A₄ with empty intersection such that any three of them have nonempty intersection. We show that the maximum size of a set system on n elements without a 3-simplex is for all n≥1, with equality only achieved by the family of sets containing a given element or of size at most 2. This extends a result of Keevash and Mubayi, who showed the conclusion for n sufficiently large.