New lower and upper bounds for the competitive ratio of transmission protocols

Transmission protocols like TCP are usually divided into a time scheduling and a data selection policy. We consider on-line algorithms of data selection policies for any time scheduling policy and any routing behavior in a network. For the model introduced by Adler et al. [Proc. 5th Israel Symp. on Theory of Computing Systems, 1997, pp. 64-72], we improve both the lower and the upper bound on the competitive ratio making them asymptotically tight. Furthermore, we present a lower bound that depends on the size of the buffers that are available both to the sender and to the receiver. We obtain a constant lower bound for the competitive ratio for constant buffer size.     

Quantum lower bounds for the Goldreich-Levin problem

At the heart of the Goldreich-Levin theorem is the problem of determining an n-bit string a by making queries to two oracles, referred to as IP (inner product) and EQ (equivalence). The IP oracle, on input x, returns a bit that is biased towards a⋅x (the modulo two inner product of a with x) in the following sense. For a random x, the probability that IP(x)=a⋅x is at least . The EQ oracle, on input x, returns a bit specifying whether or not x=a. It has been shown that a quantum algorithm can solve this problem with O(1/?) IP and EQ queries, whereas any classical algorithm requires Ω(n/?²) such queries. Also, the quantum algorithm requires only O(n/?) auxiliary one- and two-qubit gates in addition to its queries. We show that the above quantum algorithm is optimal in terms of both EQ and IP queries. Specifically, Ω(1/?) EQ queries are necessary, and Ω(1/?) IP queries are necessary if the number of EQ queries is .     

Finite-time lower bounds for the two-armed bandit problem

We obtain minimax lower bounds on the regret for the classical two-armed bandit problem. We provide a finite-sample minimax version of the well-known log n asymptotic lower bound of Lai and Robbins (1985). The finite-time lower bound allows us to derive conditions for the amount of time necessary to make any significant gain over a random guessing strategy. These bounds depend on the class of possible distributions of the rewards associated with the arms. For example, in contrast to the log n asymptotic results on the regret, we show that the minimax regret is achieved by mere random guessing under fairly mild conditions on the set of allowable configurations of the two arms. That is, we show that for every allocation rule and for every n, there is a configuration such that the regret at time n is at least 1-ϵ times the regret of random guessing, where ϵ is any small positive constant     

New lower bounds for the triplanar assignment problem. Use of the classical model

New sharp lower bounds are suggested for a triplanar assignment problem. They are based on the use of results of the theory of optimal control, the classical formulation of the problem, and represent, in our opinion, the “limit” use of the Hungarian algorithm ideas implemented for the two-index assignment problem.     

New bounds for the controller problem

The (M, W)-controller, originally studied by Afek, Awerbuch, Plotkin, and Saks, is a basic distributed tool that provides an abstraction for managing the consumption of a global resource in a distributed dynamic network. The input to the controller arrives online in the form of requests presented at arbitrary nodes. A request presented at node u corresponds to the ??desire?? of some entity to consume one unit of the global resource at u and the controller should handle this request within finite time either by granting it with a permit or by denying it. Initially, M permits (corresponding to M units of the global resource) are stored at a designated root node. Throughout the execution permits can be transported from place to place along the network??s links so that they can be granted to requests presented at various nodes; when a permit is granted to some request, it is eliminated from the network. The fundamental rule of an (M, W)-controller is that a request should not be denied unless it is certain that at least M ? W permits are eventually granted. The most efficient (M, W)-controller known to date has message complexity ${O (N\log^{2} N \log \frac{M}{W + 1})}$ , where N is the number of nodes that ever existed in the network (the dynamic network may undergo node insertions and deletions). In this paper we establish two new lower bounds on the message complexity of the controller problem. We first prove a simple lower bound stating that any (M, W)-controller must send ${\Omega (N \log \frac{M}{W + 1})}$ messages. Second, for the important case when W is proportional to M (this is the common case in most applications), we use a surprising reduction from the (centralized) monotonic labeling problem to show that any (M, W)-controller must send ??(N log N) messages. In fact, under a long lasting conjecture regarding the complexity of the monotonic labeling problem, this lower bound is improved to a tight ??(N log² N). The proof of this lower bound requires that N =?O(M) which turns out to be somewhat inevitable due to a new construction of an (M, M/2)-controller with message complexity O(N log² M).     

Lower and upper bounds for the two-echelon capacitated location-routing problem

In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.     

New lower bounds based on column generation and constraint programming for the pattern minimization problem

