Rounding, Interval Partitioning and Separation
Lists
Only you see this
Abstract
The approximation techniques that we consider in this chapter apply to problems that can be formulated as profit/cost problems, defined as follows: given an n × n positive matrix C and two positive vectors p and b, find an n-bit vector ƒ such that its cost C . ƒ is bounded by b and its profit p . ƒ is maximized. The value of ƒ is computed incrementally. Starting from the 0 vector, the algorithm analyzes all possible extensions incrementing one bit at a time, until it covers the n bits. Notice that the new set can have twice the size of the previous one thus leading to an exponential size set in the last step. However, we can discard some of the new assignments according to some criteria to get polynomial size sets.
BibTeX
@inproceedings{daz1997rounding,
author = {Josep Dı́az and Marı́a Serna and Paul G. Spirakis and Jacobo Torán},
title = {{Rounding, Interval Partitioning and Separation}},
booktitle = {Cambridge},
year = {1997},
doi = {10.1017/cbo9780511666407.005},
}Loading related content...