Coarsening of Folds in Hanging Drapes

We consider the elastic energy of a hanging drape—a thin elastic sheet, pulled down by the force of gravity, with fine‐scale folding at the top that achieves approximately uniform confinement. This example of energy‐driven pattern formation in a thin elastic sheet is of particular interest because the length scale of folding varies with height. We focus on how the minimum elastic energy depends on the physical parameters. As the sheet thickness vanishes, the limiting energy is due to the gravitational force and is relatively easy to understand. Our main accomplishment is to identify the “scaling law” of the correction due to positive thickness. We do this by (i) proving an upper bound, by considering the energies of several constructions and taking the best; and (ii) proving an ansatz‐free lower bound, which agrees with the upper bound up to a parameter‐independent prefactor. The coarsening of folds in hanging drapes has also been considered in the recent physics literature, by using a self‐similar construction whose basic cell has been called a “wrinklon.” Our results complement and extend that work by showing that self‐similar coarsening achieves the optimal scaling law in a certain parameter regime, and by showing that other constructions (involving lateral spreading of the sheet) do better in other regions of parameter space. Our analysis uses a geometrically linear Föppl‐von Kármán model for the elastic energy, and is restricted to the case when Poisson's ratio is 0. © 2016 Wiley Periodicals, Inc.     

Optimal Fine‐Scale Structures in Compliance Minimization for a Shear Load

We return to a classic problem of structural optimization whose solution requires microstructure. It is well‐known that perimeter penalization assures the existence of an optimal design. We are interested in the regime where the perimeter penalization is weak; i.e., in the effect of perimeter as a selection mechanism in structural optimization. To explore this topic in a simple yet challenging example, we focus on a two‐dimensional elastic shape optimization problem involving the optimal removal of material from a rectangular region loaded in shear. We consider the minimization of a weighted sum of volume, perimeter, and compliance (i.e., the work done by the load), focusing on the behavior as the weight ɛ of the perimeter term tends to 0. Our main result concerns the scaling of the optimal value with respect to ɛ. Our analysis combines an upper bound and a lower bound. The upper bound is proved by finding a near‐optimal structure, which resembles a rank‐2 laminate except that the approximate interfaces are replaced by branching constructions. The lower bound, which shows that no other microstructure can be much better, uses arguments based on the Hashin‐Shtrikman variational principle. The regime being considered here is particularly difficult to explore numerically due to the intrinsic nonconvexity of structural optimization and the spatial complexity of the optimal structures. While perimeter has been considered as a selection mechanism in other problems involving microstructure, the example considered here is novel because optimality seems to require the use of two well‐separated length scales.© 2016 Wiley Periodicals, Inc.     

Axial Compression of a Thin Elastic Cylinder: Bounds on the Minimum Energy Scaling Law

We consider the axial compression of a thin elastic cylinder placed about a hard cylindrical core. Treating the core as an obstacle, we prove upper and lower bounds on the minimum energy of the cylinder that depend on its relative thickness and the magnitude of axial compression. We focus exclusively on the setting where the radius of the core is greater than or equal to the natural radius of the cylinder. We consider two cases: the “large mandrel” case, where the radius of the core exceeds that of the cylinder, and the “neutral mandrel” case, where the radii of the core and cylinder are the same. In the large mandrel case, our upper and lower bounds match in their scaling with respect to thickness, compression, and the magnitude of pre‐strain induced by the core. We construct three types of axisymmetric wrinkling patterns whose energy scales as the minimum in different parameter regimes, corresponding to the presence of many wrinkles, few wrinkles, or no wrinkles at all. In the neutral mandrel case, our upper and lower bounds match in a certain regime in which the compression is small as compared to the thickness; in this regime, the minimum energy scales as that of the unbuckled configuration. We achieve these results for both the von Kármán–Donnell model and a geometrically nonlinear model of elasticity. © 2017 Wiley Periodicals, Inc.     

