The unsatisfiability threshold revisited

The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to variable ratio that marks the experimentally observed abrupt change from almost surely satisfiable formulas to almost surely unsatisfiable. Up to now, there have been rigorously established increasingly better lower and upper bounds to the actual threshold value. In this paper, we consider the problem of bounding the threshold value from above using methods that, we believe, are of interest on their own right. More specifically, we show how the method of local maximum satisfying truth assignments can be combined with results for the occupancy problem in schemes of random allocation of balls into bins in order to achieve an upper bound for the unsatisfiability threshold less than 4.571. In order to obtain this value, we establish a bound on the q-binomial coefficients (a generalization of the binomial coefficients). No such bound was previously known, despite the extensive literature on q-binomial coefficients. Finally, to prove our result we had to establish certain relations among the conditional probabilities of an event in various probabilistic models for random formulas. It turned out that these relations were considerably harder to prove than the corresponding ones for unconditional probabilities, which were previously known.     

Determining lower and upper bounds on probabilities of atomic propositions in sets of logical formulas represented by digraphs

In this paper we consider the problem of determining lower and upper bounds on probabilities of atomic propositions in sets of logical formulas represented by digraphs. We establish a sharp upper bound, as well as a lower bound that is not in general sharp. We show further that under a certain condition the lower bound is sharp. In that case, we obtain a closed form solution for the possible probabilities of the atomic propositions.The second author is partially supported by ONR grant N00014-92-J-1028 and AFOSR grant 91-0287.     

The Worst-Case GMRES for Normal Matrices

We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of 4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case. This revised version was published online in July 2006 with corrections to the Cover Date.     

On the average‐case complexity of Shellsort

We prove a lower bound expressed in the increment sequence on the average‐case complexity of the number of inversions of Shellsort. This lower bound is sharp in every case where it could be checked. A special case of this lower bound yields the general Jiang‐Li‐Vitányi lower bound. We obtain new results, for example, determining the average‐case complexity precisely in the Yao‐Janson‐Knuth 3‐pass case.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

A Cramér–Rao inequality for non-differentiable models

We compute a variance lower bound for unbiased estimators in statistical models. The construction of the bound is related to the original Cramér–Rao bound, although it does not require the differentiability of the model. Moreover, we show our efficiency bound to be always greater than the Cramér–Rao bound in smooth models, thus providing a sharper result.     

A tighter variant of Jensen’s lower bound for stochastic programs and separable approximations to recourse functions

In this paper, we propose a new method to compute lower bounds on the optimal objective value of a stochastic program and show how this method can be used to construct separable approximations to the recourse functions. We show that our method yields tighter lower bounds than Jensen’s lower bound and it requires a reasonable amount of computational effort even for large problems. The fundamental idea behind our method is to relax certain constraints by associating dual multipliers with them. This yields a smaller stochastic program that is easier to solve. We particularly focus on the special case where we relax all but one of the constraints. In this case, the recourse functions of the smaller stochastic program are one dimensional functions. We use these one dimensional recourse functions to construct separable approximations to the original recourse functions. Computational experiments indicate that our lower bounds can significantly improve Jensen’s lower bound and our recourse function approximations can provide good solutions.     

Generalized breadths,circular Cantor sets,and the least area UCC

We develop a technique suitable for determining the minimal area convex set that can cover certain prescribed regular polygons. As a side effect we improve the well-known “circle-and-triangle” lower bound on the least area Universal Convex Cover (UCC). Dedicated to the memory of Zs. Baranyai     

A Lamination Upper Bound to the Free Energy of Shape Memory Alloys

Modeling the energetic behavior of materials showing martensitic phase transformations usually leads to non-convex energy formulations. In a variety of models based on quasi-convex analysis, the Reuß lower bound, which neglects the compatibility constraint for the deformation fluctuations, is used as an estimate for the so-called energy of mixing. We present an upper bound that is on the one hand based on the lamination mixture formula, which gives an estimate of the free energy of two-variant materials and is extended to a specialized n-variant case in our work. On the other hand, we rely on experimentally well established assumptions about the type of microstructure that forms in such alloys. More precisely, we restrict the set of physically admissible microstructures to the subset of second order laminated microstructres consisting of austenite and twinned martensites. We further refine our upper bound by taking into account the notion of twin-compatibility. For the physically relevant examples of 13- and 7-variant Cu-Al-Ni shape memory alloys, striking congruence is obtained in the comparison of the Reuß lower and our upper bound for fixed volume fractions. Furthermore, we show results of global minimization of the energy obtained by each bound over the volume fractions of the variants. Similarities and differences in the energy-minimizing volume fractions are discussed. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Mixing of the Glauber dynamics for the ferromagnetic Potts model

We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree (Δ) of the underlying graph and the number of colours or spins (q) in determining whether the dynamics mixes rapidly or not. We find a lower bound L on the number of colours such that Glauber dynamics is rapidly mixing if at least L colours are used. We give a closely‐matching upper bound U on the number of colours such that with probability that tends to 1, the Glauber dynamics mixes slowly on random Δ‐regular graphs when at most U colours are used. We show that our bounds can be improved if we restrict attention to certain types of graphs of maximum degree Δ, e.g. toroidal grids for Δ = 4. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 21–52, 2016     

A priority-rule method for project scheduling with work-content constraints

The activities of a project are in general characterized by a work content in terms of resource–time units, e.g. person-days. Even though most project scheduling models assume a time-invariant resource usage, normally it is possible to vary the resource usage during the execution of an activity. Typically, a lower and an upper bound on this resource usage and a minimum time lag between consecutive changes of this resource usage are prescribed. The project scheduling problem studied in this paper consists in determining a feasible resource-usage profile for each activity such that the project duration is minimized subject to precedence and resource-capacity constraints. While the known solution methods interpret the prescribed work content as a lower bound, we assume that each activity’s work content must be processed exactly.     

