An Improved Stability Bound for Binary Exponential Backoff

Goodman, Greenberg, Madras and March gave a lower bound of n ^{-Ω(log n} ) for the maximum arrival rate for which the n -user binary exponential backoff protocol is stable. Thus, they showed that the protocol is stable as long as the arrival rate is at most n ^{-Ω(log n} ) . We improve the lower bound, showing that the protocol is stable for arrival rates up to O(n ^-(0.75+δ) ) , for any δ>0 . Received October 15, 1999, and in final form November 13, 2000. Online publication February 26, 2001.     

An Optimal Lower Bound for Buffer Management in Multi-Queue Switches

In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, their excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput. We present a tight lower bound of e/(e?1)≈1.582 on the competitive ratio of the throughput maximization, which holds even for fractional or randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm Random Schedule. Our result contradicts the claimed performance of the algorithm Random Permutation; we point out a flaw in its original analysis.     

Partition-Based Lower Bound for Max-CSP

In this paper we address Max-CSP, a constraint optimization problem typically solved using a branch and bound scheme. It is well known that the efficiency of branch and bound greatly depends on the quality of the available lower bound. Previous approaches aggregate to the lower bound individual contributions of unassigned variables. In this paper, we augment this approach by adding global contributions of disjoint subsets of unassigned variables, which requires a partition of the set of unassigned variables. Using this idea, we introduce the partition-based lower bound. It improves previous approaches based on individual contributions in the sense that our method can be added up to previous bounds, possibly increasing their value. We demonstrate our method presenting two new algorithms, PFC-PRDAC and PFC-MPRDAC, which are the natural successors of PFC-RDAC and PFC-MRDAC augmented with our approach. We provide experimental evidence for the superiority of the new algorithms on random problems and real instances of weighted over-constrained problems.     

An Explicit Lower Bound for TSP with Distances One and Two

Abstract. We show that, for any ɛ>0 , it is NP-hard to approximate the asymmetric traveling salesman problem with distances one and two within 2805/2804-ɛ . For the special case where the distance function is constrained to be symmetric, we show a lower bound of 5381/5380-ɛ , for any ɛ>0 . While it was previously known that there exists some constant, strictly greater than one, such that it is NP-hard to approximate the traveling salesman problem with distances one and two within that constant, this result is a first step towards the establishment of a good bound. In our proof we develop a new gadget construction to reduce from systems of linear equations mod 2 with two unknowns in each equation and at most three occurrences of each variable. Compared with earlier reductions to the traveling salesman problem with distances one and two, ours reduces the number of cities to less than a tenth of what was previously necessary.     

An Explicit Lower Bound for TSP with Distances One and Two

We show that, for any ?>0 , it is NP-hard to approximate the asymmetric traveling salesman problem with distances one and two within 2805/2804-? . For the special case where the distance function is constrained to be symmetric, we show a lower bound of 5381/5380-? , for any ?>0 . While it was previously known that there exists some constant, strictly greater than one, such that it is NP-hard to approximate the traveling salesman problem with distances one and two within that constant, this result is a first step towards the establishment of a good bound. In our proof we develop a new gadget construction to reduce from systems of linear equations mod 2 with two unknowns in each equation and at most three occurrences of each variable. Compared with earlier reductions to the traveling salesman problem with distances one and two, ours reduces the number of cities to less than a tenth of what was previously necessary.     

Lower Bound Techniques for QBF Expansion

Theory of Computing Systems - We propose some general techniques for proving lower bounds in expansion-based QBF proof systems. We present them in a framework centred on natural properties of...     

A Lower Bound for Scheduling Mechanisms

We study the mechanism design problem of scheduling tasks on n unrelated machines in which the machines are the players of the mechanism. The problem was proposed and studied in the seminal paper of Nisan and Ronen on algorithmic mechanism design, where it was shown that the approximation ratio of mechanisms is between 2 and n. We improve the lower bound to \(1+\sqrt{2}\) for 3 or more machines.     

