An average case analysis of the minimum spanning tree heuristic for the power assignment problem

We present an average case analysis of the minimum spanning tree heuristic for the power assignment problem. The worst‐case approximation ratio of this heuristic is 2. We show that in Euclidean d‐dimensional space, when the vertex set consists of a set of i.i.d. uniform random independent, identically distributed random variables in [0,1]^d, and the distance power gradient equals the dimension d, the minimum spanning tree‐based power assignment converges completely to a constant depending only on d.     

On the advantage over a random assignment

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max‐Lin‐2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max‐k‐Lin‐2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

On linear programs with random costs

We consider linear programs in which the objective function (cost) coefficients are independent non-negative random variables, and give upper bounds for the random minimum cost. One application shows that for quadratic assignment problems with such costs certain branch-and-bound algorithms usually take more than exponential time.     

An improved assignment lower bound for the euclidean traveling salesman problem

A simple transformation of the distance matrix for the Euclidean traveling salesman problem is presented that produces a tighter lower bound on the length of the optimal tour than has previously been attainable using the assignment relaxation. The improved lower bound is obtained by exploiting geometric properties of the problem to produce fewer and larger subtours on the first solution of the assignment problem. This research should improve the performance of assignment based exact procedures and may lead to improved heuristics for the traveling salesman problem.     

Worst-case analysis of a dynamic channel assignment strategy

We consider the problem of channel assignment in cellular networks with arbitrary reuse distance. We show upper and lower bounds for the competitive ratio of a previously proposed and widely studied version of dynamic channel assignment, which we refer to as the greedy algorithm. We study two versions of this algorithm: one that performs reassignment of channels, and one that never reassigns channels to calls. For reuse distance 2, we show tight bounds on the competitive ratio of both versions of the algorithm. For reuse distance 3, we show non-trivial lower bounds for both versions of the algorithm.     

Asymptotic Properties of Random Multidimensional Assignment Problems

The multidimensional assignment problem (MAP) is a NP-hard combinatorial optimization problem, occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables. We prove also that the mean optimal solution goes to negative infinity when assignment costs are independent normally distributed random variables.     

A spectral technique for random satisfiable 3CNF formulas

Let I be a random 3CNF formula generated by choosing a truth assignment ? for variables x₁, x_n uniformly at random and including every clause with i literals set true by ? with probability p_i, independently. We show that for any constants 0 ≤ η₂,η₃ ≤ 1 there is a constant d_min so that for all d ≥ d_min a spectral algorithm similar to the graph coloring algorithm of Alon and Kahale will find a satisfying assignment with high probability for p₁ = d/n², p₂ = η₂d/n², and p₃ = η₃d/n². Appropriately setting the η_i's yields natural distributions on satisfiable 3CNFs, not‐all‐equal‐sat 3CNFs, and exactly‐one‐sat 3CNFs. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The dynamic multilevel assignment problem as a stochastic extremal process

This paper considers the multilevel assignment problem (i.e. the assignment problem where the supply alternatives are ranked in hierarchical levels) under the assumption that the utility components for each pairwise matching are stochastic. A dynamic version of the multilevel stochastic assignment model is developed, where both demand and supply evaluate alternatives according to a stochastic extremal process, i.e. a process where the maximum of a sequence of random variables is taken into account. The probability distributions of the random variables which describe the joint dynamic behaviour of demand and supply are found. It is also shown that the assignment probabilities assume the structure of a nested-logit model.     

On the expected optimal value of random assignment problems: Experimental results and open questions

In the paper, we study the expected optimal value of random linear assignment problems, whose data are random variables with the uniform and the exponential distributions. An interior point approach is used to solve large-scale dense assignment problems with size up to 10,000 nodes and 100 million edges. Our computational results indicate the validity of a long-standing conjecture about the limiting value of the expected optimal assignment. Some interesting open problems and extensions are discussed.     

Characteristics of Good Meta-Heuristic Algorithms for the Frequency Assignment Problem

Most writers on frequency assignment algorithms have described the details of a single algorithm, and evaluated the algorithm on selected data sets. There has been relatively little emphasis on describing the common features that are important if an algorithm is to have good performance. This paper describes the key features, with particular emphasis on algorithms for weighted fixed spectrum problems. The use of algorithms handling weighted constraints has become increasingly common in recent years. The advantages and disadvantages of weighting constraints are demonstrated.     

Investigation of polynomial algorithms for solving the three-index planar assignment problem

Under certain additional conditions imposed on the coefficients of the objective function in the three-index planar assignment problem, a large series of computational experiments aimed at the investigation of four polynomial algorithms for finding an asymptotically optimal solution of this problem is conducted.     

A Study of Permutation Operators for Minimum Span Frequency Assignment Using an Order Based Representation