O the volume growth of the hyperbolic regular $$\varvec{}$$-simplex

In this paper we give lower and upper bounds for the volume growth of a regular hyperbolic simplex, namely for the ratio of the n-dimensional volume of a regular simplex and the \((n-1)\)-dimensional volume of its facets. In addition to the methods of U. Haagerup and M. Munkholm we use a third volume form based on the hyperbolic orthogonal coordinates of a body. In the case of the ideal, regular simplex our upper bound gives the best known upper bound. On the other hand, also in the ideal case our general lower bound, improved the best known one for \(n=3\).     

The Supremum of Chi-Square Processes

We describe a lower bound for the critical value of the supremum of a Chi-Square process. This bound can be approximated using an RQMC simulation. We compare numerically this bound with the upper bound given by Davies, only suitable for a regular Chi-Square process. In a second part, we focus on a non regular Chi-Square process: the Ornstein–Uhlenbeck Chi-Square process. Recently, Rabier et al. (2009) have shown that this process has an application in genetics: it is the limiting process of the likelihood ratio test process related to the test of a gene on an interval representing a chromosome. Using results from Delong (Commun Stat Theory Method A10(20):2197–2213, 1981), we propose a theoretical formula for the supremum of such a process and we compare it in particular with our simulated lower bound.     

Range sets for weak efficiency in multiobjective linear programming and a parametric polytopes intersection problem

ABSTRACT

The aim of this paper is to obtain the range set for a given multiobjective linear programming problem and a weakly efficient solution. The range set is the set of all values of a parameter such that a given weakly efficient solution remains efficient when the objective coefficients vary in a given direction. The problem was originally formulated by Benson in 1985 and left to be solved. We formulate an algorithm for determining the range set, based on some hard optimization problems. Due to toughness of these optimization problems, we propose also lower and upper bound approximation techniques. In the second part, we focus on topological properties of the range set. In particular, we prove that a range set is formed by a finite union of intervals and we propose upper bounds on the number of intervals. Our approach to tackle the range set problem is via the intersection problem of parametric polytopes. Thus, our results have much wider area of applicability since the intersection (and separability) problem of convex polyhedra is important in many fields of optimization.     

New classes of fast lower bounds for bin packing problems

The bin packing problem is one of the classical NP-hard optimization problems. In this paper, we present a simple generic approach for obtaining new fast lower bounds, based on dual feasible functions. Worst-case analysis as well as computational results show that one of our classes clearly outperforms the previous best “economical” lower bound for the bin packing problem by Martello and Toth, which can be understood as a special case. In particular, we prove an asymptotic worst-case performance of 3/4 for a bound that can be computed in linear time for items sorted by size. In addition, our approach provides a general framework for establishing new bounds. Received: August 11, 1998 / Accepted: February 1, 2001?Published online September 17, 2001     

Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound

In this paper we study the Resource Constrained Project Scheduling Problem (RCPSP) with “Feeding Precedence” (FP) constraints and minimum makespan objective. This problem typically arises in production planning environment, like make-to-order manufacturing, where the effort associated with the execution of an activity is not univocally related to its duration percentage and the traditional finish-to-start precedence constraints or the generalized precedence relations cannot completely represent the overlapping among activities. In this context, we need to introduce in the RCPSP the FP constraints. For this problem we propose a new mathematical formulation and define a lower bound based on the Lagrangian relaxation of the resource constraints. A computational experimentation on randomly generated instances of sizes of up to 100 activities shows a better performance of this lower bound when compared to other lower bounds. Moreover, for the optimally solved instances, its value is very close to the optimal one. Furthermore, in order to show the effectiveness of the proposed lower bound on large instances for which the optimal solution is known, we adapted our approach to solve the benchmarks of the basic RCPSP from the PSLIB with 120 activities.     

Bounds for the relative Euler-Poincaré characteristic of certain hyperelliptic fibrations

In this paper, we find the lower bound for the relative Euler-Poincaré characteristic of a relatively minimal hyperelliptic fibration with slope four. We prove the existence of hyperelliptic fibrations over an elliptic curve, which attain our bound.     

Upper and Lower Bounds for the Lengths of Steiner Trees in 3-Space

We present a method of determining upper and lower bounds for the length of a Steiner minimal tree in 3-space whose topology is a given full Steiner topology, or a degenerate form of that full Steiner topology. The bounds are tight, in the sense that they are exactly satisfied for some configurations. This represents the first nontrivial lower bound to appear in the literature. The bounds are developed by first studying properties of Simpson lines in both two and three dimensional space, and then introducing a class of easily constructed trees, called midpoint trees, which provide the upper and lower bounds. These bounds can be constructed in quadratic time. Finally, we discuss strategies for improving the lower bound.Supported by a grant from the Australia Research Council.     

On Four-Connecting a Triconnected Graph

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n · α(m, n) + m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and α(m, n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k − 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.     

Bounds to optimal burn‐in and optimal work size

Burn‐in is a widely used method to improve the quality of products or systems after they have been produced. In this paper, we consider the problem of determining the optimal burn‐in time and optimal work size maximizing the long‐run average amount of work saved per time unit in the computer applications. Assuming that the underlying lifetime distribution of the computer has an initially decreasing or/and eventually increasing failure rate function, an upper bound for the optimal burn‐in time is derived for each fixed work size and a uniform (with respect to the burn‐in time) upper bound for the optimal work size is also obtained. Furthermore, it is shown that a non‐trivial lower bound for the optimal burn‐in time can be derived if the underlying lifetime distribution has a large initial failure rate. Copyright © 2005 John Wiley & Sons, Ltd.