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.     

Symmetry analysis of the charged squashed Kaluza–Klein black hole metric

In this research article, a complete analysis of symmetries and conservation laws for the charged squashed Kaluza–Klein black hole space‐time in a Riemannian space is discussed. First, a comprehensive group analysis of the underlying space‐time metric using Lie point symmetries is presented, and then the n‐dimensional optimal system of this space‐time metric, for n = 1,…,4, are computed. It is shown that there is no any n‐dimensional optimal system of Lie symmetry subalgebra associated to the system of geodesic for n≥5. Then the point symmetries of the one‐parameter Lie groups of transformations that leave invariant the action integral corresponding to the Lagrangian that means Noether symmetries are found, and then the conservation laws associated to the system of geodesic equations are calculated via Noether's theorem. Copyright © 2015 John Wiley & Sons, Ltd.     

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 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 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 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 the design of chaos-based secure communication systems

This paper discusses the topic of using chaotic models for constructing secure communication systems. It investigates three different case studies that use encryption/decryption functions with varying degrees of complexity and performance. The first case study explores synchronization of identical chaotic systems, which is considered the most crucial step when developing chaos-based secure communication systems. It proposes a fast mechanism for synchronizing the transmitter and the receiver that is based on the drive-response approach. The superiority and causality of this mechanism is demonstrated via contrasting its performance and practical implementation against that of the traditional method of Pecora and Carroll. The second case study explores the use of an improved cryptography method for improving the scrambling of the transmitted signals. The improvement is based on using both the transmitter states and parameters for performing the encryption. The security analysis of this method is analyzed, highlighting its advantages and limitation, via simulating intruder attacks to the communication channel. Finally, the third case study augments a parameter update law to the previous two designs such that the encryption method is more robust. It uses a decoupling technique for which the synchronization process is completely isolated from the parameter identification algorithm. The Lorenz system was used to exemplify all the suggested techniques, and the transmission of both analog and digital signals was explored, while investigating various techniques to optimize the performance of the proposed systems.     

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 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 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.