The pattern minimization problem is a cutting and packing problem that consists in finding a cutting plan with the minimum number of different patterns. This objective may be relevant when changing from one pattern to another involves a cost for setting up the cutting machine. When the minimization of the number of different patterns is done by assuming that no more than the minimum number of rolls can be used, the problem is also referred to as the cutting stock problem with setup costs.     

Lower and upper bounds for the mixed capacitated arc routing problem

This paper presents a linear formulation, valid inequalities, and a lower bounding procedure for the mixed capacitated arc routing problem (MCARP). Moreover, three constructive heuristics and a memetic algorithm are described. Lower and upper bounds have been compared on two sets of randomly generated instances. Computational results show that the average gaps between lower and upper bounds are 0.51% and 0.33%, respectively.     

The symmetric travelling salesman problem I. New fast lower bounds for the problem of optimal 2-matching

To solve the symmetric travelling salesman problem we suggest a lower bound—the solution of an optimal 2-matching problem. The latter problem is solved (in a polynomial number of steps) not completely, but up to obtaining new stable lower bounds.     

Local search and lower bounds for the patient admission scheduling problem

We propose a multi-neighborhood local search procedure to solve a healthcare problem, known as the Patient Admission Scheduling problem. We design and experiment with different combinations of neighborhoods, showing that they have diverse effectiveness for different sets of weights of the cost components that constitute the objective function. We also compute many lower bounds based on the relaxation of some constraints. The outcome is that our results compare favorably with the previous work on the problem, improving all available instances, and in some cases are also quite close to the lower bounds. Finally, we propose the application of the technique to the dynamic case, in which admission and discharge dates are not predictable in advance.     

New lower bounds for statistical query learning

We prove two lower bounds in the statistical query (SQ) learning model. The first lower bound is on weak-learning. We prove that for a concept class of SQ-dimension d, a running time of is needed. The SQ-dimension of a concept class is defined to be the maximum number of concepts that are “uniformly correlated”, in that each of their pair has nearly the same correlation. This lower bound matches the upper bound in Blum et al. (Weakly Learning DNF and Characterizing Statistical Query Learning using Fourier Analysis, STOC 1994, pp. 253-262), up to a logarithmic factor. We prove this lower bound against an “honest SQ-oracle”, which gives a stronger result than the ones against the more frequently used “adversarial SQ-oracles”. The second lower bound is more general. It gives a continuous trade-off between the “advantage” of an algorithm in learning the target function and the number of queries it needs to make, where the advantage of an algorithm is the probability it succeeds in predicting a label minus the probability it does not. Both lower bounds extend and/or strengthen previous results, and solve an open problem left in previous papers. An earlier version of this paper [K. Yang, New lower bounds for statistical query learning, in: The Proceedings of the 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, Lecture Notes in Computer Science, vol. 2375, 2002, pp. 229-243.] appeared in the proceedings of the 15th Annual Conference on Computational Learning Theory (COLT 2002).     

Efficient lower and upper bounds of the diagonal-flip distance between triangulations

There remains today an open problem whether the rotation distance between binary trees or equivalently the diagonal-flip distance between triangulations can be computed in polynomial time. We present an efficient algorithm for computing lower and upper bounds of this distance between a pair of triangulations.     

Arbitrarily tight upper and lower bounds on the Bayesianprobability of error

This paper presents new upper and lower bounds on the minimum probability of error of Bayesian decision systems for the two-class problem. These bounds can be made arbitrarily close to the exact minimum probability of error, making them tighter than any previously known bounds     

Stronger uncertainty relations with improvable upper and lower bounds

The quantum superposition principle is used to establish improved upper and lower bounds for the Maccone–Pati uncertainty inequality, which is based on a “weighted-like” sum of the variances of observables. Our bounds include free parameters that not only guarantee nontrivial bounds but also effectively control the bounds’ tightness. Significantly, these free parameters depend on neither the state nor the observables. A feature of our method is that any nontrivial bound can always be improved. In addition, we generalize both bounds to uncertainty relations with multiple (three or more) observables, maintaining the uncertainty relations’ tightness. Examples are given to illustrate our improved bounds.     

A comparison of lower bounds for the single-machine early/tardy problem

This paper considers the single-machine early/tardy problem. The paper presents a procedure that integrates a timetabling algorithm into a lower bound for jobs not included in a partial sequence. The paper also shows how two lower bounds that were developed previously for the problem can be improved. The lower bounds are tested on problems of various sizes and parameters for the distribution of due dates. The results show that the lower bounds are able to increase the efficiency of a branch-and-bound algorithm.