Bottleneck shortest paths on a partially ordered scale

In bottleneck combinatorial problems, admissible solutions are compared with respect to their maximal elements. In such problems, one may work with an ordinal evaluation scale instead of a numerical scale. We consider here a generalization of this problem in which one only has a partially ordered scale (instead of a completely ordered scale). After the introduction of a mappimax comparison operator between sets of evaluations (which boils down to the classical operator when the order is complete), we establish computational complexity results for this variation of the shortest path problem. Finally, we formulate our problem as an algebraic shortest path problem and suggest adequate algorithms to solve it in the subsequent semiring.Received: June 2002, Revised: March 2003, AMS classification: 05C50, 16Y60, 90B06Olivier Spanjaard: Corresponding author.     

Recent advances in the solution of quadratic assignment problems

 The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe these developments, as well as recent work which is likely to result in the solution of even more difficult instances. Received: February 13, 2003 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words. quadratic assignment problem – discrete optimization – branch and bound Mathematics Subject Classification (1991): 90C27, 90C09, 90C20     

$\Phi $-functions for complex 2D-objects

Within two-dimensional cutting and packing problems with irregular shaped objects, the concept of -functions has been proven to be very helpful for several solution approaches. In order to construct such -functions a previous work, in which so-called primary objects are considered, is continued. Now -functions are constructed for pairs of objects which can be represented as a finite combination (union, intersection, complement) of primary objects which allows the handling of arbitrary shaped objects by appropriate approximations of sufficient accuracy.Received: October 2002, Revised: October 2003, AMS classification: 65K05, 90C26, 90B06All correspondence to: Guntram Scheithauer     

Concentrator location in telecommunications

We survey the main results in the authors PhD Thesis presented in December 2002 at the Université Libre de Bruxelles and supervised by Prof. Martine Labbé. The dissertation is written in English and is available at smg.ulb.ac.be. Several versions of concentrator location problems in telecommunication networks are studied. The thesis presents a list of polyhedral results for these problems and a branch and cut algorithm for the most general problem introduced.Received: October 2003, AMS classification: 90B80, 90B18, 90C57     

Convergence rates for adaptive approximation of ordinary differential equations

Summary This paper constructs an adaptive algorithm for ordinary differential equations and analyzes its asymptotic behavior as the error tolerance parameter tends to zero. An adaptive algorithm, based on the error indicators and successive subdivision of time steps, is proven to stop with the optimal number, N, of steps up to a problem independent factor defined in the algorithm. A version of the algorithm with decreasing tolerance also stops with the total number of steps, including all refinement levels, bounded by . The alternative version with constant tolerance stops with total steps. The global error is bounded by the tolerance parameter asymptotically as the tolerance tends to zero. For a p-th order accurate method the optimal number of adaptive steps is proportional to the p-th root of the quasi-norm of the error density, while the number of uniform steps, with the same error, is proportional to the p-th root of the larger L ¹ -norm of the error density. Mathematics Subject Classification (2000):65Y20, 65L50, 65L70This work has been supported by the EU–TMR project HCL # ERBFMRXCT960033, the EU–TMR grant # ERBFMRX-CT98-0234 (Viscosity Solutions and their Applications), the Swedish Science Foundation, UdelaR and UdeM in Uruguay, the Swedish Network for Applied Mathematics, the Parallel and Scientific Computing Institute (PSCI) and the Swedish National Board for Industrial and Technical Development (NUTEK).     

Infinitesimal study of a factorization of the Prym map

The Prym map factors through a space ={X} of intrinsically polarized varieties, namely , where is a connected étale double cover of a smooth curve C of genus g, consists of the set of even precanonical effective divisors on , and (P,) is the principally polarized Prym variety associated to . X is a connected, reduced local complete intersection of (pure) dimension g-1, and when C is non hyperelliptic X is normal and irreducible. By analogy with the proofs of the classical Torelli theorem for curves by Andreotti and by Andreotti-Mayer and Green, which factor the Jacobi map through a symmetric product of the curve, the present factorization may be used to attack the Torelli problem for Prym varieties. In [19] we have shown that X determines the Prym variety (P,), as the Albanese variety of X, and that X also determines the double cover , at least when C is non hyperelliptic and the codimension of sing in P is at least 5. The next challenge in this approach to the Torelli problem is to analyze the infinitesimal structure of these maps.The goal of the present paper is to show the first map is unramified when C is non hyperelliptic, i.e. that a first order deformation of which induces the trivial first order deformation of X, is already trivial on . (This question was studied for g=3 by H. Yin [23].) We do this as follows for g3. There is a map from to a curve of effective Cartier divisors on X. We prove that if C is non hyperelliptic, this map is an isomorphism from onto a smooth connected component of the Hilbert scheme of X. This is an analogue of Prop. 4.1. b), p.334, in [7], (that the set , is a connected component of Hilb(C^(g-1)) isomorphic to C).Then we deduce that if a first order deformation of induces the trivial deformation of X, the deformation of is isomorphic to the trivial deformation of the curve in Hilb(X). It follows that the original deformation of is trivial. The complementary question of whether every first order deformation of X comes from a first order deformation of , analogous to Thm. 3.6 of [7], is proved in [23] for g=3 and C non hyperelliptic, but remains open for g4 at the time of writing. We will work throughout over the complex numbers, and will generally assume the base curve C is smooth and non hyperelliptic, although some results are true more generally. Dedicated in memory of Fabio BardelliMathematics Subject Classification (2000) 14H40, 14K     

