Strategy-proofness, solidarity, and consistency for multiple assignment problems

We consider a problem of allocating indivisible objects when agents may desire to consume more than one object and no monetary transfers are allowed. We are interested in allocation rules that satisfy desirable properties from an economic and social point of view. In addition to strategy-proofness and Pareto efficiency, we consider consistency and two solidarity properties (replacement-domination and population-monotonicity). In most of the cases, these properties are satisfied only by serially dictatorial rules. Received: November 1999/Final version: December 2001     

Random assignment problems

Analysis of random instances of optimization problems provides valuable insights into the behavior and properties of problem’s solutions, feasible region, and optimal values, especially in large-scale cases. A class of problems that have been studied extensively in the literature using the methods of probabilistic analysis is represented by the assignment problems, and many important problems in operations research and computer science can be formulated as assignment problems. This paper presents an overview of the recent results and developments in the area of probabilistic assignment problems, including the linear and multidimensional assignment problems, quadratic assignment problem, etc.     

Quadratic assignment problems

This paper surveys quadratic assignment problems (QAP). At first several applications of this problem class are described and mathematical formulations of QAPs are given. Then some exact solution methods and good heuristics are outlined. Their computational behaviour is illustrated by numerical results. Further recent results on the asymptotic probabilistic behaviour of QAPs are outlined.     

An algorithm for algebraic assignment problems

An O(n³) algorithm is described for solving algebraic assigment problems.     

Testing for multiple change points

In this paper we concentrate on testing for multiple changes in the mean of a series of independent random variables. Suggested method applies a maximum type test statistic. Our primary focus is on an effective calculation of critical values for very large sample sizes comprising (tens of) thousands of observations and a moderate to large number of segments. To that end, Monte Carlo simulations and a modified Bellman’s principle of optimality are used. It is shown that, indisputably, computer memory becomes a critical bottleneck in solving a problem of such a size. Thus, minimization of the memory requirements and appropriate order of calculations appear to be the keys to success. In addition, the formula that can be used to get approximate asymptotic critical values using the theory of exceedance probability of Gaussian fields over a high level is presented.     

The alternating basis algorithm for assignment problems

The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems which both circumvents and exploits degeneracy. The algorithm is based on the observation that the degeneracy difficulties of the simplex method result from the unnecessary inspection of alternative basis representations of the extreme points. This paper characterizes a subsetQ of all bases that are capable of leading to an optimal solution to the problem if one exists. Using this characterization, an extreme point algorithm is developed which considers only those bases inQ. Computational results disclose that the new algorithm is substantially more efficient than previously developed primal and primal-dual extreme point (simplex) methods for assignment problems.     

Geometric three-dimensional assignment problems

We investigate two geometric special cases of the three-dimensional assignment problem: Given are three sets B, R and G (blue, red and green) each containing n grid points in the Euclidean plane. We want to find a partition of B ∪ R ∪ G into n three0colored triangles such that (a) the total circumference of all triangles or (b) the total area of all triangles becomes minimum. Both versions of the problem are proved to be NP-hard.     

Multi-dimensional vector assignment problems

We consider a special class of axial multi-dimensional assignment problems called multi-dimensional vector assignment (MVA) problems. An instance of the MVA problem is defined by $m$ disjoint sets, each of which contains the same number $n$ of $p$-dimensional vectors with nonnegative integral components, and a cost function defined on vectors. The cost of an $m$-tuple of vectors is defined as the cost of their component-wise maximum. The problem is now to partition the $m$ sets of vectors into $n$   $m$-tuples so that no two vectors from the same set are in the same $m$-tuple and so that the sum of the costs of the $m$-tuples is minimized. The main motivation comes from a yield optimization problem in semi-conductor manufacturing. We consider a particular class of polynomial-time heuristics for MVA, namely the sequential heuristics, and we study their approximation ratio. In particular, we show that when the cost function is monotone and subadditive, sequential heuristics have a finite approximation ratio for every fixed $m$. Moreover, we establish smaller approximation ratios when the cost function is submodular and, for a specific sequential heuristic, when the cost function is additive. We provide examples to illustrate the tightness of our analysis. Furthermore, we show that the MVA problem is APX-hard even for the case $m=3$ and for binary input vectors. Finally, we show that the problem can be solved in polynomial time in the special case of binary vectors with fixed dimension $p$.     

