A parallel algorithm to solve the stable marriage problem

In this paper a parallel algorithm to solve the stable marriage problem is given. The worst case performance of this algorithm is stated. A theoretical analysis shows that the probability of the occurrence of this worst case is extremely small. For instance, if there are sixteen men and sixteen women involved, then the probability that the worst case occurs is only 10^–45. Possible future research is also discussed in this paper.     

Open problems around exact algorithms

We list a number of open questions around worst case time bounds and worst case space bounds for NP-hard problems. We are interested in exponential time solutions for these problems with a relatively good worst case behavior. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature.     

The Upper Bound for the Stable Marriage Problem

The stable problem was originally posed by Gale and Shapley. The worst case performance of their solution is derived in a manner that illustrates the complexity characteristics of the problem. Several conclusions about the nature of the worst case situation are presented.     

Heuristics for unequal weight delivery problems with a fixed error guarantee

This paper presents heuristics that are based on optimal partitioning of a travelling salesman tour, for solving the unequal weight delivery problem. The worst case error performance is given as a bound on the worst case ratio of the cost of the heuristic solution to the cost of the optimal solution. A fully polynomial procedure which consists of applying the optimal partitioning to a travelling salesman tour generated by Christofides' heuristic has a worst case error bound of 3.5−3/Q where Q is the capacity limit of the vehicles. When optimal partitioning is applied to an optimal travelling salesman tour, the worst case error bound becomes 3−2/Q.     

First fit decreasing scheduling on uniform multiprocessors

Independent tasks are nonpreemptively scheduled on m≥2 processors which are assumed to have different speeds. The purpose of this paper is to show that the worst case ratio of the multifit algorithm MF, which is based on the bin-packing method FFD (first fit decreasing), depends on the order of the processors and that the MF has a better worst case behavior than the well-known LPT algorithm for certain processor configurations.     

可转包两台流水作业机排序的近似算法

研究可转包的两台流水作业机排序问题, 目标是极小化最大完工时间和总外包费用之和. 首先给出最坏情况界为2的近似算法, 接着对工件满足有序化约束的情形给出最坏情况界为\frac{3}{2}的改进算法, 以上算法界均为紧界.     

Worst case analysis of a class of set covering heuristics

In [2], Chvatal provided the tight worst case bound of the set covering greedy heuristic. We considered a general class of greedy type set covering heuristics. Their worst case bounds are dominated by that of the greedy heuristic.     

超尺寸物品装箱问题

本文给出一类新的装箱问题，超尺寸物品装箱问题。就实际解决该问题所普遍彩的两步法，证明了当采用经典目标函数并且拆分次数不超过2时，第二步采用FFDLR的渐进最坏比为3/2。进而针对超尺寸物品装箱问题的算法提出了一个评价效率更高的目标函数。证明了在此目标函数下，当不限制物品的最大尺寸时，第二步采用最优装法两步法的渐近最坏比为2。最后，给出渐近最坏与拆分次数的关系。     

The effect of multiple optima on the simple GA run-time complexity

Genetic algorithms are stochastic search algorithms that have been applied to optimization problems. In this paper we analyze the run-time complexity of a genetic algorithm when we are interested in one of a set of distinguished solutions. One such case occurs when multiple optima exist. We define the worst case scenario and derive a probabilistic worst case bound on the number of iterations required to find one of these multiple solutions of interest.     

A one-step worst-case optimal algorithm for bi-objective univariate optimization

A bi-objective optimization problem with univariate non-convex objectives is considered. The objective functions are assumed Lipschitz continuous. An algorithm is developed implementing the concept of one-step worst case optimality. The possibility of extension of the proposed algorithm to the multivariate case is discussed. Some illustrative numerical examples are included where the proposed algorithm is compared with an average case optimal algorithm.     

Worst case risk measurement: Back to the future?

This paper studies the problem of finding best-possible upper bounds on a rich class of risk measures, expressible as integrals with respect to measures, under incomplete probabilistic information. Both univariate and multivariate risk measurement problems are considered. The extremal probability distributions, generating the worst case scenarios, are also identified.The problem of worst case risk measurement has been studied extensively by Etienne De Vijlder and his co-authors, within the framework of finite-dimensional convex analysis. This paper revisits and extends some of their results.     

Multi-pattern matching with bidirectional indexes

We study multi-pattern matching in a scenario where the pattern set is to be matched to several texts and hence indexing the pattern set is affordable. This kind of scenarios arise, for example, in metagenomics, where pattern set represents DNA of several species and the goal is to find out which species are represented in the sample and in which quantity. We develop a generic search method that exploits bidirectional indexes both for the pattern set and texts, and analyze the best and worst case running time of the method on worst case text. We show that finding the instance of the search method with minimum best case running time on worst case text is NP-hard. The positive result is that an instance with logarithm factor approximation to minimum best case running time can be found in polynomial time using a bidirectional index called affix tree. We further show that affix trees can be simulated, in reduced space, using bidirectional variant of compressed suffix trees. Lastly, we provide a practical implementation of this approach. We show that one can obtain 3-fold speed up against the basic scenario of searching each pattern independently with data sets typical in high-throughput DNA sequencing.     

