Finite turns and the regular closure of linear context-free languages

Turn bounded pushdown automata with different conditions for beginning a new turn are investigated. Their relationships with closures of the linear context-free languages under regular operations are studied. For example, automata with an unbounded number of turns that have to empty their pushdown store up to the initial symbol in order to start a new turn are characterized by the regular closure of the linear languages. Automata that additionally have to re-enter the initial state are (almost) characterized by the Kleene star closure of the linear languages. For both a bounded and an unbounded number of turns, requiring to empty the pushdown store is a strictly stronger condition than requiring to re-enter the initial state. Several new language families are obtained which form a double-stranded hierarchy. Closure properties of these families under AFL operations are derived. The regular closure of the linear languages share the strong closure properties of the context-free languages, i.e., the family is a full AFL. Interestingly, three natural new language families are not closed under intersection with regular languages and inverse homomorphism. Finally, an algorithm is presented parsing languages from the new families in quadratic time.     

Growth of power-free languages: Numerical and asymptotic bounds

We consider power-free languages over finite alphabets. That is, the words which are powers with the exponent greater than a given constant cannot be factors of words in these languages. We give numerical bounds of the exponential growth rate for a wide range of such languages. These bounds are obtained using the algorithms proposed by the author. On the basis of these bounds we suggest the asymptotic behaviour of the growth rate as a function of the exponent and the size of the alphabet, and give some theorems about this behaviour.     

Branch-and-price algorithms for the Two-Echelon Capacitated Vehicle Routing Problem

In this paper, we propose an Integer Programming formulation and two branch-and-price implementations for the Two-Echelon Capacitated Vehicle Routing Problem. One algorithm considers routes that satisfy the elementarity condition, while the other relaxes such constraint when pricing routes. For instances that could not be solved to proven optimality within a given time limit, our computational experience suggests that the former provides sharper upper bounds while the latter offers tighter lower bounds. As a by-product, ten new best upper bounds and two new optimality certificates are provided here.     

On growth factors of the modified Gram–Schmidt algorithm

Growth factors play a central role in studying the stability properties and roundoff estimates of matrix factorizations; therefore, they have attracted many numerical analysts to study upper bounds of these growth factors. In this article, we derive several upper bounds of row‐wise growth factors of the modified Gram–Schmidt (MGS) algorithm to solve the least squares (LS) problem and the weighted LS problem. We also extend the analysis to the MGS‐like algorithm to solve the constrained LS problem. Copyright © 2008 John Wiley & Sons, Ltd.     

New upper bounds for online strip packing

In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into one or more strips of width 1 and infinite height so as to minimize the required height of the packing. By analyzing a two-phase shelf algorithm, we derive a new upper bound 6.4786 on the competitive ratio for online one strip packing. This result improves the best known upper bound of 6.6623. We also extend this algorithm to online multiple strips packing and present some numeric upper bounds on their competitive ratios which are better than the previous bounds.     

Enhancing set constraint solvers with lexicographic bounds

Since their beginning in constraint programming, set solvers have been applied to a wide range of combinatorial search problems, such as bin-packing, set partitioning, circuit and combinatorial design. In this paper we present and evaluate a new means towards improving the practical reasoning power of Finite Set (FS) constraint solvers to better address such set problems with a particular attention to the challenging symmetrical set problems often cast as Combinatorial Design Problems (CDPs). While CDPs find a natural formulation in the language of sets, in constraint programming literature, alternative models are often used due to a lack of efficiency of traditional FS solvers. We first identify the main structural components of CDPs that render their modeling suitable to set languages but their solving a technical challenge. Our new prototype solver extends the traditional subset variable domain with lexicographic bounds that better approximate a set domain by satisfying the cardinality restrictions applied to the variable, and allow for active symmetry breaking using ordering constraints. Our contribution includes the formal and practical framework of the new solver implemented on top of a traditional set solver, and an empirical evaluation on benchmark CDPs.     

Restorations of punctured languages and similarity of languages

