Towards the computation of minimum drag profiles in viscous laminar flow

A numerical method is given for the solution of certain optimum design problems of fluid mechanics. The profile of given area and smallest drag in a uniform laminar flow is computed. This profile is long and slim, its front end is shaped like a wedge of angle 90° and its rear end is shaped like a cusp. Owing to the numerical complexity of the problem the precision of the results is average (around 5%). However, this work is a good illustration of the theoretical method exposed previously and it shows how good precision can be obtained if one is prepared to pay for it. A numerical solution of the adjoint system of the stationary Navier-Stokes equation is also given; this equation will play an important role in optimum design in fluid mechanics.     

Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies

This paper considers a Markovian model for the optimal dynamic routing of homogeneous traffic to parallel heterogeneous queues, each having its own finite input buffer and server pool, where buffer and server-pool sizes, as well as service rates, may differ across queues. The main goal is to identify a heuristic index-based routing policy with low complexity that consistently attains a nearly minimum average loss rate (or, equivalently, maximum throughput rate). A second goal is to compare alternative policies, with respect to computational demands and empirical performance. A novel routing policy that can be efficiently computed is developed based on a second-order extension to Whittle’s restless bandit (RB) index, since the latter is constant for this model. New results are also given for the more computationally demanding index policy obtained via policy improvement (PI), including that it reduces to shortest queue routing under symmetric buffer and server-pool sizes. A numerical study shows that the proposed RB index policy is nearly optimal across the instances considered, and substantially outperforms several previously proposed index policies.     

Linear maps preserving the minimum and reduced minimum moduli

We describe linear maps from a C^∗-algebra onto another one preserving different spectral quantities such as the minimum modulus, the surjectivity modulus, and the reduced minimum modulus.     

Uniform shallow arches of minimum weight and minimum maximum deflection

The present paper serves several purposes. Besides presenting closed-form solutions to the problems in the title, it serves to illustrate the deduction of existence and nonexistence of solutions in this context, to point out some of the more or less known inadequacies of these design criteria and, finally, to provide the basis for a comparison with the natural structural shapes of shallow arches presented in another reference. The minimum weight and minimum maximum deflection criteria both yield, as one possible optimal design, an arch on the verge of failure. This is consequence of the fully-stressed design aspects of these criteria which, in this case, correspond to the maximum possible axial load. However, meaningful results are obtained for a prescribed axial load in the minimum weight problem and for a given weight in the minimum of the maximum deflection problem.     

Finding minimum areak-gons

Given a setP ofn points in the plane and a numberk, we want to find a polygon with vertices inP of minimum area that satisfies one of the following properties: (1) is a convexk-gon, (2) is an empty convexk-gon, or (3) is the convex hull of exactlyk points ofP. We give algorithms for solving each of these three problems in timeO(kn ³). The space complexity isO(n) fork=4 andO(kn ²) fork5. The algorithms are based on a dynamic programming approach. We generalize this approach to polygons with minimum perimeter, polygons with maximum perimeter or area, polygons containing the maximum or minimum number of points, polygons with minimum weight (for some weights added to vertices), etc., in similar time bounds.This paper includes work done while David Eppstein was at Columbia University, Department of Computer Science, and while Günter Rote and Gerhard Woeginger were at the Freie Universität Berlin, Fachbereich Mathematik, Institut für Informatik. Research was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).     

Degree-bounded minimum spanning trees

Given n points in the Euclidean plane, the degree-δ minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most δ. The problem is NP-hard for 2≤δ≤3, while the NP-hardness of the problem is open for δ=4. The problem is polynomial-time solvable when δ=5. By presenting an improved approximation analysis for Chan’s degree-4 MST algorithm [T. Chan, Euclidean bounded-degree spanning tree ratios, Discrete & Computational Geometry 32 (2004) 177-194], we show that, for any arbitrary collection of points in the Euclidean plane, there always exists a degree-4 spanning tree of weight at most times the weight of an MST.     

Most balanced minimum cuts

We consider the problem of finding most balanced cuts among minimum st-edge cuts and minimum st-vertex cuts, for given vertices s and t, according to different balance criteria. For edge cuts we seek to maximize . For vertex cuts C of G we consider the objectives of (i) maximizing min{|S|,|T|}, where {S,T} is a partition of V(G)?C with s∈S, t∈T and [S,T]=0?, (ii) minimizing the order of the largest component of G−C, and (iii) maximizing the order of the smallest component of G−C.All of these problems are NP-hard. We give a PTAS for the edge cut variant and for (i). These results also hold for directed graphs. We give a 2-approximation for (ii), and show that no non-trivial approximation exists for (iii) unless P=NP.To prove these results we show that we can partition the vertices of G, and define a partial order on the subsets of this partition, such that ideals of the partial order correspond bijectively to minimum st-cuts of G. This shows that the problems are closely related to Uniform Partially Ordered Knapsack (UPOK), a variant of POK where element utilities are equal to element weights. Our algorithm is also a PTAS for special types of UPOK instances.     

Finding minimum clique capacity

