2023

1.
Deligkas, A., Eiben, E., Skretas, G.: Minimizing Reachability Times on Temporal Graphs via Shifting Labels. International Joint Conference on Artificial Intelligence (IJCAI). pp. 5333–5340 (2023).
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
We study how we can accelerate the spreading of information in temporal graphs via delaying operations; a problem that captures real-world applications varying from information flows to distribution schedules. In a temporal graph there is a set of fixed vertices and the available connections between them change over time in a predefined manner. We observe that, in some cases, the delay of some connections can in fact decrease the time required to reach from some vertex (source) to another vertex (target). We study how we can minimize the maximum time a set of source vertices needs to reach every other vertex of the graph when we are allowed to delay some of the connections of the graph. For one source, we prove that the problem is W[2]-hard and NP-hard, when parameterized by the number of allowed delays. On the other hand, we derive a polynomial-time algorithm for one source and unbounded number of delays. This is the best we can hope for; we show that the problem becomes NP-hard when there are two sources and the number of delays is not bounded. We complement our negative result by providing an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution. Finally, we provide polynomial-time algorithms for several classes of graphs.
@inproceedings{deligkas2023minimizing, abstract = {We study how we can accelerate the spreading of information in temporal graphs via delaying operations; a problem that captures real-world applications varying from information flows to distribution schedules. In a temporal graph there is a set of fixed vertices and the available connections between them change over time in a predefined manner. We observe that, in some cases, the delay of some connections can in fact decrease the time required to reach from some vertex (source) to another vertex (target). We study how we can minimize the maximum time a set of source vertices needs to reach every other vertex of the graph when we are allowed to delay some of the connections of the graph. For one source, we prove that the problem is W[2]-hard and NP-hard, when parameterized by the number of allowed delays. On the other hand, we derive a polynomial-time algorithm for one source and unbounded number of delays. This is the best we can hope for; we show that the problem becomes NP-hard when there are two sources and the number of delays is not bounded. We complement our negative result by providing an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution. Finally, we provide polynomial-time algorithms for several classes of graphs.}, author = {Deligkas, Argyrios and Eiben, Eduard and Skretas, George}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {georgeskretas ijcai myown year2023}, pages = {5333--5340}, title = {Minimizing Reachability Times on Temporal Graphs via Shifting Labels}, year = 2023 }

2022

1.
Mertzios, G.B., Michail, O., Skretas, G., Spirakis, P.G., Theofilatos, M.: The Complexity of Growing a Graph. International Symposium on Algorithms and Experiments for Wireless Sensor Networks. pp. 123–137. Springer (2022).
[ BibTeX ] [ DOI ]
 
@inproceedings{mertzios2022complexity, author = {Mertzios, George B and Michail, Othon and Skretas, George and Spirakis, Paul G. and Theofilatos, Michail}, booktitle = {International Symposium on Algorithms and Experiments for Wireless Sensor Networks}, keywords = {georgeskretas myown year2022}, pages = {123-137}, publisher = {Springer}, title = {The Complexity of Growing a Graph}, year = 2022 }

2.
Hacker, P., Naumann, F., Friedrich, T., Grundmann, S., Lehmann, A.: AI Compliance - Challenges of Bridging Data Science and Law. ACM Journal of Data and Information Quality. (2022).
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ]
 
This vision paper outlines the main building blocks of what we term AI Compliance, an effort to bridge two complementary research areas: computer science and the law. Such research has the goal to model, measure, and affect the quality of AI artifacts, such as data, models and applications, to then facilitate adherence to legal standards.
@article{hacker2022compliance, abstract = {This vision paper outlines the main building blocks of what we term AI Compliance, an effort to bridge two complementary research areas: computer science and the law. Such research has the goal to model, measure, and affect the quality of AI artifacts, such as data, models and applications, to then facilitate adherence to legal standards.}, author = {Hacker, Philipp and Naumann, Felix and Friedrich, Tobias and Grundmann, Stefan and Lehmann, Anja}, journal = {ACM Journal of Data and Information Quality}, keywords = {myown tobiasfriedrich}, title = {AI Compliance - Challenges of Bridging Data Science and Law}, year = 2022 }

2019

1.
Cucina, D., Rizzo, M., Ursu, E.: Multiple changepoint detection for periodic autoregressive models with an application to river flow analysis. Stochastic Environmental Research and Risk Assessment. 33, 1137–1157 (2019).
[ Abstract ] [ BibTeX ] [ DOI ]
 
