Karapetyan, Daniel, Gagarin, Andrei  ORCID: https://orcid.org/0000-0001-9749-9706 and Gutin, Gregory
2015.
Pattern backtracking algorithm for the workflow satisfiability problem with user-independent constraints.
Presented at: FAW 2015: 9th International Workshop on Frontiers in Algorithmics,
Guilin, China,
3-5 July 2015.
Published in: Wang, Jianxin and Yap, Chee eds.
Frontiers in Algorithmics: 9th International Workshop, FAW 2015, Guilin, China, July 3-5, 2015, Proceedings.
Lecture Notes in Computer Science.
, vol.9130
Springer Verlag,
pp. 138-149.
10.1007/978-3-319-19647-3_13
|
Preview |
PDF
- Accepted Post-Print Version
Download (337kB) | Preview |
Abstract
The workflow satisfiability problem (WSP) asks whether there exists an assignment of authorised users to the steps in a workflow specification, subject to certain constraints on the assignment. (Such an assignment is called valid.) The problem is NP-hard even when restricted to the large class of user-independent constraints. Since the number of steps k is relatively small in practice, it is natural to consider a parametrisation of the WSP by k. We propose a new fixed-parameter algorithm to solve the WSP with user-independent constraints. The assignments in our method are partitioned into equivalence classes such that the number of classes is exponential in k only. We show that one can decide, in polynomial time, whether there is a valid assignment in an equivalence class. By exploiting this property, our algorithm reduces the search space to the space of equivalence classes, which it browses within a backtracking framework, hence emerging as an efficient yet relatively simple-to-implement or generalise solution method. We empirically evaluate our algorithm against the state-of-the-art methods and show that it clearly wins the competition on the whole range of our test problems and significantly extends the domain of practically solvable instances of the WSP.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Status: | Published |
| Schools: | Schools > Mathematics |
| Subjects: | Q Science > QA Mathematics |
| Publisher: | Springer Verlag |
| ISBN: | 9783319196466 |
| ISSN: | 0302-9743 |
| Date of First Compliant Deposit: | 1 June 2016 |
| Last Modified: | 14 Nov 2024 12:45 |
| URI: | https://orca.cardiff.ac.uk/id/eprint/91297 |
Citation Data
Cited 17 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
 |
Edit Item |
Dimensions
Dimensions