Parallel branch, cut, and price for large-scale discrete optimization

In discrete optimization, most exact solution approaches are based on branch and bound, which is conceptually easy to parallelize in its simplest forms. More sophisticated variants, such as the so-called branch, cut, and price algorithms, are more difficult to parallelize because of the need to share large amounts of knowledge discovered during the search process. In the first part of the paper, we survey the issues involved in parallelizing such algorithms. We then review the implementation of SYMPHONY and COIN/BCP, two existing frameworks for implementing parallel branch, cut, and price. These frameworks have limited scalability, but are effective on small numbers of processors. Finally, we briefly describe our next-generation framework, which improves scalability and further abstracts many of the notions inherent in parallel BCP, making it possible to implement and parallelize more general classes of algorithms. Mathematics Subject Classification (1991):65K05, 68N99, 68W10, 90-04, 90-08, 90C06, 90C09, 90C10, 90C11, 90C57     

Smooth quasiregular mappings with branching

We give an example of a -smooth quasiregular mapping in 3-space with nonempty branch set. Moreover, we show that the branch set of an arbitrary quasiregular mapping in n-space has Hausdorff dimension quantitatively bounded away from n. By using the second result, we establish a new, qualitatively sharp relation between smoothness and branching.     

A new implementation of Yen’s ranking loopless paths algorithm

Yens algorithm is a classical algorithm for ranking the K shortest loopless paths between a pair of nodes in a network. In this paper an implementation of Yens algorithm is presented. Both the original algorithm and this implementation present computational complexity order when considering a worst-case analysis. However, computational experiments are reported, which allow to conclude that in practice this new implementation outperforms two other, Perkos implementation and a straightforward one.AMS classification: 05C38, 05C85, 68R10, 90C27.Ernesto Q.V. Martins: Sadly, the author passed away in November, 2000.Marta M.B. Pascoal: The research of Marta Pascoal was developed within CISUC and partially supported by the Portuguese Ministry of Science and Technology (MCT), under PRAXIS XXI Project of JNICT.     

A new approach to Sobolev spaces and connections to $\mathbf\Gamma$-convergence

This is a follow-up of a paper of Bourgain, Brezis and Mironescu [2]. We study how the existence of the limit

The Dirichlet energy of mappings from ${\bf B^3}$ into a manifold: density results and gap phenomenon

Weak limits of graphs of smooth maps with equibounded Dirichlet integral give rise to elements of the space . We assume that the 2-homology group of has no torsion and that the Hurewicz homomorphism is injective. Then, in dimension n = 3, we prove that every element T in , which has no singular vertical part, can be approximated weakly in the sense of currents by a sequence of smooth graphs {u _k } with Dirichlet energies converging to the energy of T. We also show that the injectivity hypothesis on the Hurewicz map cannot be removed. We finally show that a similar topological obstruction on the target manifold holds for the approximation problem of the area functional.Received: 9 May 2003, Accepted: 5 June 2003, Published online: 25 February 2004     

Multiple solutions of constant sign for nonlinear nonsmooth eigenvalue problems near resonance

In this paper we study a class of nonlinear elliptic eigenvalue problems driven by the p-Laplacian and having a nonsmooth locally Lipschitz potential. We show that as the parameter approaches (= the principal eigenvalue of ) from the right, the problem has three nontrivial solutions of constant sign. Our approach is variational based on the nonsmooth critical point theory for locally Lipschitz functions. In the process of the proof we also establish a generalization of a recent result of Brezis and Nirenberg for C₀¹ versus W₀^1,p minimizers of a locally Lipschitz functional. In addition we prove a result of independent interest on the existence of an additional critical point in the presence of a local minimizer of constant sign. Finally by restricting further the asymptotic behavior of the potential at infinity, we show that for all the problem has two solutions one strictly positive and the other strictly negative.Received: 7 January 2003, Accepted: 12 May 2003, Published online: 4 September 2003Mathematics Subject Classification (2000): 35J20, 35J85, 35R70     