River flow data are usually subject to several sources of discontinuity and inhomogeneity. An example is seasonality, because climatic oscillations occurring on inter-annual timescale have an obvious impact on the river flow. Further sources of alteration can be caused by changes in reservoir management, instrumentation or even unexpected shifts in climatic conditions. When such changes are ignored the results of a statistical analysis can be strongly misleading, so flexible procedures are needed for building the appropriate models, which may be very complex. This paper develops an automatic procedure to estimate the number and locations of changepoints in Periodic AutoRegressive (PAR) models, which have been extensively used to account for seasonality in hydrology. We aim at filling the literature gap on multiple changepoint detection by allowing several time segments to be detected, inside of which a different PAR structure is specified, with the resulting model being employed to successfully capture the discontinuities of river flow data. The model estimation is performed by optimization of an objective function based on an information criterion using genetic algorithms. The proposed methodology is evaluated by means of simulation studies and it is then employed in the analysis of two river flows: the South Saskatchewan, measured at Saskatoon, Canada, and the Colorado, measured at Lees Ferry, Arizona. For these river flows we build changepoint models, discussing the possible events that caused discontinuity, and evaluate their forecasting accuracy. Comparisons with the literature on river flow analysis and on existing methods for changepoint detection confirm the efficiency of our proposal.
@article{cucina2019multiple, abstract = {River flow data are usually subject to several sources of discontinuity and inhomogeneity. An example is seasonality, because climatic oscillations occurring on inter-annual timescale have an obvious impact on the river flow. Further sources of alteration can be caused by changes in reservoir management, instrumentation or even unexpected shifts in climatic conditions. When such changes are ignored the results of a statistical analysis can be strongly misleading, so flexible procedures are needed for building the appropriate models, which may be very complex. This paper develops an automatic procedure to estimate the number and locations of changepoints in Periodic AutoRegressive (PAR) models, which have been extensively used to account for seasonality in hydrology. We aim at filling the literature gap on multiple changepoint detection by allowing several time segments to be detected, inside of which a different PAR structure is specified, with the resulting model being employed to successfully capture the discontinuities of river flow data. The model estimation is performed by optimization of an objective function based on an information criterion using genetic algorithms. The proposed methodology is evaluated by means of simulation studies and it is then employed in the analysis of two river flows: the South Saskatchewan, measured at Saskatoon, Canada, and the Colorado, measured at Lees Ferry, Arizona. For these river flows we build changepoint models, discussing the possible events that caused discontinuity, and evaluate their forecasting accuracy. Comparisons with the literature on river flow analysis and on existing methods for changepoint detection confirm the efficiency of our proposal.}, author = {Cucina, Domenico and Rizzo, Manuel and Ursu, Eugen}, editor = {Springer}, journal = {Stochastic Environmental Research and Risk Assessment}, keywords = {domenicocucina eugenursu manuelrizzo myown serra year2019}, month = {jun}, number = 4, pages = {1137-1157}, title = {Multiple changepoint detection for periodic autoregressive models with an application to river flow analysis}, volume = 33, year = 2019 }

2.
Battaglia, F., Cucina, D., Rizzo, M.: Detection and estimation of additive outliers in seasonal time series. Computational Statistics. 1–17 (2019).
[ Abstract ] [ BibTeX ] [ DOI ]
 
The detection of outliers in a time series is an important issue because their presence may have serious negative effects on the analysis in many different ways. Moreover the presence of a complex seasonal pattern in the series could affect the properties of the usual outlier detection procedures. Therefore modelling the appropriate form of seasonality is a very important step when outliers are present in a seasonal time series. In this paper we present some procedures for detection and estimation of additive outliers when parametric seasonal models, in particular periodic autoregressive, are specified to fit the data. A simulation study is presented to evaluate the benefits and the drawbacks of the proposed procedure on a selection of seasonal time series. An application to three real time series is also examined.
@article{noauthororeditor, abstract = {The detection of outliers in a time series is an important issue because their presence may have serious negative effects on the analysis in many different ways. Moreover the presence of a complex seasonal pattern in the series could affect the properties of the usual outlier detection procedures. Therefore modelling the appropriate form of seasonality is a very important step when outliers are present in a seasonal time series. In this paper we present some procedures for detection and estimation of additive outliers when parametric seasonal models, in particular periodic autoregressive, are specified to fit the data. A simulation study is presented to evaluate the benefits and the drawbacks of the proposed procedure on a selection of seasonal time series. An application to three real time series is also examined.}, author = {Battaglia, Francesco and Cucina, Domenico and Rizzo, Manuel}, journal = {Computational Statistics}, keywords = {domenicocucina francescobattaglia manuelrizzo myown year2019}, pages = {1-17}, title = {Detection and estimation of additive outliers in seasonal time series}, year = 2019 }