The genetic algorithm (GA) described in this paper breeds permutations of transmitters for minimum span frequency assignment. The approach hybridizes a GA with a greedy algorithm, and employs a technique called Generalized Saturation Degree to seed the initial population. Several permutation operators from the GA literature are compared, and results indicate that position based operators are more appropriate for this kind of problem than are order based operators. My offspring versus mid-parent correlation studies on crossovers show Pearson's correlation coefficient to be a reliable predictor of performance in most cases. Results presented herein represent improvements over previously published results.     

On the Hamming distance in combinatorial optimization problems on hypergraph matchings

In this note we consider the properties of the Hamming distance in combinatorial optimization problems on hypergraph matchings, also known as multidimensional assignment problems. It is shown that the Hamming distance between feasible solutions of hypergraph matching problems can be computed as an optimal value of linear assignment problem. For random hypergraph matching problems, an upper bound on the expected Hamming distance to the optimal solution is derived, and an exact expression is obtained in the special case of multidimensional assignment problems with 2 elements in each dimension.     

A survey of algorithms for the generalized assignment problem

This paper surveys algorithms for the well-known problem of finding the minimum cost assignment of jobs to agents so that each job is assigned exactly once and agents are not overloaded. All approaches seem to be based on branch-and-bound with bound supplied through heuristics and through relaxations of the primal problem formulation. From the survey one can select building blocks for the design of one's own tailor-made algorithm. The survey also reveals that although just about every mathematical programming technique was tried on this problem, there is still a lack of a representative set of test problems on which competing enumeration algorithms can be compared, as well as a shortage of effective heuristics.     

A linear time algorithm for the Koopmans–Beckmann QAP linearization and related problems

An instance of the quadratic assignment problem (QAP) with cost matrix $Q$ is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix $C$ such that for each assignment, the QAP and LAP objective function values are identical. The QAP linearization problem can be solved in $O\left(n^4\right)$ time. However, for the special cases of Koopmans–Beckmann QAP and the multiplicative assignment problem the input size is of $\Omega \left(n^2\right)$. We show that the QAP linearization problem for these special cases can be solved in $O\left(n^2\right)$ time. For symmetric Koopmans–Beckmann QAP, Bookhold [I. Bookhold, A contribution to quadratic assignment problems, Optimization 21 (1990) 933–943.] gave a sufficient condition for linearizability and raised the question if the condition is necessary. We show that Bookhold’s condition is also necessary for linearizability of symmetric Koopmans–Beckmann QAP.     

List scheduling algorithms to minimize the makespan on identical parallel machines

In this paper we present constructive algorithms for the classical deterministic scheduling problem of minimizing the makespan on identical machines. Since the problem is known to beNP-hard in the strong sense, the approximate algorithms play a relevant role when solving this problem. The proposed algorithms are based on list scheduling procedures, but the assignment rule is not the same for the full set of jobs. Computational results show that these algorithms perform very well. This research has been partially supported by the Research Project H015/2000, Universidad de Alcalá. The authors are indebted to Joaquín Pérez and the referees for their helpful remarks and comments. We also wish to thank Paul Alexander Ayres for his help in the correct use of English.     

Solving (large scale) matching problems combinatorially

In this paper we describe computational results for a modification of the shortest augmenting path approach for solving large scale matching problems. Using a new assignment start procedure and the two-phase strategy, where first the problem is solved on a sparse subgraph and then reoptimization is used, matching problems on complete graphs with 1000 nodes are solved in about 10–15 seconds on an IBM 4361.This work was partially supported by Sonderforschungsbereich 303, University of Bonn, and a special grant from the Deutsche Forschungsgemeinschaft.     

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 genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil

A heuristic based on genetic algorithms is proposed to the problem of configuring hub-and-spoke networks for trucking companies that operate less-than-truckload (LTL) services in Brazil. The problem consists of determining the number of consolidation terminals (also known as hubs), their locations and the assignment of the spokes to the hubs, aiming to minimize the total cost, which is composed of fixed and variable costs. The proposed formulation differs from similar formulations found in the literature in the sense that it allows variable scale-reduction factors for the transportation costs according to the total amount of freight between hub terminals, as occurs to less-than-truckload (LTL) freight carriers in Brazil. Our genetic algorithm approach incorporates an efficient local improvement procedure that is applied to each generated individual of the population. Computational results for benchmark problems are presented. A practical application to a real world problem involving one of the top-ten trucking companies in Brazil is also described.     

遗传算法在林木采伐作业信息管理中的应用

遗传算法是基于生物学进化原理的一种新的优化算法，本文介绍了遗传算法在林木采伐信息管理上的应用，通过林木采伐生产作业的衔接紧密的实际例子，论述了该方法在生产任务安排，降伐运输成本及劳力分配等信息管理中的作用。