A sharp attainment result for nonconvex variational problems

We consider the problem of minimizing autonomous, multiple integrals like

Online competitive algorithms for maximizing weighted throughput of unit jobs

We study an online unit-job scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unit-job scheduling, as well as some lower bounds on the competitive ratios.We first give a randomized algorithm RMix with competitive ratio of e/(e−1)≈1.582. This is the first algorithm for this problem with competitive ratio smaller than 2.Then we consider s-bounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm Edf_α, whose competitive ratio on s-bounded instances is 2−2/s+o(1/s). For 3-bounded instances its ratio is ≈1.618, matching the known lower bound.In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform instances, if the span s is unbounded. For s=2, our proof gives a lower bound of . Also, in the 2-uniform case, we prove a lower bound of for deterministic memoryless algorithms, matching a known upper bound.Finally, we investigate the multiprocessor case and give a -competitive algorithm for m processors. We also show improved lower bounds for the general and s-uniform cases.     

A problem of Kusner on equilateral sets

R. B. Kusner [R. Guy, Amer. Math. Monthly 90, 196-199 (1983)] asked whether a set of vectors in such that the distance between any pair is 1, has cardinality at most d + 1. We show that this is true for p = 4 and any , and false for all 1<p<2 with d sufficiently large, depending on p. More generally we show that the maximum cardinality is at most if p is an even integer, and at least if 1<p<2, where depends on p. Received: 5 May 2003     

A <Emphasis Type="Italic">C</Emphasis><Superscript>∞</Superscript>-Regularity Theorem for Nondegenerate CR Mappings

We prove the following regularity result: If , are smooth generic submanifolds and M is minimal, then every C^k-CR-map from M into M which is k-nondegenerate is smooth. As an application, every CR diffeomorphism of k-nondegenerate minimal submanifolds in of class C^k is smooth.     

Approximating <Emphasis Type="Italic">J</Emphasis>-holomorphic curves by holomorphic ones

Given an almost complex structure J in a cylinder of (p > 1) together with a compatible symplectic form and given an arbitrary J-holomorphic curve without boundary in that cylinder, we construct an holomorphic perturbation of , for the canonical complex structure J ₀ of , such that the distance between these two curves in W ^1,2 and norms, in a sub-cylinder, are controled by quantities depending on J, and by the area of only. These estimates depend neither on the topology nor on the conformal class of . They are key tools in the recent proof of the regularity of 1-1 integral currents in [RT].Received: 2 October 2003, Accepted: 18 November 2003, Published online: 25 February 2004     

A decomposition approach for a very large scale optimal diversity management problem

This paper focuses on the solution of the optimal diversity management problem formulated as a p-Median problem. The problem is solved for very large scale real instances arising in the car industry and defined on a graph with several tens of thousands of nodes and with several millions of arcs. The particularity is that the graph can consist of several non connected components. This property is used to decompose the problem into a series of p-Median subproblems of a smaller dimension. We use a greedy heuristic and a Lagrangian heuristic for each subproblem. The solution of the whole problem is obtained by solving a suitable assignment problem using a Branch-and-Bound algorithm.Received: June 2004 / Revised version: December 2004MSC classification: 49M29, 90C06, 90C27, 90C60All correspondence to: Antonio SforzaIgor Vasilev: Support for this author was provided by NATO grant CBP.NR.RIG.911258.     

Products of characters and finite <Emphasis Type="Italic">p</Emphasis>-groups II

Let p be a prime number. Let G be a finite p-group and . Denote by the complex conjugate of . Assume that . We show that the number of distinct irreducible constituents of the product is at least . Received: 17 March 2003     

Computing Minimum-Volume Enclosing Axis-Aligned Ellipsoids

Given a set of points and ε>0, we propose and analyze an algorithm for the problem of computing a (1+ε)-approximation to the minimum-volume axis-aligned ellipsoid enclosing . We establish that our algorithm is polynomial for fixed ε. In addition, the algorithm returns a small core set , whose size is independent of the number of points m, with the property that the minimum-volume axis-aligned ellipsoid enclosing is a good approximation of the minimum-volume axis-aligned ellipsoid enclosing . Our computational results indicate that the algorithm exhibits significantly better performance than the theoretical worst-case complexity estimate. This work was supported in part by the National Science Foundation through CAREER Grants CCF-0643593 and DMI-0237415.