An asymptotically exact algorithm for one modification of planar three-index assignment problem
Authors:
- 1 December 2007
- journal article
- Published by Pleiades Publishing Ltd in Journal of Applied and Industrial Mathematics
- Vol. 1 (4) , 442-452
Abstract
An m-layer three-index assignment problem is considered which is a modification of the classical planar three-index assignment problem. This problem is NP-hard for m ⩾ 2. An approximate algorithm, solving this problem for 1 < m < n/2, is suggested. The bounds on its quality are proved in the case when the input data (the elements of an m × n × n matrix) are independent identically distributed random variables whose values lie in the interval [a n, b n], where b n > a n > 0. The time complexity of the algorithm is O(mn 2 + m 7/2). It is shown that in the case of a uniform distribution (and also a distribution of minorized type) the algorithm is asymptotically exact if m = Θ(n 1 − θ ) and b n/a n = o(n θ) for every constant θ, 0 < θ < 1.Keywords
This publication has 13 references indexed in Scilit:
- On Some Probability Inequalities for Some Discrete Optimization Problems2006
- Algorithms with Performance Guarantees for a Metric Problem of Finding Two Edge-Disjoint Hamiltonian Circuits of Minimum Total WeightOperations Research Proceedings, 2004
- Multi-index assignment problem: an asymptotically optimal approach2001
- Asymptotic optimality of a transport-problem plan constructed by the minimum-element methodCybernetics and Systems Analysis, 1999
- Arrays of distinct representatives — a very simple NP-complete problemDiscrete Mathematics, 1997
- An Algorithm for the Three-Index Assignment ProblemOperations Research, 1991
- Facets of the three-index assignment polytopeDiscrete Applied Mathematics, 1989
- Complexity of a 3-dimensional assignment problemEuropean Journal of Operational Research, 1983
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- Theory of Graphs1962