Propagating Knapsack Constraints in Sublinear Time

Irit Katriel, Meinolf Sellmann, Eli Upfal, Pascal Van Hentenryck

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(n log n + m k log (n/k)) time, where k <= n depends on the specific knapsack instance. We show that the expected value of k is significantly smaller than n on several interesting input distributions, hence while keeping the same worst-case complexity, on expectation the new algorithm is faster than the previously best method which runs in amortized linear time. After a theoretical study, we introduce heuristic enhancements and demonstrate the new algorithm's performance experimentally.

Subjects: 15.2 Constraint Satisfaction; 15. Problem Solving

Submitted: Apr 24, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.