Blister Patterns and Energy Minimization in Compressed Thin Films on Compliant Substrates

This paper is motivated by the complex blister patterns sometimes seen in thin elastic films on thick, compliant substrates. These patterns are often induced by an elastic misfit that compresses the film. Blistering permits the film to expand locally, reducing the elastic energy of the system. It is therefore natural to ask: what is the minimum elastic energy achievable by blistering on a fixed area fraction of the substrate? This is a variational problem involving both the elastic deformation of the film and substrate and the geometry of the blistered region. It involves three small parameters: the nondimensionalized thickness of the film, the compliance ratio of the film/substrate pair, and the mismatch strain. In formulating the problem, we use a small‐slope (Föppl–von Kármán) approximation for the elastic energy of the film, and a local approximation for the elastic energy of the substrate. For a one‐dimensional version of the problem, we obtain “matching” upper and lower bounds on the minimum energy, in the sense that both bounds have the same scaling behavior with respect to the small parameters. The upper bound is straightforward and familiar: it is achieved by periodic blistering on a specific length scale. The lower bound is more subtle, since it must be proved without any assumption on the geometry of the blistered region. For a two‐dimensional version of the problem, our results are less complete. Our upper and lower bounds only “match” in their scaling with respect to the nondimensionalized thickness, not in the dependence on the compliance ratio and the mismatch strain. The lower bound is an easy consequence of our one‐dimensional analysis. The upper bound considers a two‐dimensional lattice of blisters and uses ideas from the literature on the folding or “crumpling” of a confined elastic sheet. Our main two‐dimensional result is that in a certain parameter regime, the elastic energy of this lattice is significantly lower than that of a few large blisters. © 2015 Wiley Periodicals, Inc.     

Capacity and tool allocation problem in flexible manufacturing systems

This study addresses an allocation problem that arises in the semiconductor industry and flexible manufacturing systems where the tools should be loaded on computer numerical controlled (CNC) machines to process a number of operations. The time and tool magazine capacities of the CNC machines and the number of available tools of each type are limited. The objective is to maximize the total weight of operation assignments. We present a mixed integer programming formulation of the problem and show that the problem is NP-hard in the strong sense. We show that the linear programming relaxation upper bound dominates the best possible Lagrangean relaxation upper bound. We develop several lower bounding procedures and a lower bounding procedure using Lagrangean relaxation approach. Our computational results show that the upper and lower bounding procedures produce near-optimal solutions in reasonable times.     

Graph Treewidth and Geometric Thickness Parameters

Consider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of G, is the classical graph parameter thickness. By restricting the edges to be straight, we obtain the geometric thickness. By additionally restricting the vertices to be in convex position, we obtain the book thickness. This paper studies the relationship between these parameters and treewidth. Our first main result states that for graphs of treewidth k, the maximum thickness and the maximum geometric thickness both equal ⌈k/2⌉. This says that the lower bound for thickness can be matched by an upper bound, even in the more restrictive geometric setting. Our second main result states that for graphs of treewidth k, the maximum book thickness equals k if k ≤ 2 and equals k + 1 if k ≥ 3. This refutes a conjecture of Ganley and Heath [Discrete Appl. Math. 109(3):215-221, 2001]. Analogous results are proved for outerthickness, arboricity, and star-arboricity.     

A single machine batch scheduling problem with bounded batch size

We address a single-machine batch scheduling problem to minimize total flow time. Processing times are assumed to be identical for all jobs. Setup times are assumed to be identical for all batches. As in many practical situations, batch sizes may be bounded. In the first setting studied in this paper, all batch sizes cannot exceed a common upper bound. In the second setting, all batch sizes share a common lower bound. An optimal solution consists of the number of batches and their (integer) size. We introduce an efficient solution for both problems.     

Persistence of the bifurcation structure for a semilinear elliptic problem on thin domains

