Routing vehicles to minimize fuel consumption

We consider a generalization of the capacitated vehicle routing problem known as the cumulative vehicle routing problem in the literature. Cumulative VRPs are known to be a simple model for fuel consumption in VRPs. We examine four variants of the problem, and give constant factor approximation algorithms. Our results are based on a well-known heuristic of partitioning the traveling salesman tours and the use of the averaging argument.     

Heuristics and lower bounds for the simple assembly line balancing problem type 1: Overview,computational tests and improvements

Assigning tasks to work stations is an essential problem which needs to be addressed in an assembly line design. The most basic model is called simple assembly line balancing problem type 1 (SALBP-1). We provide a survey on 12 heuristics and 9 lower bounds for this model and test them on a traditional and a lately-published benchmark dataset. The present paper focuses on algorithms published before 2011.     

Heuristics with guaranteed performance bounds for a manufacturing system with product recovery

We consider a manufacturing system with product recovery. The system manufactures a new product as well as remanufactures the product from old, returned items. The items remanufactured with the returned products are as good as new and satisfy the same demand as the new item. The demand rate for the new item and the return rate for the old item are deterministic and constant. The relevant costs are the holding costs for the new item and the returned item, and the fixed setup costs for both manufacturing and remanufacturing. The objective is to determine the lot sizes and production schedule for manufacturing and remanufacturing so as to minimize the long-run average cost per unit time. We first develop a lower bound among all classes of policies for the problem. We then show that the optimal integer ratio policy for the problem obtains a solution whose cost is at most 1.5% more than the lower bound.     

Lower bounds for lower Ramsey numbers

For any graph G, let i(G) and μ;(G) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers m and n, the lower Ramsey number s(m, n) is the largest integer p so that every graph of order p has i(G) ≤ m or μ;(G) ≤ n. In this paper we give several new lower bounds for s (m, n) as well as determine precisely the values s(1, n).     

Mixed lower bounds for quantum transport

Let H be a self-adjoint operator on a separable Hilbert space , . Given an orthonormal basis of , we consider the time-averaged moments 〈|X|_ψ^p〉(T) of the position operator associated to . We derive lower bounds for the moments in terms of both spectral measure μ_ψ and generalized eigenfunctions u_ψ(n,x) of the state ψ. As a particular corollary, we generalize the recently obtained lower bound in terms of multifractal dimensions of μ_ψ and give some equivalent forms of it which can be useful in applications. We establish, in particular, the relations between the L^q-norms (q>1/2) of the imaginary part of Borel transform of probability measures and the corresponding multifractal dimensions.     

New lower bounds for multiple coverings

A code , where Z ₂ = {0,1}, is said to be a binary μ-fold R-covering code, if for any word there are at least μ distinct codewords which differ from v in at most R coordinates. The size of the smallest binary μ-fold R-covering code of length n is denoted by K(n, R, μ). In this paper we use integer programming and exhaustive search to improve 57 lower bounds on K(n, R, μ) for 6 ≤ n ≤ 16, 1 ≤ R ≤ 4 and 2 ≤ μ ≤ 4.      

New lower bounds for Hopcroft's problem

We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set ofn points andm hyperplanes in $\mathbb{R}^d $ , is any point contained in any hyperplane? We define a general class ofpartitioning algorithms, and show that in the worst case, for allm andn, any such algorithm requires time Ω(n logm + n ^2/3m^2/3 + m logn) in two dimensions, or Ω(n logm + n ^5/6m^1/2 + n^1/2m^5/6 + m logn) in three or more dimensions. We obtain slightly higher bounds for the counting version of Hopcroft's problem in four or more dimensions. Our planar lower bound is within a factor of 2O(log^*(n+m)) of the best known upper bound, due to Matou?ek. Previously, the best known lower bound, in any dimension, was Ω(n logm + m logn). We develop our lower bounds in two stages. First we define a combinatorial representation of the relative order type of a set of points and hyperplanes, called amonochromatic cover, and derive lower bounds on its size in the worst case. We then show that the running time of any partitioning algorithm is bounded below by the size of some monochromatic cover. As a related result, using a straightforward adversary argument, we derive aquadratic lower bound on the complexity of Hopcroft's problem in a surprisingly powerful decision tree model of computation.     

