Proof of the squashed cube conjecture

We prove a conjecture of R. L. Graham and H. O. Pollak to the effect that every connected graph onn vertices has a distance-preserving embedding in “squashed cube” of dimensionn?1. This means that to each vertex of the graph a string ofn?1 symbols from the alphabet {0, 1, *} can be assigned in such a way that the length of the shortest path between two vertices is equal to the Hamming distance between the corresponding strings, with * being regarded as at distance zero from either 1 or 0. Our labelling thus provides an efficient addressing scheme for the loop-switching communications system proposed by J. R. Pierce.     

On the design of reactive systems

The notion of joint actions provides a framework in which the granularity of atomic actions can be refined in the design of concurrent systems. An example of a telephone exchange is elaborated to demonstrate the feasibility of this approach for reactive systems and to illustrate transformations that are justifiable in such a process. Particular problems arise when a refinement would allow new interleavings of semantically relevant events. The meaning of a reactive computation is specified in a way that makes this possible.Dedicated to Peter Naur on the occasion of his 60th birthday     

On the design of lottery games

We describe a model of participation in lottery games designed to address the optimisation of tax revenue in state-sponsored lotteries. The model treats participants dynamically and examines a long-run equilibrium. A novel high frequency approximation is used to turn the problem into a static, state-contingent deterministic programming problem. We demonstrate that the solution of this problem has qualitatively plausible properties and then calibrate the model against the United Kingdom National Lottery (UKNL). The results suggest that the current design of the UKNL may not be maximising tax revenue.     

On the design of voting games

By focusing on the protectionist tendency found in the design of voting games, a thorough analysis is provided for the role of blocking coalitions in a simple game. We characterize those blocking families that univocally determine the game, and show that otherwise at least three games share a given nonempty blocking family, also giving an upper bound for the number of such games. Some examples illustrate the application of these ideas to political science.     

On optimal design of vibrating structures

Optimal design problems of linearly elastic vibrating structural members have been formulated in two ways. One is to minimize the total mass holding the frequency fixed; the other is to maximize the fundamental frequency holding the total mass fixed. Generally, these two formulations are equivalent and lead to the same solution. It is shown in this work that the equivalence is lost when the design variable (the specific stiffness) appears linearly in Rayleigh's quotient and when there is no nonstructural mass. The maximum-frequency formulation then is a normal Lagrange problem, whereas the minimum-mass problem is abnormal. The lack of recognition of this can lead to incorrect conclusions, particularly concerning existence of solutions. It is shown that existence depends directly on the boundary conditions and, when a sandwich beam has a free end, a solution to the maximum-frequency problem does not exist.     

On the optimum design of piston rings

We study a family of control problems that arise in the design of dynamically loaded bearings which have a minimum power loss; in particular, we study the design of piston rings with minimum parasitic power loss.This research was partially supported by NSF Grant No. MCS-77-05624.     

On the multi-component layout design with inertial force

The purpose of this paper is to introduce inertial forces into the proposed integrated layout optimization method designing the multi-component systems. Considering a complex packing system for which several components will be placed in a container of specific shape, the aim of the design procedure is to find the optimal location and orientation of each component, as well as the configuration of the structure that supports and interconnects the components. On the one hand, the Finite-circle Method (FCM) is used to avoid the components overlaps, and also overlaps between components and the design domain boundaries. One the other hand, the optimal material layout of the supporting structure in the design domain is designed by topology optimization. A consistent material interpolation scheme between element stiffness and inertial load is presented to avoid the singularity of localized deformation due to the presence of design dependent inertial loading when the element stiffness and the involved inertial load are weakened with the element material removal. The tested numerical example shows the proposed methods extend the actual concept of topology optimization and are efficient to generate reasonable design patterns.     

On the uniqueness of embedding a residual design

We prove that if a residual $\text{2-(k(k+λ?1)}\text{λ,k,λ)}$ design R has more than one embedding into a symmetric design then k ? λ(λ?1)². If equality holds then R has exactly two embeddings and the corresponding derived design is in both cases λ ? 1 identical copies of the design of points and lines of PG(3, λ ? 1). Using the main proposition from which these results follow we also prove that if a symmetric2-(v,k, λ) design has an axial non-central or central non-axial automorphism then k?λ(λ² ? 2λ + 2).     

On the design of a reflector antenna II