Consistent multiple testing for change points

The change point problem for independent normal means is considered as a multiple testing problem. Two stepwise methods are considered. Namely, the binary segmentation method of Vostrikova (1981) [7] and the maximum residual down method of Cohen et al. (2009) [5]. Both of these methods are shown to be consistent. Consistent here means that as sample sizes tend to infinity, the probability of making an error (false rejection or false acceptance) tends to zero.     

Lagrangean/surrogate relaxation for generalized assignment problems

This work presents Lagrangean/surrogate relaxation to the problem of maximum profit assignment of n tasks to m agents (n > m), such that each task is assigned to only one agent subject to capacity constraints on the agents. The Lagrangean/surrogate relaxation combines usual Lagrangean and surrogate relaxations relaxing first a set of constraints in the surrogate way. Then, the Lagrangean relaxation of the surrogate constraint is obtained and approximately optimized (one-dimensional dual). The Lagrangean/surrogate is compared with the usual Lagrangean relaxation on a computational study using a large set of instances. The dual bounds are the same for both relaxations, but the Lagrangean/surrogate can give improved local bounds at the application of a subgradient method, resulting in less computational times. Three relaxations are derived for the problem. The first relaxation considers a vector of multipliers for the capacity constraints, the second for the assignment constraints and the other for the Lagrangean decomposition constraints. Relaxation multipliers are used with efficient constructive heuristics to find good feasible solutions. The application of a Lagrangean/surrogate approach seems very promising for large scale problems.     

Asymptotic analysis for multi-objective sequential stochastic assignment problems

ABSTRACT

We provide an asymptotic analysis of multi-objective sequential stochastic assignment problems (MOSSAP). In MOSSAP, a fixed number of tasks arrive sequentially, with an n-dimensional value vector revealed upon arrival. Each task is assigned to one of a group of known workers immediately upon arrival, with the reward given by an n-dimensional product-form vector. The objective is to maximize each component of the expected reward vector. We provide expressions for the asymptotic expected reward per task for each component of the reward vector and compare the convergence rates for three classes of Pareto optimal policies.     

Towards auction algorithms for large dense assignment problems

In this paper, we focus on the problem of solving large-scale instances of the linear sum assignment problem by auction algorithms. We introduce a modified auction algorithm, called look-back auction algorithm, which extends the forward auction algorithm by the ability of reusing information from previous bids. We show that it is able to reuse information from the previous bids with high efficiency for all tested types of input instances. We discuss then the design and implementation of a suite of sequential and distributed memory auction algorithms on a Linux cluster with the evaluation on several types of input instances of the linear sum assignment problem. Our results show that the look-back auction algorithm solves sequentially nearly all types of dense instances faster than other evaluated algorithms and it is more stable than the forward-reverse auction algorithm for sparse instances. Our distributed memory auction algorithms are fully memory scalable. This research has been supported by IGA CTU under grant CTU0308013 and under research program MSMT 6840770014.     

A novel chaotic search for quadratic assignment problems

We propose a novel method for solving the quadratic assignment problems. First, we realize the conventional tabu search on a neural network, and modify it to a chaotic version. Our novel method includes both effects of chaotic dynamics and tabu search. We compare the performance of the novel chaotic search with the conventional tabu search and an exponential tabu search whose memory effect for tabu (forbidding previous moves) decays exponentially. We show that the exponential tabu search has higher performance than the conventional tabu search, and further that the novel method with a chaotic neural network exhibits the best performance. We also propose a controlling method of the chaotic neural network for realizing easy and robust applications of our method. Then, better performance can be realized without manual parameter setting for various problems.     

Absolute and relative Weyl theorems for generalized eigenvalue problems

Weyl-type eigenvalue perturbation theories are derived for Hermitian definite pencils A-λB, in which B is positive definite. The results provide a one-to-one correspondence between the original and perturbed eigenvalues, and give a uniform perturbation bound. We give both absolute and relative perturbation results, defined in the standard Euclidean metric instead of the chordal metric that is often used.