Abstract
In this chapter, we consider a class of combinatorial optimization problems on hypergraph matchings that represent multidimensional generalizations of the well-known linear assignment problem (LAP). We present two algorithms for solving randomized instances of MAPs with linear and bottleneck objectives that obtain solutions with guaranteed quality.
Original language | English (US) |
---|---|
Pages (from-to) | 225-244 |
Number of pages | 20 |
Journal | Springer Proceedings in Mathematics and Statistics |
Volume | 20 |
DOIs | |
State | Published - 2012 |
Externally published | Yes |
Keywords
- Hypergraph matching problem
- Multidimensional assignment problem
- Probabilistic analysis
ASJC Scopus subject areas
- General Mathematics