We study a semilinear elliptic problem on thin domains with a bifurcation parameter. It is shown that the set of solutions is upper semicontinuous as the thickness of a domain tends to 0, and that solution branches including bifurcation points persist near those of a one-dimensional limiting equation.     

The first eigenvalue of a spherical cap

We find upper and lower bounds for the first eigenvalue of the Laplacian on the two-sphere from which a disk has been removed, with Dirichlet conditions imposed on the resulting boundary. When the radius of the disk tends to zero our lower bound is sharper than that obtained by Del Grosso, Gerardi, and Marchetti in the preceding paper.     

Blow-Up Phenomena for Some Pseudo-Parabolic Equations with Nonlocal Term

We investigate the initial boundary value problem of some semilinear pseudo-parabolic equations with Newtonian nonlocal term. We establish a lower bound for the blow-up time if blow-up does occur. Also both the upper bound for $T$ and blow up rate of the solution are given when $J(u_0)<0$. Moreover, we establish the blow up result for arbitrary initial energy and the upper bound for $T$. As a product, we refine the lifespan when $J(u_0)<0.$     

Two counterfeit coins

We consider the problem of ascertaining the minimum number of weighings which suffice to determine the counterfeit (heavier) coins in a set of n coins of the same appearance, given a balance scale and the information that there are exactly two heavier coins present. An optimal procedure is constructed for infinitely many n's, and for all other n's a lower bound and an upper bound for the maximum number of steps of an optimal precedure are determined which differ by just one unit. Some results of Cairns are improved, and his conjecture at the end of [3] is proved in a slightly modified form.     

Randomized On-Line Scheduling Similar Jobs to Minimize Makespan on Two Identical Processors

In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.     

Optimizing bandwidth allocation in elastic optical networks with application to scheduling

We study a problem of optimal bandwidth allocation in the elastic optical networks technology, where usable frequency intervals are of variable width. In this setting, each lightpath has a lower and upper bound on the width of its frequency interval, as well as an associated profit, and we seek a bandwidth assignment that maximizes the total profit. This problem is known to be NP-complete. We strengthen this result by showing that, in fact, the problem is inapproximable within any constant ratio even on a path network. We further derive NP-hardness results and present approximation algorithms for several special cases of the path and ring networks, which are of practical interest. Finally, while in general our problem is hard to approximate, we show that an optimal solution can be obtained by allowing resource augmentation. Some of our results resolve open problems posed by Shalom et al. (2013) [28]. Our study has applications also in real-time scheduling.     

On the max‐cut of sparse random graphs

We consider the problem of estimating the size of a maximum cut (Max‐Cut problem) in a random Erdős‐Rényi graph on n nodes and edges. It is shown in Coppersmith et al. that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region with high probability (w.h.p.) as n increases, for all sufficiently large c. The upper bound was obtained by application of the first moment method, and the lower bound was obtained by constructing algorithmically a cut which achieves the stated lower bound. In this paper, we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval w.h.p. as n increases, for all sufficiently large c. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as c increases and use it to obtain an improved upper bound on the Max‐Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value . It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of on the Max‐Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of .     

Fractal methods and the problem of estimating scaling exponents: A new approach based on upper and lower linear bounds

The characterization of irregular objects with fractal methods often leads to the estimation of the slope of a function which is plotted versus a scale parameter. The slope is usually obtained with a linear regression. The problem is that the fit is usually not acceptable from the statistical standpoint. We propose a new approach in which we use two straight lines to bound the data from above and from below. We call these lines the upper and lower linear bounds. We propose to define these bounds as the solution of an optimization problem. We discuss the solution of this problem and we give an algorithm to obtain its solution. We use the difference between the upper and lower linear bounds to define a measure of the degree of linearity in the scaling range. We illustrate our method by analyzing the fluctuations of the variogram in a microresistivity well log from an oil reservoir in the North Sea.     

Ginzburg‐Landau vortex dynamics driven by an applied boundary current