Punctured languages are languages whose words are partial words in the sense that the letters at some positions are unknown. We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with similarity classes according to some kind of similarity for languages. Thus all results we can also formulate in the language of similarity. We show some hierarchies of similarity classes for each class from the Chomsky hierarchy and prove the existence of linear languages which are not δ ‐similar to any regular language for any δ < ½. For δ ≥ ½ this is unknown but it could only be possible in the case of non‐slender linear languages. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Generalization of an inequality of Birnbaum and Marshall,with applications to growth rates for submartingales

The well-known submartingale maximal inquality of Birnbaum and Marshall (1961) is generalized to provide upper tail inequalities for suprema of processes which are products of a submartingale by a nonincreasing nonnegative predictable process. The new inequalities are proved by applying an inequality of Lenglart (1977), and are then used to provide best-possible universal growth-rates for a general submartingale in terms of the predictable compensator of its positive part. Applications of these growth rates include strong asymptotic upper bounds on solutions to certain stochastic differential equations, and strong asymptotic lower bounds on Brownian-motion occupation-times.     

Bounds and estimates on the effective properties for nonlinear composites

In this paper we derive lower bounds and upper bounds on the effective properties for nonlinear heterogeneous systems. The key result to obtain these bounds is to derive a variational principle, which generalizes the variational principle by P. Ponte Castaneda from 1992. In general, when the Ponte Castaneda variational principle is used one only gets either a lower or an upper bound depending on the growth conditions. In this paper we overcome this problem by using our new variational principle together with the bounds presented by Lukkassen, Persson and Wall in 1995. Moreover, we also present some examples where the bounds are so tight that they may be used as a good estimate of the effective behavior.     

An exact algorithm for large multiple knapsack problems

The Multiple Knapsack Problem (MKP) is the problem of assigning a subset of n items to m distinct knapsacks, such that the total profit sum of the selected items is maximized, without exceeding the capacity of each of the knapsacks. The problem has several applications in naval as well as financial management. A new exact algorithm for the MKP is presented, which is specially designed for solving large problem instances. The recursive branch-and-bound algorithm applies surrogate relaxation for deriving upper bounds, while lower bounds are obtained by splitting the surrogate solution into the m knapsacks by solving a series of Subset-sum Problems. A new separable dynamic programming algorithm is presented for the solution of Subset-sum Problems, and we also use this algorithm for tightening the capacity constraints in order to obtain better upper bounds. The developed algorithm is compared to the mtm algorithm by Martello and Toth, showing the benefits of the new approach. A surprising result is that large instances with n=100 000 items may be solved in less than a second, and the algorithm has a stable performance even for instances with coefficients in a moderately large range.     

Linear programming for the 0–1 quadratic knapsack problem

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints rebundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.     

学生面试问题的分配策略

就学生面试问题中的教师分配策略进行了系统的分析.首先我们分别给出并证明了在面试老师数一定,满足没有两个老师相同以及三个老师相同情形下的,可承担面试学生数的四个上界.然后提出了2种分配算法:排队算法和集合压缩算法,计算结果表明,所提算法可以很好的逼近理论上界.针对文理各半的情形,我们也同样提出并证明了类似的上界,两种分配策略同样适合文理各半的情形.在不分文理和文理各半的两种情况下,我们提出的分配策略都能很好的逼进甚至达到上界,同时也说明了我们理论界是一个很紧的上界.     

Vizing's coloring algorithm and the fan number

Most upper bounds for the chromatic index of a graph come from algorithms that produce edge colorings. One such algorithm was invented by Vizing [Diskret Analiz 3 (1964), 25–30] in 1964. Vizing's algorithm colors the edges of a graph one at a time and never uses more than Δ+µ colors, where Δ is the maximum degree and µ is the maximum multiplicity, respectively. In general, though, this upper bound of Δ+µ is rather generous. In this paper, we define a new parameter fan(G) in terms of the degrees and the multiplicities of G. We call fan(G) the fan number of G. First we show that the fan number can be computed by a polynomial‐time algorithm. Then we prove that the parameter Fan(G)=max{Δ(G), fan(G)} is an upper bound for the chromatic index that can be realized by Vizing's coloring algorithm. Many of the known upper bounds for the chromatic index are also upper bounds for the fan number. Furthermore, we discuss the following question. What is the best (efficiently realizable) upper bound for the chromatic index in terms of Δ and µ ? Goldberg's Conjecture supports the conjecture that χ′+1 is the best efficiently realizable upper bound for χ′ at all provided that P ≠ NP . © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 115–138, 2010     

