Exam (elaborations)

Nonlinear Assignment Problems and solutions Algorithms and Applications

2 views 0 purchase

Course
ENGR 213 (ENGR)

Institution
Harvard University, Cambridge University

[Show more]

Preview 4 out of 60 pages

View example

Uploaded on July 19, 2022
Number of pages 60
Written in 2021/2022
Type Exam (elaborations)
Contains Questions & answers

approximation
applications
nonlinear assignment problems and solutions algorithms and applications
multi index assignment problems complexity

Institution
Harvard University, Cambridge University
Course
ENGR 213 (ENGR)

vincent54bundi

Member since 2 year 2 documents sold

CA$8.49

Added

Add to cart

Add to wishlist

100% satisfaction guarantee
Immediately available after payment
Both online and in PDF
No strings attached

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

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying these notes from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller vincent54bundi. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for CA$8.49. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

78834 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling

Exam (elaborations)

Nonlinear Assignment Problems and solutions Algorithms and Applications

Document information

Subjects

Written for

Seller

Reviews received

Content preview