In this paper we study the time‐dependent Ginzburg‐Landau equations on a smooth, bounded domain Ω ? ?², subject to an electrical current applied on the boundary. The dynamics with an applied current are nondissipative, but via the identification of a special structure in an interaction energy, we are able to derive a precise upper bound for the energy growth. We then turn to the study of the dynamics of the vortices of the solutions in the limit ε → 0. We first consider the original time scale in which the vortices do not move and the solutions undergo a “phase relaxation.” Then we study an accelerated time scale in which the vortices move according to a derived dynamical law. In the dynamical law, we identify a novel Lorentz force term induced by the applied boundary current. © 2010 Wiley Periodicals, Inc.     

Ricci curvature and betti numbers

We derive a uniform bound for the total betti number of a closed manifold in terms of a Ricci curvature lower bound, a conjugate radius lower bound and a diameter upper bound. The result is based on an angle version of Toponogov comparison estimate for small triangles in a complete manifold with a Ricci curvature lower bound. We also give a uniform estimate on the generators of the fundamental group and prove a fibration theorem in this setting.     

The projected newton method for solving inverse eigenvalue problems - the case of multiple eigenvaues

This paper deals with the optimal solution of ill-posed linear problems, i.e..linear problems for which the solution operator is unbounded. We consider worst-case ar,and averagecase settings. Our main result is that algorithms having finite error (for a given setting) exist if and only if the solution operator is bounded (in that setting). In the worst-case setting, this means that there is no algorithm for solving ill-posed problems having finite error. In the average-case setting, this means that algorithms having finite error exist if and only lf the solution operator is bounded on the average. If the solution operator is bounded on the average, we find average-case optimal information of cardinality n and optimal algorithms using this information, and show that the average error of these algorithms tends to zero as n→∞. These results are then used to determine the [euro]-complexity, i.e., the minimal costof finding an [euro]-accurate approximation. In the worst-case setting, the [euro]comp1exity of an illposed problem is infinite for all [euro]>0; that is, we cannot find an approximation having finite error and finite cost. In the average-case setting, the [euro]-complexity of an ill-posed problem is infinite for all [euro]>0 iff the solution operator is not bounded on the average, moreover, if the the solutionoperator is bounded on the average, then the [euro]-complexity is finite for all [euro]>0.     

A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

The symmetric quadratic knapsack problem (SQKP), which has several applications in machine scheduling, is NP-hard. An approximation scheme for this problem is known to achieve an approximation ratio of (1 + ?) for any ? > 0. To ensure a polynomial time complexity, this approximation scheme needs an input of a lower bound and an upper bound on the optimal objective value, and requires the ratio of the bounds to be bounded by a polynomial in the size of the problem instance. However, such bounds are not mentioned in any previous literature. In this paper, we present the first such bounds and develop a polynomial time algorithm to compute them. The bounds are applied, so that we have obtained for problem (SQKP) a fully polynomial time approximation scheme (FPTAS) that is also strongly polynomial time, in the sense that the running time is bounded by a polynomial only in the number of integers in the problem instance.     

An exponential decay estimate for the stationary axisymmetric perturbation of Poiseuille flow in a circular pipe

We prove a decay estimate for the steady state incompressible Navier-Stokes equations. The estimate describes the exponential decay, in the axial direction of a semi-infinite circular tube, for an energy-type functional in terms of the axisymmetric perturbation of Poiseuille flow, provided that the Reynolds number does not exceed a critical value, for which we exhibit a lower and an upper bound. Since the motion is considered axisymmetric we use a stream function formulation, and the results are similar to those obtained by Horgan [8], for a two-dimensional channel flow problem. For the Stokes problem our estimate for the rate of decay is a lower bound to the actual rate of decay which is obtained from an asymptotic solution to the Stokes equations. Finally we describe a numerical approach to computing bounds to the energy functionalE(0).