Complexity bounds for primal-dual methods minimizing the model of objective function

Mathematical Programming - We provide Frank–Wolfe ( $$equiv $$ Conditional Gradients) method with a convergence analysis allowing to approach a primal-dual solution of convex optimization...     

Upper and lower bounds for the Voronoi-Minkowski constant

We study the behavior of the constant C(s) as s → ∞ arising in the estimate of the number of relative minima of s-dimensional integer lattices Γ via the logarithm log₂ N raised to the s ? 1th power, where N = D(Γ) is the determinant of Γ.     

Regular simplices and lower volume bounds for hyperbolicn-manifolds

For an-dimensional compact hyperbolic manifoldM ⁿ a new lower volume bound is presented. The estimate depends on the volume of a hyperbolic regularn-simplex of edge length equal to twice the in-radius ofM ⁿ. Its proof relies upon local density bounds for hyperbolic sphere packings.     

Structures and lower bounds for binary covering arrays

A $q$-ary $t$-covering array is an $m\times n$ matrix with entries from $\{0,1,\dots ,q?1\}$ with the property that for any $t$ column positions, all $q^t$ possible vectors of length $t$ occur at least once. One wishes to minimize $m$ for given $t$ and $n$, or maximize $n$ for given $t$ and $m$. For $t=2$ and $q=2$, it is completely solved by Rényi, Katona, and Kleitman and Spencer. They also show that maximal binary 2-covering arrays are uniquely determined. Roux found a lower bound of $m$ for a general $t,n$, and $q$. In this article, we show that $m\times n$ binary 2-covering arrays under some constraints on $m$ and $n$ come from the maximal covering arrays. We also improve the lower bound of Roux for $t=3$ and $q=2$, and show that some binary 3 or 4-covering arrays are uniquely determined.     

Ranking lower bounds for the bin-packing problem

In this paper, we evaluate different known lower bounds for the bin-packing problem including linear programming relaxation (LP), Lagrangean relaxation (LR), Lagrangean decomposition (LD) and the Martello–Toth (MT) [Martello, S., Toth, P., Knapsack Problems: Algorithms and Computer Implementations, Wiley, New York, 1990] lower bounds. We give conditions under which Lagrangean bounds are superior to the LP bound, show that Lagrangean decomposition (LD) yields the same bound as Lagrangean relaxation (LR) and prove that the MT lower bound is a Lagrangean bound evaluated at a finite set of Lagrange multipliers; hence, it is no better than the LR and LD lower bounds.     

Constructive lower bounds for off-diagonal Ramsey numbers

We describe an explicit construction whicy, for some fixed absolute positive constant ε, produces, for every integers>1 and all sufficiently largem, a graph on at least vertices containing neither a clique of sizes nor an independent set of sizem. Part of this work was done at the Institute for Advanced Study, Princeton, NJ 08540, USA. Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research supported in part by a grant A1019901 of the Academy of Sciences of the Czech Republic and by a cooperative research grant INT-9600919/ME-103 from the NSF (USA) and the MŠMT (Czech Republic).     

On error bounds for lower semicontinuous functions

We give some sufficient conditions for proper lower semicontinuous functions on metric spaces to have error bounds (with exponents). For a proper convex function f on a normed space X the existence of a local error bound implies that of a global error bound. If in addition X is a Banach space, then error bounds can be characterized by the subdifferential of f. In a reflexive Banach space X, we further obtain several sufficient and necessary conditions for the existence of error bounds in terms of the lower Dini derivative of f. Received: April 27, 2001 / Accepted: November 6, 2001?Published online April 12, 2002     

Complexity lower bounds for machine computing models

The article is the text of a survey report on methods of obtaining lower bounds on the computational complexity for abstract computers. Besides the methods for obtaining the lower bounds, related methods for the simulation of some machines by others, with the preservation of some complexity measures at the expense of increase in others (trade-off results), are presented. Methods of crossing sequences, tails, overlaps, and related methods are examined. A new proof of an old result is sometimes given to illustrate the working of a method, or a new result is proved.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 118, pp. 4–24, 1982.