𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The computational complexity of bilevel assignment problems

✍ Scribed by Elisabeth Gassner; Bettina Klinz

Publisher
Springer
Year
2009
Tongue
English
Weight
282 KB
Volume
7
Category
Article
ISSN
1619-4500

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The Computational Complexity of Some Pro
The Computational Complexity of Some Problems of Linear Algebra
✍ Jonathan F Buss; Gudmund S Frandsen; Jeffrey O Shallit πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 330 KB

We consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets of a commutative ring R. Let x 1 , x 2 , ..., x t be variables. Given a matrix M=M(x 1 , x 2 , ..., x t ) with entries chosen from E \_ [x 1 , x 2 , ..., x t ], we want to determine maxrank S (M)=

The computational complexity of Steiner
The computational complexity of Steiner tree problems in graded matrices
✍ T. DudΓ‘s; B. Klinz; G.J. Woeginger πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 349 KB

## Communicated by M. Iri Abstract--We investigate the computational complexity of the Steiner tree problem in graphs when the distance matrix is graded, i.e., has increasing, respectively, decreasing rows, or increasing, respectively, decreasing columns, or both. We exactly characterize polynomia

Complexity of the min–max and min–max re
Complexity of the min–max and min–max regret assignment problems
✍ Hassene Aissi; Cristina Bazgan; Daniel Vanderpooten πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 179 KB

This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment pro