Propagating Knapsack Constraints in Sublinear Time
Abstract
We develop an efficient incremental version of an existing cost-based filtering algorithm for the Knapsack constraint. On a universe of n elements, m invocations of the algorithm require a total of O(nlog n + mk log(n/k)) time, where k ≤ n depends on the instance. We show that the expected value of k is significantly smaller than n on several interesting input distributions, hence while keeping the same worstcase complexity, on expectation the new algorithm is faster than the previously best solution which runs in amortized linear time. After a theoretical study, we introduce heuristic enhancements and demonstrate the new algorithm’s performance experimentally.
Cite
Text
Katriel et al. "Propagating Knapsack Constraints in Sublinear Time." AAAI Conference on Artificial Intelligence, 2007.Markdown
[Katriel et al. "Propagating Knapsack Constraints in Sublinear Time." AAAI Conference on Artificial Intelligence, 2007.](https://mlanthology.org/aaai/2007/katriel2007aaai-propagating/)BibTeX
@inproceedings{katriel2007aaai-propagating,
title = {{Propagating Knapsack Constraints in Sublinear Time}},
author = {Katriel, Irit and Sellmann, Meinolf and Upfal, Eli and Van Hentenryck, Pascal},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2007},
pages = {231-236},
url = {https://mlanthology.org/aaai/2007/katriel2007aaai-propagating/}
}