Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Engineering algorithms for workflow satisfiability problem with user-independent constraints

Cohen, David, Crampton, Jason, Gagarin, Andrei, Gutin, Gregory and Jones, Mark 2014. Engineering algorithms for workflow satisfiability problem with user-independent constraints. Presented at: FAW 2014: 8th International Workshop on Frontiers in Algorithmics, Zhangjiajie, China, 28-30 June 2014. Published in: Chen, Jainer, Hopcroft, John E. and Wang, Jianxin eds. Frontiers in Algorithmics: 8th International Workshop, FAW 2014, Zhangjiajie, China, June 28-30, 2014. Proceedings. Lecture Notes in Computer Science Springer Verlag, pp. 48-59. 10.1007/978-3-319-08016-1_5

[img]
Preview
PDF - Accepted Post-Print Version
Download (295kB) | Preview

Abstract

The workflow satisfiability problem (WSP) is a planning problem. Certain sub-classes of this problem have been shown to be fixed-parameter tractable. In this paper we develop an implementation of an algorithm for WSP that has been shown, in our previous paper, to be fixed-parameter for user-independent constraints. In a set of computational experiments, we compare our algorithm to an encoding of the WSP into a pseudo-Boolean SAT problem solved by the well-known solver SAT4J. Our algorithm solves all instances of WSP generated in our experiments, unlike SAT4J, and it solves many instances faster than SAT4J. For lightly constrained instances, SAT4J usually outperforms our algorithm.

Item Type: Conference or Workshop Item (Paper)
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Publisher: Springer Verlag
ISBN: 9783319080154
ISSN: 0302-9743
Date of First Compliant Deposit: 1 June 2016
Last Modified: 26 Jan 2018 15:23
URI: http://orca.cf.ac.uk/id/eprint/91298

Citation Data

Cited 17 times in Google Scholar. View in Google Scholar

Cited 12 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics