SODA

A Synchronized Sweep Algorithm for the k-Dimensional Cumulative Constraint

Letort, Arnaud and Carlsson, Mats and Beldiceanu, Nicolas (2013) A Synchronized Sweep Algorithm for the k-Dimensional Cumulative Constraint. In: CPAOIR, 18-22 May 2013, Yorktown Heights, NY, USA .

Full text not available from this repository.

Official URL: http://link.springer.com/chapter/10.1007/978-3-642...

Abstract

This paper presents a sweep based algorithm for the k-dimensional Cumulative constraint, which can operate in filtering mode as well as in greedy assignment mode. Given n tasks and k resources, this algorithm has a worst-case time complexity of O(kn^2) but scales well in practice. In greedy assignment mode, it handles up to 1 million tasks with 64 resources in one single constraint in SICStus. In filtering mode, on our benchmarks, it yields a speed-up of about k^(3/4) when compared to its decomposition into k independent Cumulative constraints.

Item Type:Conference or Workshop Item (Paper)
ID Code:5689
Deposited By:Mats Carlsson
Deposited On:09 Jul 2014 14:15
Last Modified:09 Jul 2014 14:15

Repository Staff Only: item control page