Generalized parametric path problems

Kshitij Gajjar, Girish Varma, Prerona Chatterjee, Jaikumar Radhakrishnan
Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, PMLR 161:536-546, 2021.

Abstract

Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general path problem with relaxed assumptions, and describe how this formulation is applicable in these domains. We study the complexity of the general problem, and a variant of it where preprocessing is allowed. We show that when the parametric weights are linear functions, algorithms remain tractable even under our relaxed assumptions. Furthermore, we show that if the weights are allowed to be non-linear, the problem becomes NP-hard. We also study the multi-dimensional version of the problem where the weight functions are parameterized by multiple parameters. We show that even with two parameters, this problem is NP-hard.

Cite this Paper

BibTeX
@InProceedings{pmlr-v161-gajjar21a, title = {Generalized parametric path problems}, author = {Gajjar, Kshitij and Varma, Girish and Chatterjee, Prerona and Radhakrishnan, Jaikumar}, booktitle = {Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence}, pages = {536--546}, year = {2021}, editor = {de Campos, Cassio and Maathuis, Marloes H.}, volume = {161}, series = {Proceedings of Machine Learning Research}, month = {27--30 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v161/gajjar21a/gajjar21a.pdf}, url = {https://proceedings.mlr.press/v161/gajjar21a.html}, abstract = {Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general path problem with relaxed assumptions, and describe how this formulation is applicable in these domains. We study the complexity of the general problem, and a variant of it where preprocessing is allowed. We show that when the parametric weights are linear functions, algorithms remain tractable even under our relaxed assumptions. Furthermore, we show that if the weights are allowed to be non-linear, the problem becomes NP-hard. We also study the multi-dimensional version of the problem where the weight functions are parameterized by multiple parameters. We show that even with two parameters, this problem is NP-hard.} }
Endnote
%0 Conference Paper %T Generalized parametric path problems %A Kshitij Gajjar %A Girish Varma %A Prerona Chatterjee %A Jaikumar Radhakrishnan %B Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2021 %E Cassio de Campos %E Marloes H. Maathuis %F pmlr-v161-gajjar21a %I PMLR %P 536--546 %U https://proceedings.mlr.press/v161/gajjar21a.html %V 161 %X Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general path problem with relaxed assumptions, and describe how this formulation is applicable in these domains. We study the complexity of the general problem, and a variant of it where preprocessing is allowed. We show that when the parametric weights are linear functions, algorithms remain tractable even under our relaxed assumptions. Furthermore, we show that if the weights are allowed to be non-linear, the problem becomes NP-hard. We also study the multi-dimensional version of the problem where the weight functions are parameterized by multiple parameters. We show that even with two parameters, this problem is NP-hard.
APA
Gajjar, K., Varma, G., Chatterjee, P. & Radhakrishnan, J.. (2021). Generalized parametric path problems. Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 161:536-546 Available from https://proceedings.mlr.press/v161/gajjar21a.html.

Related Material