Some basic exchange properties in combinatorial optimization and their application to constructing the K-best solutions
✍ Scribed by Ulrich Dergis
- Publisher
- Elsevier Science
- Year
- 1985
- Tongue
- English
- Weight
- 668 KB
- Volume
- 11
- Category
- Article
- ISSN
- 0166-218X
No coin nor oath required. For personal study only.
✦ Synopsis
Some basic exchange properties A combinatorial optimization problem (COP) can be described in the following way: Given a finite set E and a family of (feasible) subsets 9'~ 2' and a mapping c: E + ll?. With every FC E we associate a weight c(F): = c c(e). ccF Now the problem is to find SE .I/'s.t. c(S)5c(S') for all S' E 9'.
This problem is refered to as 9"(9'). Here .'/'may be the set of bases of a matroid, the set of perfect matchings in a graph etc.
Thus in the following we study only the minimization problem .9((.5") associated with the system (E,.Y',c). Yet analogous results for the maximization problem can easily be obtained by translating the results for the minimization problem to (E,.Y, -c).
Let m( 9)) be any useful measure of the dimension of the problem .?(.y), for instance m(9) = [El, and let n(9): = max{ /SJ 1 SE .7'}. In the following we will abbreviate m = m(9) and n = n(7).