An algorithm and upper bounds for the weighted maximal planar graph problem

In this paper, we investigate the weighted maximal planar graph (WMPG) problem. Given a complete, edge-weighted, simple graph, the WMPG problem involves finding a subgraph with the highest sum of edge weights that is maximal planar, namely, it can be embedded in the plane without any of its edges intersecting, and no additional edge can be added to the subgraph without violating its planarity. We present a new integer linear programming (ILP) model for this problem. We then develop a cutting-plane algorithm to solve the WMPG problem based on the proposed ILP model. This algorithm enables the problem to be solved more efficiently than previously reported algorithms. New upper bounds are also provided, which are useful in evaluating the quality of heuristic solutions or in generating initial solutions for meta-heuristics. Computational results are reported for a set of 417 test instances of size varying from 6 to 100 nodes including 105 instances from the literature and 312 randomly generated instances. The computational results indicate that instances with up to 24 nodes can be solved optimally in reasonable computational time and the new upper bounds for larger instances significantly improve existing upper bounds.     

The computation of bounds for the norm of the error in the conjugate gradient algorithm

In this paper we consider computing estimates of the norm of the error in the conjugate gradient (CG) algorithm. Formulas were given in a paper by Golub and Meurant (1997). Here, we first prove that these expressions are indeed upper and lower bounds for the A-norm of the error. Moreover, starting from these formulas, we investigate the computation of the l ₂-norm of the error. Finally, we define an adaptive algorithm where the approximations of the extreme eigenvalues that are needed to obtain upper bounds are computed when running CG leading to an improvement of the upper bounds for the norm of the error. Numerical experiments show the effectiveness of this algorithm. This revised version was published online in August 2006 with corrections to the Cover Date.     

Recognizing splicing languages: Syntactic monoids and simultaneous pumping

We use syntactic monoid methods, together with an enhanced pumping lemma, to investigate the structure of splicing languages. We obtain an algorithm for deciding whether a regular language is a reflexive splicing language, but the general question remains open.     

A note on matrices with maximal growth factor for Neville elimination

Neville elimination is a direct method for the solution of linear systems of equations with advantages for some classes of matrices and in the context of pivoting strategies for parallel implementations. The growth factor is an indicator of the numerical stability of an algorithm. In the literature, bounds for the growth factor of Neville elimination with some pivoting strategies have appeared. In this work, we determine all the matrices such that the minimal upper bound of the growth factor of Neville elimination with those pivoting strategies is reached.     

Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case

We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not included in the class of monotone Boolean functions. For the particular case of symmetric functions our bounds are matching and we exactly characterize the best possible competitiveness achievable by a deterministic algorithm. Our upper bound is obtained by a simple polynomial time algorithm.     

Improved state space relaxation for constrained two-dimensional guillotine cutting problems

Christofides and Hadjiconstantinou (1995) introduced a dynamic programming state space relaxation for obtaining upper bounds for the Constrained Two-dimensional Guillotine Cutting Problem. The quality of those bounds depend on the chosen item weights, they are adjusted using a subgradient-like algorithm. This paper proposes Algorithm X, a new weight adjusting algorithm based on integer programming that provably obtains the optimal weights. In order to obtain even better upper bounds, that algorithm is generalized into Algorithm X2 for obtaining optimal two-dimensional item weights. We also present a full hybrid method, called Algorithm X2D, that computes those strong upper bounds but also provides feasible solutions obtained by: (1) exploring the suboptimal solutions hidden in the dynamic programming matrices; (2) performing a number of iterations of a GRASP based primal heuristic; and (3) executing X2H, an adaptation of Algorithm X2 to transform it into a primal heuristic. Extensive experiments with instances from the literature and on newly proposed instances, for both variants with and without item rotation, show that X2D can consistently deliver high-quality solutions and sharp upper bounds. In many cases the provided solutions are certified to be optimal.