Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Synchronized Sweep Algorithm for the k-Dimensional Cumulative Constraint
SICStus Prolog.
RISE, Swedish ICT, SICS. RISE, Swedish ICT, SICS, Computer Systems Laboratory. SICStus Prolog.
SICStus Prolog.
Number of Authors: 3
2013 (English)In: CPAIOR, Springer , 2013, 9, Vol. LNCS 7874, 144-159 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer , 2013, 9. Vol. LNCS 7874, 144-159 p.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-24332DOI: 10.1007/978-3-642-38171-3_10OAI: oai:DiVA.org:ri-24332DiVA: diva2:1043412
Conference
CPAOIR
Projects
SICStus Prolog
Available from: 2016-10-31 Created: 2016-10-31Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full texthttp
By organisation
SICSComputer Systems Laboratory
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.27.0