Let C be a clique of a graph G. The capacity of C is defined to be (|V (G)\C|+|D|)/2, where D is the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C. We give a polynomial-time algorithm to find the minimum clique capacity in a graph G. This problem arose in the study [1] of packing vertex-disjoint induced three-vertex paths in a graph with no stable set of size three, which in turn was motivated by Hadwiger’s conjecture.     

The minimum distance of sets of points and the minimum socle degree

Let K be a field of characteristic 0. Let be a reduced finite set of points, not all contained in a hyperplane. Let be the maximum number of points of Γ contained in any hyperplane, and let . If I⊂R=K[x₀,…,x_n] is the ideal of Γ, then in Tohaˇneanu (2009) [12] it is shown that for n=2,3, d(Γ) has a lower bound expressed in terms of some shift in the graded minimal free resolution of R/I. In these notes we show that this behavior holds true in general, for any n≥2: d(Γ)≥A_n, where A_n=min{a_i−n} and ⊕_iR(−a_i) is the last module in the graded minimal free resolution of R/I. In the end we also prove that this bound is sharp for a whole class of examples due to Juan Migliore (2010) [10].     

Inverse minimum flow problem

In this paper we consider the inverse minimum flow (ImF) problem, where lower and upper bounds for the flow must be changed as little as possible so that a given feasible flow becomes a minimum flow. A linear time and space method to decide if the problem has solution is presented. Strongly and weakly polynomial algorithms for solving the ImF problem are proposed. Some particular cases are studied and a numerical example is given.     

On minimum norm solutions

This note investigates the problem $$\min x_p^p /p,s.t.Ax \geqslant b,$$ where 1<p<∞. It is proved that the dual of this problem has the form $$\max b^T y - A^T y_q^q /q,s.t.y \geqslant 0,$$ whereq=p/(p?1). The main contribution is an explicit rule for retrieving a primal solution from a dual one. If an inequality is replaced by an equality, then the corresponding dual variable is not restricted to stay nonnegative. A similar modification exists for interval constraints. Partially regularized problems are also discussed. Finally, we extend an observation of Luenberger, showing that the dual of $$\min x_p ,s.t.Ax \geqslant b,$$ is $$\max b^T y,s.t.y \geqslant 0,A^T y_q \leqslant 1,$$ and sharpening the relation between a primal solution and a dual solution.     

Low-degree minimum spanning trees

Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that, under theL _p norm, the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit ball; we show an even tighter bound for MSTs where the maximum degree is minimized. We give the best-known bounds for the maximum MST degree for arbitraryL _p metrics in all dimensions, with a focus on the rectilinear metric in two and three dimensions. We show that for any finite set of points in the rectilinear plane an MST exists with maximum degree of at most 4, and for three-dimensional rectilinear space the maximum possible degree of a minimum-degree MST is either 13 or 14. Gabriel Robins was partially supported by NSF Young Investigator Award MIP-9457412. Jeffrey Salowe was partially supported by NSF Grants MIP-9107717 and CCR-9224789.     

A controllability minimum principle

A controllability minimum principle and two associated transversality conditions are presented, dealing with the controllability of nonlinear systems. The theorems represent necessary conditions for a control function to generate a system path which lies in the boundary of the set of points that are controllable to a target. The theorems presented here are controllability counterparts to Pontryagin's maximum principle, and undoubtedly these results will seem familiar or may have occurred to other researchers in the area of optimal control. The purpose of this paper is to make the distinction explicit and to establish the validity of these controllability theorems on their own merits. The theorems are demonstrated using a simple example and the principal result (a controllability minimum principle) is shown to be equivalent to the Kalman controllability criterion for linear systems.     

On minimum weight pseudo-triangulations

In this note we discuss some structural properties of minimum weight pseudo-triangulations of point sets.     

On equiwellset minimum problems

A sequence of minimum problems given on a metric space, together with a limit problem, is called equiwellset if every problem has exactly one solution, if the values converge, and if any asymptotically minimizing sequence converges to the solution of the limit problem. When all problems are equal we get the classical definition of Tyhonov. A metric characterization of equiwellposedness is given that generalizes results of Vainberg for a single problem. Differential characterizations are also obtained extending a result of Asplund-Rockafellar. Applications are given to the epsilon method and to the perturbations of the linear quadratic problem.Work partially supported by Laboratorio di Matematica Applicata del C.N.R. presso l'Università di Genova.     

Colorings at minimum cost

We define by min_c∑_{u,v}∈E(G)|c(u)−c(v)| the min-costMC(G) of a graph G, where the minimum is taken over all proper colorings c. The min-cost-chromatic numberχ_M(G) is then defined to be the (smallest) number of colors k for which there exists a proper k-coloring c attaining MC(G). We give constructions of graphs G where χ(G) is arbitrarily smaller than χ_M(G). On the other hand, we prove that for every 3-regular graph G^′, χ_M(G^′)≤4 and for every 4-regular line graph G^″, χ_M(G^″)≤5. Moreover, we show that the decision problem whether χ_M(G)=k is -hard for k≥3.