A Separation Bound for Real Algebraic Expressions

Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking roots of polynomials whose coefficients are given by the values of subexpressions. We consider the sign computation of real algebraic expressions, a task vital for the implementation of geometric algorithms. We prove a new separation bound for real algebraic expressions and compare it analytically and experimentally with previous bounds. The bound is used in the sign test of the number type leda::real. Partially supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2000-26473 (ECG—Effective Computational Geometry for Curves and Surfaces).     

Lower tolerance-based Branch and Bound algorithms for the ATSP

In this paper, we develop a new tolerance-based Branch and Bound algorithm for solving NP-hard problems. In particular, we consider the asymmetric traveling salesman problem (ATSP), an NP-hard problem with large practical relevance. The main algorithmic contribution is our lower bounding strategy that uses the expected costs of including arcs in the solution to the assignment problem relaxation of the ATSP, the so-called lower tolerance values. The computation of the lower bound requires the calculation of a large set of lower tolerances. We apply and adapt a finding from [23] that makes it possible to compute all lower tolerance values efficiently. Computational results show that our Branch and Bound algorithm exhibits very good performance in comparison with state-of-the-art algorithms, in particular for difficult clustered ATSP instances.     

An Improved Lower Matrix Bound of the Solution of the Unified Coupled Riccati Equation

A new lower matrix bound of the solution for the unified coupled algebraic Riccati equation (UCARE) is proposed. This bound improves the drawback of the results presented in a previous paper.     

A Superlogarithmic Lower Bound for Shuffle-Unshuffle Sorting Networks

Shuffle-unshuffle sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n -input shuffle-unshuffle sorting networks with depth have been discovered. These networks are the only known sorting networks of depth o( lg ² n) that are not based on expanders, and their existence raises the question of whether a depth of O( lg n) can be achieved by any shuffle-unshuffle sorting network. In this paper we resolve this question by establishing an Ω( lg n lg lg n/lg lg lg n) lower bound on the depth of any n -input shuffle-unshuffle sorting network. Our lower bound can be extended to certain restricted classes of nonoblivious sorting algorithms on hypercubic machines. Received September 9, 1999, and in final form December 20, 1999.     

良结构下推系统的可覆盖性问题的下界

良结构下推系统是下推系统和良结构迁移系统的结合,该系统允许状态和栈字符是向量的形式,因而它们是无限的.状态迁移的同时允许栈进行入栈出栈的操作.它“非常接近不可判定的边缘”.利用重置0操作,提出了一个模型可覆盖性问题复杂度下界的一般性证明方法,并且证明了状态是3维向量的子集和一般性的良结构下推系统的可覆盖性问题分别是Tower难和Hyper-Ackermann难的.     

An Extragradient Algorithm for Monotone Variational Inequalities

A new iterative algorithm is proposed for solving the variational inequality problem with a monotone and Lipschitz continuous mapping in a Hilbert space. The algorithm is based on the following two well-known methods: the Popov algorithm and so-called subgradient extragradient algorithm. An advantage of the algorithm is the computation of only one value of the inequality mapping and one projection onto the admissible set per one iteration. The weak convergence of sequences generated by the proposed algorithm is proved.     

多状态网络可靠度下界的矩阵分解算法

为减少计算多状态网络可靠度精确值的复杂性,提出基于分解计算多状态网络不可靠度精确值的思想,在此基础上提出一个求解多状态网络不可靠度动态上界(对应于可靠度动态下界)的算法.算法先通过分解运算去除某些边引起的d-最小割集之间的相关性,将网络不可靠度转化为多个互斥事件的概率之和,再应用MESP界求取这些事件的概率,计算网络不可靠度上界,对应得到可靠度下界,并计算了得到的可靠度下界与精确值间的绝对误差界.通过定义d-最小割集矩阵,利用矩阵分解实现算法,结构清晰、便于编程计算.相关引理的证明及算例分析表明随着分解的深入,算法能够得到满足精度要求的可靠度下界.