@InProceedings{Bercher2020POPvsPOCL,
  author               = {Pascal Bercher and Conny Olz},
  title                = {POP $\equiv$ POCL, right? Complexity Results for Partial Order (Causal Link) Makespan Minimization},
  booktitle            = {Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020)},
  year                 = {2020},
  pages                = {9785--9793},
  publisher            = {AAAI Press},
  doi                  = {10.1609/aaai.v34i06.6530},
  abstract             = {We study PO and POCL plans with regard to their makespan -- the execution  time when allowing the parallel execution of causally independent actions. Partially ordered (PO) plans are often assumed to be equivalent to partial order causal link  (POCL) plans, where the causal relationships between actions are explicitly represented via causal links. As a first contribution, we study the similarities and differences of PO and POCL plans, thereby clarifying a common misconception about their relationship: There are PO plans for which there does not exist a POCL plan with the same orderings.We prove that we can still always find a POCL plan with the same makespan in polynomial time. As another main result we prove that turning a PO or POCL plan into one with minimal makespan by only removing ordering constraints (called deordering) is NP-complete. We provide a series of further results on special cases and implications, such as reordering, where orderings can be changed arbitrarily.},
  url_Paper            = {https://bercher.net/publications/2020/Bercher2020POPvsPOCL.pdf},
  url_Spotlight-slides = {https://bercher.net/publications/2020/Bercher2020POPvsPOCLSlidesSpotlight.pdf},
  url_Poster           = {https://bercher.net/publications/2020/Bercher2020POPvsPOCLPoster.pdf},
  keywords             = {conference}
}

{"_id":"RQkdHAjsQoySb8ZDZ","bibbaseid":"bercher-olz-poppoclrightcomplexityresultsforpartialordercausallinkmakespanminimization-2020","authorIDs":["4MgTsqa4pqwWD5L7g","8RLqMgShfRBnsyJWJ","AbR38PcFgcYhQEGiq","Be853DNQm2dkcxEky","HsQ97XBWs9p6tpo3i","gKYBTZ8WTzmEHtWPg","uWoe5n3L7AjW5DwG7"],"author_short":["Bercher, P.","Olz, C."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]},{"firstnames":["Conny"],"propositions":[],"lastnames":["Olz"],"suffixes":[]}],"title":"POP $≡$ POCL, right? Complexity Results for Partial Order (Causal Link) Makespan Minimization","booktitle":"Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020)","year":"2020","pages":"9785–9793","publisher":"AAAI Press","doi":"10.1609/aaai.v34i06.6530","abstract":"We study PO and POCL plans with regard to their makespan – the execution time when allowing the parallel execution of causally independent actions. Partially ordered (PO) plans are often assumed to be equivalent to partial order causal link (POCL) plans, where the causal relationships between actions are explicitly represented via causal links. As a first contribution, we study the similarities and differences of PO and POCL plans, thereby clarifying a common misconception about their relationship: There are PO plans for which there does not exist a POCL plan with the same orderings.We prove that we can still always find a POCL plan with the same makespan in polynomial time. As another main result we prove that turning a PO or POCL plan into one with minimal makespan by only removing ordering constraints (called deordering) is NP-complete. We provide a series of further results on special cases and implications, such as reordering, where orderings can be changed arbitrarily.","url_paper":"https://bercher.net/publications/2020/Bercher2020POPvsPOCL.pdf","url_spotlight-slides":"https://bercher.net/publications/2020/Bercher2020POPvsPOCLSlidesSpotlight.pdf","url_poster":"https://bercher.net/publications/2020/Bercher2020POPvsPOCLPoster.pdf","keywords":"conference","bibtex":"@InProceedings{Bercher2020POPvsPOCL,\n author = {Pascal Bercher and Conny Olz},\n title = {POP $\\equiv$ POCL, right? Complexity Results for Partial Order (Causal Link) Makespan Minimization},\n booktitle = {Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020)},\n year = {2020},\n pages = {9785--9793},\n publisher = {AAAI Press},\n doi = {10.1609/aaai.v34i06.6530},\n abstract = {We study PO and POCL plans with regard to their makespan -- the execution time when allowing the parallel execution of causally independent actions. Partially ordered (PO) plans are often assumed to be equivalent to partial order causal link (POCL) plans, where the causal relationships between actions are explicitly represented via causal links. As a first contribution, we study the similarities and differences of PO and POCL plans, thereby clarifying a common misconception about their relationship: There are PO plans for which there does not exist a POCL plan with the same orderings.We prove that we can still always find a POCL plan with the same makespan in polynomial time. As another main result we prove that turning a PO or POCL plan into one with minimal makespan by only removing ordering constraints (called deordering) is NP-complete. We provide a series of further results on special cases and implications, such as reordering, where orderings can be changed arbitrarily.},\n url_Paper = {https://bercher.net/publications/2020/Bercher2020POPvsPOCL.pdf},\n url_Spotlight-slides = {https://bercher.net/publications/2020/Bercher2020POPvsPOCLSlidesSpotlight.pdf},\n url_Poster = {https://bercher.net/publications/2020/Bercher2020POPvsPOCLPoster.pdf},\n keywords = {conference}\n}\n\n","author_short":["Bercher, P.","Olz, C."],"key":"Bercher2020POPvsPOCL","id":"Bercher2020POPvsPOCL","bibbaseid":"bercher-olz-poppoclrightcomplexityresultsforpartialordercausallinkmakespanminimization-2020","role":"author","urls":{" paper":"https://bercher.net/publications/2020/Bercher2020POPvsPOCL.pdf"," spotlight-slides":"https://bercher.net/publications/2020/Bercher2020POPvsPOCLSlidesSpotlight.pdf"," poster":"https://bercher.net/publications/2020/Bercher2020POPvsPOCLPoster.pdf"},"keyword":["conference"],"metadata":{"authorlinks":{}},"downloads":5},"bibtype":"inproceedings","biburl":"https://bercher.net/bibtex/bibliography.bib","creationDate":"2020-04-16T15:24:02.037Z","downloads":5,"keywords":["conference"],"search_terms":["pop","pocl","right","complexity","results","partial","order","causal","link","makespan","minimization","bercher","olz"],"title":"POP $≡$ POCL, right? Complexity Results for Partial Order (Causal Link) Makespan Minimization","year":2020,"dataSources":["upePYbh3wGv9oDZcn","zKgS72cAu6Ez7npdh","XzPF4F9wH9enwN62c","bPpsmYWjffAy6QHP5","wYF8yPQT6a4TgShWe"]}