The reflector antenna design problem requires to solve a second boundary value problem for a complicated Monge-Ampére equation, for which the traditional discretization methods fail. In this paper we reduce the problem to that of finding a minimizer or a maximizer of a linear functional subject to a linear constraint. Therefore it becomes an linear optimization problem and algorithms in linear programming apply.Received: 7 July 2003, Accepted: 26 August 2003, Published online: 15 October 2003Mathematics Subject Classification (2000): 78A05, 28A50This work was supported by the Australian Research Council.     

On routing in VLSI design and communication networks

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. First we propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of overall wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming (LP) formulation of both problems and solve the LP relaxations by the fast approximation algorithms for min-max resource-sharing problems in [K. Jansen, H. Zhang, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Math. Programming, to appear, doi:10.1007/s10107-007-0106-8] (which is a generalization of the approximation algorithm proposed by Grigoriadis and Khachiyan [Coordination complexity of parallel price-directive decomposition, Math. Oper. Res. 2 (1996) 321-340]). For the global routing problem, we investigate the particular property of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally, we develop asymptotic approximation algorithms for both problems with ratios depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for the problems of minimizing the total costs (including both the edge and the bend costs) while spanning all given subsets of vertices.     

On uniform controller design for linear switched systems

Traditional method to design a controller for each subsystem of switched systems will increase the complexity of the controller’s realization. Hence this paper gives sufficient conditions for designing a uniform output feedback controller for linear switched systems, and this common controller can be used for all subsystems of the switched systems. Then the output stabilization problem for a particular class of linear switched systems under this uniform output feedback controller has been studied. An illustrative example is given in order to highlight the proposed method.     

On the optimal design of insurance contracts with guarantees

The paper analyzes insurance contracts where the benefits of the insured depend on the performance of an investment strategy and which guarantee a certain interest rate on the contributions made by the insured. The insured has to decide simultaneously on the investment strategy and the guarantee scheme. For a CRRA insured and in a BS economy, the optimal combination is given by a constant mix strategy and the contribution guarantee scheme. In case the insured has a subsistence level, the CPPI strategy turns out to be optimal for arbitrary schemes. We illustrate our results by numerical examples and analyze the utility losses of a CRRA insured due to the use of a suboptimal combination of investment strategy and guarantee scheme.     

On the complexity of the one-terminal network design problem

The one-terminal network design problem considered here is to select a subset of the set of potential edges so as to minimize the sum of construction cost plus expected usage cost with discounting. We distinguish between easy and hard cases of this problem.     

On a class of optimum problems in structural design

The paper deals with the existence of solutions for a class of optimal design problems. The notion of relaxation of an integral functional with respect toG-convergence is introduced, and a general integral representation theorem is obtained for the relaxed functional. For a particular class of functionals, this integral representation is computed explicitly.This work has been realized in a National Research Project in Mathematics supported by the Ministero della Pubblica Istruzione (Italy).     

On the design of networks with unicyclic connected components

This is a summary of my PhD thesis supervised by Walid Ben-Ameur and defended on September 29 2009, at Télécom SudParis. The thesis is written in French language and is available from the author upon request at makhlouf.hadji@it-sudparis.eu.     

On a class of algorithms from experimental design theory

The theory of optimal (approximate) linear regression design has produced several iterative methods to solve a special type of convex minimization problems. The present paper gives a unified and extended theoretical treatment of the methods. The emphasis is on the mathematical structures relevant for the optimization process, rather than on the statistical background of experimental design. So the main body of the paper can be read independently from the experimental design context. Applications are given to a special class of extremum problems arising in statistics. The numerical results obtained indicate that the methods are of practical interest     

On generalizations of network design problems with degree bounds

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems. Our main result is a (1, b + O(log n))-approximation algorithm for the minimum crossing spanning tree (MCST) problem with laminar degree constraints. The laminar MCST problem is a natural generalization of the well-studied bounded-degree MST, and is a special case of general crossing spanning tree. We give an additive Ω(log ^c m) hardness of approximation for general MCST, even in the absence of costs (c > 0 is a fixed constant, and m is the number of degree constraints). This also leads to a multiplicative Ω(log ^c m) hardness of approximation for the robust k-median problem (Anthony et al. in Math Oper Res 35:79–101, 2010), improving over the previously known factor 2 hardness. We then consider the crossing contra-polymatroid intersection problem and obtain a (2, 2b + Δ ? 1)-approximation algorithm, where Δ is the maximum element frequency. This models for example the degree-bounded spanning-set intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2Δ ? 1) approximation algorithm under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.