超尺寸物品装箱问题及其算法

本文探讨一类新装箱问题-超尺寸物品装箱问题。针对实际解决该问题的两涉法，我们提出了一个评价效率更高的目标函数，证明了在此目标函数下两步法的渐近最坏比不小于2，并给出了渐近量坏比与拆分次数的关系。最后本文提出了一种不同于两步法的新在线算法MA，证明了在新目标函数下其渐近最坏比不超过7/4。     

Average Flow Constraints and Stabilizability in Uncertain Production-Distribution Systems

We consider a multi-inventory system with controlled flows and uncertain demands (disturbances) bounded within assigned compact sets. The system is modelled as a first-order one integrating the discrepancy between controlled flows and demands at different sites/nodes. Thus, the buffer levels at the nodes represent the system state. Given a long-term average demand, we are interested in a control strategy that satisfies just one of two requirements: (i) meeting any possible demand at each time (worst case stability) or (ii) achieving a predefined flow in the average (average flow constraints). Necessary and sufficient conditions for the achievement of both goals have been proposed by the authors. In this paper, we face the case in which these conditions are not satisfied. We show that, if we ignore the requirement on worst case stability, we can find a control strategy driving the expected value of the state to zero. On the contrary, if we ignore the average flow constraints, we can find a control strategy that satisfies worst case stability while optimizing any linear cost on the average control. In the latter case, we provide a tight bound for the cost.     

Cuckoo hashing

We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. [SIAM J. Comput. 23 (4) (1994) 738–761]. The space usage is similar to that of binary search trees. Besides being conceptually much simpler than previous dynamic dictionaries with worst case constant lookup time, our data structure is interesting in that it does not use perfect hashing, but rather a variant of open addressing where keys can be moved back in their probe sequences. An implementation inspired by our algorithm, but using weaker hash functions, is found to be quite practical. It is competitive with the best known dictionaries having an average case (but no nontrivial worst case) guarantee on lookup time.     

Average complexity for linear operators over bounded domains

Suppose one wants to compare worst case and average complexities for approximation of a linear operator. In order to get a fair comparison the complexities have to be obtained for the same domain of the linear operator. In previous papers, average complexity was studied when the domain was the entire space. To avoid trivial results, worst case complexity has been studied for bounded domains, and in particular, for balls of finite radius. In this paper we study the average complexity for approximation of linear operators whose domain is a ball of finite radius q. We prove that the average complexities even for modest q and for q = +∞ are closely related. This and existing results enable us to compare the worst case and average complexities for balls of finite radius. We also analyze the average complexity for the normalized and relative errors. The paper is illustrated by integration of functions of one variable and by approximation of functions of d variables which are equipped with a Wiener measure.     

A stochastic programming model using an endogenously determined worst case risk measure for dynamic asset allocation

We present a new approach to asset allocation with transaction costs. A multiperiod stochastic linear programming model is developed where the risk is based on the worst case payoff that is endogenously determined by the model that balances expected return and risk. Utilizing portfolio protection and dynamic hedging, an investment portfolio similar to an option-like payoff structure on the initial investment portfolio is characterized. The relative changes in the expected terminal wealth, worst case payoff, and risk aversion, are studied theoretically and illustrated using a numerical example. This model dominates a static mean-variance model when the optimal portfolios are evaluated by the Sharpe ratio. Received: August 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000     

Q2‖Cmax的对偶近似算法

本文讨论两台同类平行机排序问题,首先给出Ｍｕｌｔｉｆｉｔ算法在不同迭代初值下的紧界,然后利用一个新设计的对偶贪婪子过程构造出线性时间６／５－复合近似算法。     

A hybrid algorithm for finding thekth smallest ofn elements in O(n) time

The problem of finding thekth smallest ofn elements can be solved either with O(n) algorithms or with O(n ²) algorithms. Although they require a higher number of operations in the worst case, O(n ²) algorithms are generally preferred to O(n) algorithms because of their better average performance. We present a hybrid algorithm which is O(n) in the worst case and efficient in the average case.     

The multifit algorithm for set partitioning containing kernels

This pager investigates the set partitioning containing kernels. This problem can alsobe considered as the identical machine scheduling prohlem with nonsimultaneous machine release times. That the algorithm MULTIFIT has a worst ease bound of 6/5 is proved. Throughcombining MULTIFIT and LPT. an algorithm MULTILPT with a worat case bound of 7/6 has been obtained.