Feasibility Analysis of Conditional DAG Tasks is co-NPNP-Hard

Sanjoy Baruah

doi:10.1145/3453417.3453422

Feasibility Analysis of Conditional DAG Tasks is co-NPNP-Hard

Sanjoy Baruah

Department of Computer Science & Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Scopus citations

Abstract

Feasibility-analysis algorithms have traditionally been required to have running times no worse than pseudo-polynomial in their inputs, in order to be considered efficient. But this is changing: motivated by a vast improvement in the performance of Integer Linear Programming (ILP) solvers, some recent work has begun to consider the limited use of ILP solvers as acceptably efficient for the purposes of feasibility analysis. In this paper, a characterization is proposed for the class of feasibility-analysis problems that can be solved efficiently under this more expansive interpretation of efficiency. This characterization is applied to the conditional directed acyclic graph (DAG) workload model, and a demarcation is identified between the feasibility-analysis problems on DAGs that are efficiently solvable using ILP solvers and those that are not.

Original language	English
Title of host publication	RTNS 2021 - 29th International Conference on Real-Time Networks and Systems
Publisher	Association for Computing Machinery
Pages	165-172
Number of pages	8
ISBN (Electronic)	9781450390019
DOIs	https://doi.org/10.1145/3453417.3453422
State	Published - Apr 7 2021
Event	29th International Conference on Real-Time Networks and Systems, RTNS 2021 - Nantes, France Duration: Apr 7 2021 → …

Publication series

Name	ACM International Conference Proceeding Series

Conference

Conference	29th International Conference on Real-Time Networks and Systems, RTNS 2021
Country/Territory	France
City	Nantes
Period	04/7/21 → …

Keywords

Computational Complexity
Conditional Directed Acyclic Graphs
Feasibility analysis
Integer Linear Programming

Access to Document

10.1145/3453417.3453422

Cite this

@inproceedings{fd231395fbbe441cb3509b0750124ebb,

title = "Feasibility Analysis of Conditional DAG Tasks is co-NPNP-Hard",

abstract = "Feasibility-analysis algorithms have traditionally been required to have running times no worse than pseudo-polynomial in their inputs, in order to be considered efficient. But this is changing: motivated by a vast improvement in the performance of Integer Linear Programming (ILP) solvers, some recent work has begun to consider the limited use of ILP solvers as acceptably efficient for the purposes of feasibility analysis. In this paper, a characterization is proposed for the class of feasibility-analysis problems that can be solved efficiently under this more expansive interpretation of efficiency. This characterization is applied to the conditional directed acyclic graph (DAG) workload model, and a demarcation is identified between the feasibility-analysis problems on DAGs that are efficiently solvable using ILP solvers and those that are not.",

keywords = "Computational Complexity, Conditional Directed Acyclic Graphs, Feasibility analysis, Integer Linear Programming",

author = "Sanjoy Baruah",

note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 29th International Conference on Real-Time Networks and Systems, RTNS 2021 ; Conference date: 07-04-2021",

year = "2021",

month = apr,

day = "7",

doi = "10.1145/3453417.3453422",

language = "English",

series = "ACM International Conference Proceeding Series",

publisher = "Association for Computing Machinery",

pages = "165--172",

booktitle = "RTNS 2021 - 29th International Conference on Real-Time Networks and Systems",

}

Baruah, S 2021, Feasibility Analysis of Conditional DAG Tasks is co-NPNP-Hard. in RTNS 2021 - 29th International Conference on Real-Time Networks and Systems. ACM International Conference Proceeding Series, Association for Computing Machinery, pp. 165-172, 29th International Conference on Real-Time Networks and Systems, RTNS 2021, Nantes, France, 04/7/21. https://doi.org/10.1145/3453417.3453422

TY - GEN

T1 - Feasibility Analysis of Conditional DAG Tasks is co-NPNP-Hard

AU - Baruah, Sanjoy

PY - 2021/4/7

Y1 - 2021/4/7

N2 - Feasibility-analysis algorithms have traditionally been required to have running times no worse than pseudo-polynomial in their inputs, in order to be considered efficient. But this is changing: motivated by a vast improvement in the performance of Integer Linear Programming (ILP) solvers, some recent work has begun to consider the limited use of ILP solvers as acceptably efficient for the purposes of feasibility analysis. In this paper, a characterization is proposed for the class of feasibility-analysis problems that can be solved efficiently under this more expansive interpretation of efficiency. This characterization is applied to the conditional directed acyclic graph (DAG) workload model, and a demarcation is identified between the feasibility-analysis problems on DAGs that are efficiently solvable using ILP solvers and those that are not.

AB - Feasibility-analysis algorithms have traditionally been required to have running times no worse than pseudo-polynomial in their inputs, in order to be considered efficient. But this is changing: motivated by a vast improvement in the performance of Integer Linear Programming (ILP) solvers, some recent work has begun to consider the limited use of ILP solvers as acceptably efficient for the purposes of feasibility analysis. In this paper, a characterization is proposed for the class of feasibility-analysis problems that can be solved efficiently under this more expansive interpretation of efficiency. This characterization is applied to the conditional directed acyclic graph (DAG) workload model, and a demarcation is identified between the feasibility-analysis problems on DAGs that are efficiently solvable using ILP solvers and those that are not.

KW - Computational Complexity

KW - Conditional Directed Acyclic Graphs

KW - Feasibility analysis

KW - Integer Linear Programming

UR - https://www.scopus.com/pages/publications/85111990738

U2 - 10.1145/3453417.3453422

DO - 10.1145/3453417.3453422

M3 - Conference contribution

AN - SCOPUS:85111990738

T3 - ACM International Conference Proceeding Series

SP - 165

EP - 172

BT - RTNS 2021 - 29th International Conference on Real-Time Networks and Systems

PB - Association for Computing Machinery

T2 - 29th International Conference on Real-Time Networks and Systems, RTNS 2021

Y2 - 7 April 2021

ER -

Feasibility Analysis of Conditional DAG Tasks is co-NPNP-Hard

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this