TY - GEN
T1 - Work in Progress
T2 - 41st IEEE Real-Time Systems Symposium, RTSS 2020
AU - Baruah, Sanjoy
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/12
Y1 - 2020/12
N2 - Algorithms used for the pre-runtime analysis of safety-critical systems have traditionally been required to have running times no worse than pseudo-polynomial in the size of their inputs. Some recent work, however, has been motivated by a vast improvement in the performance of Integer Linear Programming (ILP) solvers and a concurrent widespread and inexpensive availability of increasing computing capabilities, to consider the use of ILP solvers as acceptably efficient for the purposes of such analysis. In this paper, the concept of ILP-tractability is proposed as a formal characterization of the class of scheduling problems that can be solved efficiently under this newer interpretation of efficiency. Techniques are presented for showing a problem to be ILP-tractable, as well as for showing a problem to be ILP-intractable-i.e., it cannot be solved efficiently using ILP solvers.
AB - Algorithms used for the pre-runtime analysis of safety-critical systems have traditionally been required to have running times no worse than pseudo-polynomial in the size of their inputs. Some recent work, however, has been motivated by a vast improvement in the performance of Integer Linear Programming (ILP) solvers and a concurrent widespread and inexpensive availability of increasing computing capabilities, to consider the use of ILP solvers as acceptably efficient for the purposes of such analysis. In this paper, the concept of ILP-tractability is proposed as a formal characterization of the class of scheduling problems that can be solved efficiently under this newer interpretation of efficiency. Techniques are presented for showing a problem to be ILP-tractable, as well as for showing a problem to be ILP-intractable-i.e., it cannot be solved efficiently using ILP solvers.
KW - Computational Complexity
KW - ILP-tractability
KW - Integer Linear Programs (ILPs)
KW - Schedulability-analysis
UR - https://www.scopus.com/pages/publications/85101958058
U2 - 10.1109/RTSS49844.2020.00046
DO - 10.1109/RTSS49844.2020.00046
M3 - Conference contribution
AN - SCOPUS:85101958058
T3 - Proceedings - Real-Time Systems Symposium
SP - 391
EP - 394
BT - Proceedings - 2020 IEEE 41st Real-Time Systems Symposium, RTSS 2020
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 1 December 2020 through 4 December 2020
ER -