Nonlinear
Assignment
Problems and
solutions
Algorithms and
Applications
MULTI INDEX ASSIGNMENT PROBLEMS:
COMPLEXITY, APPROXIMATION, APPLICATIONS
INTRODUCTION
This chapter deals with approximation algorithms for
and applications of multi index assignment problems
(MIAPs). MIAPs and relatives of it have a relatively long
history both in applications as well as in theoretical
results, starting at least in the fifties (see e.g. [Motzkin,
,1952], [Schell, 1955] and [Koopmans and Beckmann,
1957]). Here we intend to give the reader i) an idea of the
range and diversity of practical problems that have been
formulated as an MIAP, and ii) an overview on what is
known on theoretical aspects of solving instances of
MIAPs. In particular, we will discuss complexity and
approximability issues for special cases of MIAPs. We feel
that investigating special cases of MIAPs is an important
topic since real-world instances almost always posses a
certain structure that can be exploited when it comes to
solving them.
Before doing so, let us first describe a somewhat
frivolous, quite unrealistic situation that gives rise to an
instance of an MIAP. Suppose that you have become
mayor of a set of villages. Everything is running
smoothly, except in one village where chaos seems to
rule. You, as a responsible mayor should, start looking
into this and after careful gathering of information you
find that there 30 cats, 30 houses, 30 men and 30 women
present in the village. Now, in order to establish some
peace you impose that 30 "units" will have to be formed,
each consisting of a cat, a house, a man, and a woman. It
,turns out that for each possible 4-tuple (and there are
304 = 810000 of them), a number is
NONLINEAR ASSIGNMENT PROBLEMS
known that reflects the happiness of this particular unit.
Since you as a mayor want to maximize total happiness,
the problem becomes to find those 30 units that achieve
total happiness.
This is an example of a so-called axial 4-index assignment
problem. Different versions of the MIAP may arise by
varying the number of indices, or by asking not for 30 4-
tuples but instead for 302 4-tuples such that each pair
consisting of a cat and a house is represented exactly
once in a 4-tuple, or by considering other objective
functions (e.g. bottleneck).
This chapter is organized as follows. In Section 1.1 we
give some technical preliminaries. Section 2. deals with
the two versions of the 3-index assignment problem;
Section 3. treats the general case. Finally, in Section 4. we
discuss extensions of the MIAP.
1.1 TECHNICAL PRELIMINARIES
, An introduction to the issue of approximation and
complexity can be found in [Papadimitriou, 1994] and
[Crescenzi and Kann, 1999]. Here, we shortly describe
two concepts we need.
A p-approximation algorithm for a maximization
(minimization) problem P is a polynomial time algorithm
that, for all instances, outputs a solution with a value that
is at least (at most) equal to p times the value of an
optimal solution of P. Observe that for maximization
problems 0 < p < 1 and for minimization problems p > 1.
A polynomial time approximation scheme (PTAS) for a
maximization (minimization) problem is a family of
polynomial time (1 - e)-approximation algorithms ((1 +
e)-approximation algorithms) for all e > 0.
1. THE 3-INDEX ASSIGNMENT PROBLEM
In this section we introduce two types of 3-index
assignment problems, the so-called axial 3-index
assignment problem and the so-called planar 3-index
assignment problem (these names were first used by
Assignment
Problems and
solutions
Algorithms and
Applications
MULTI INDEX ASSIGNMENT PROBLEMS:
COMPLEXITY, APPROXIMATION, APPLICATIONS
INTRODUCTION
This chapter deals with approximation algorithms for
and applications of multi index assignment problems
(MIAPs). MIAPs and relatives of it have a relatively long
history both in applications as well as in theoretical
results, starting at least in the fifties (see e.g. [Motzkin,
,1952], [Schell, 1955] and [Koopmans and Beckmann,
1957]). Here we intend to give the reader i) an idea of the
range and diversity of practical problems that have been
formulated as an MIAP, and ii) an overview on what is
known on theoretical aspects of solving instances of
MIAPs. In particular, we will discuss complexity and
approximability issues for special cases of MIAPs. We feel
that investigating special cases of MIAPs is an important
topic since real-world instances almost always posses a
certain structure that can be exploited when it comes to
solving them.
Before doing so, let us first describe a somewhat
frivolous, quite unrealistic situation that gives rise to an
instance of an MIAP. Suppose that you have become
mayor of a set of villages. Everything is running
smoothly, except in one village where chaos seems to
rule. You, as a responsible mayor should, start looking
into this and after careful gathering of information you
find that there 30 cats, 30 houses, 30 men and 30 women
present in the village. Now, in order to establish some
peace you impose that 30 "units" will have to be formed,
each consisting of a cat, a house, a man, and a woman. It
,turns out that for each possible 4-tuple (and there are
304 = 810000 of them), a number is
NONLINEAR ASSIGNMENT PROBLEMS
known that reflects the happiness of this particular unit.
Since you as a mayor want to maximize total happiness,
the problem becomes to find those 30 units that achieve
total happiness.
This is an example of a so-called axial 4-index assignment
problem. Different versions of the MIAP may arise by
varying the number of indices, or by asking not for 30 4-
tuples but instead for 302 4-tuples such that each pair
consisting of a cat and a house is represented exactly
once in a 4-tuple, or by considering other objective
functions (e.g. bottleneck).
This chapter is organized as follows. In Section 1.1 we
give some technical preliminaries. Section 2. deals with
the two versions of the 3-index assignment problem;
Section 3. treats the general case. Finally, in Section 4. we
discuss extensions of the MIAP.
1.1 TECHNICAL PRELIMINARIES
, An introduction to the issue of approximation and
complexity can be found in [Papadimitriou, 1994] and
[Crescenzi and Kann, 1999]. Here, we shortly describe
two concepts we need.
A p-approximation algorithm for a maximization
(minimization) problem P is a polynomial time algorithm
that, for all instances, outputs a solution with a value that
is at least (at most) equal to p times the value of an
optimal solution of P. Observe that for maximization
problems 0 < p < 1 and for minimization problems p > 1.
A polynomial time approximation scheme (PTAS) for a
maximization (minimization) problem is a family of
polynomial time (1 - e)-approximation algorithms ((1 +
e)-approximation algorithms) for all e > 0.
1. THE 3-INDEX ASSIGNMENT PROBLEM
In this section we introduce two types of 3-index
assignment problems, the so-called axial 3-index
assignment problem and the so-called planar 3-index
assignment problem (these names were first used by
