ACUTE (Algorithms for Computing with Uncertainty - Theory and Experiments) is an EPSRC-funded project that investigates algorithms for computing with uncertainty. The project has started on 1st November 2019 and ended on 31 October 2023.

People

Investigator

• Thomas Erlebach, Durham University (PI)

• Amitabh Trehan, Durham University (Co-I, since August 2022)

Post-Doc

• Konstantinos Dogeas (September 2022 - October 2023)

Visiting Researchers and Collaborators

• Evripidis Bampis, Sorbonne Université, Paris

• Christoph Dürr, Sorbonne Université, Paris

• Nicole Megow, University of Bremen

• Jens Schlöter, University of Bremen

Ex-Staff

• Michael Hoffmann, University of Leicester (co-PI, until June 2021)

• Murilo Santos de Lima (post-doc, until April 2021)

Project Summary

How much information should we collect before making a decision? This question underlies the research area of computing with explorable uncertainty. For example, assume that we want to build a network connecting a set of branch offices. For any two locations A and B of branch offices, we have an estimate of the cost for building a link between A and B based on the distance between them. The exact cost of building a link between A and B can be determined by further investigations, but these investigations take time and cost money. If we knew the exact link cost for every pair of locations, we could determine the cheapest way of building the network using a known algorithm for the "minimum spanning tree" problem. The approach of first determining for all pairs of locations the exact cost of building a link between them is not efficient, however: It will take a long time to determine all the exact link costs, and the costs for obtaining that information will be significant. It is therefore desirable to find efficient methods for selecting in a clever way the pairs of locations for which the link costs need to be determined, while still achieving the goal of being able to build a cheap network with the information gained. Algorithms for computing with explorable uncertainty solve such problems: They specify a strategy for selecting the pairs of locations for which exact information should be determined until sufficient information has been gained to determine the best possible network to be built. More generally, computing with explorable uncertainty deals with problems where part of the input is uncertain (known only approximately) but can be obtained at a cost using a query operation.

Previous work on computing with uncertainty has focused on the setting where queries are made one by one sequentially (which may take a long time) and where the goal is to make as few queries as possible while ensuring that sufficient information is obtained to solve the problem optimally. This leaves open the question of how the queries should be selected if a number of queries can be made at the same time in parallel, which is realistic in many applications (for example, in the application outlines above, the exact costs of building links between several pairs of branch office locations could be determined in parallel). Another direction that has not yet been sufficiently considered is the setting where the goal is to optimize a combination of the query cost and the cost of the solution determine in the end. The project aims to take research in computing with explorable uncertainty to the next level by addressing these open questions and developing new algorithms that work provably well in the described scenarios. Methods developed in the project can potentially be useful to any decision-making scenarios where additional information about the input data of a problem is available in principle and can be obtained at a cost.

Funder

ACUTE is funded by EPSRC (EP/S033483/1: 01/11/2019-19/09/2021, EP/S033483/2: 20/09/2021-31/10/2023).

Publications

1. Christoph Dürr, Thomas Erlebach, Nicole Megow and Julie Meißner: An Adversarial Model for Scheduling with Testing. Algorithmica 82:3630-3675, 2020. Available online since 10 July 2020. DOI: http://doi.org/10.1007/s00453-020-00742-2
   Also: arXiv:1709.02592 [cs.DS]

2. Steven Chaplick, Magnús M. Halldórsson, Murilo Santos de Lima, Tigran Tonoyan: Query Minimization Under Stochastic Uncertainty. LATIN 2020, LNCS 12118, Springer, pp. 181-193. DOI: https://doi.org/10.1007/978-3-030-61792-9_15

3. Thomas Erlebach: Algorithms that Access the Input via Queries. SOFSEM 2021, LNCS 12607, Springer, pp. 3-12. DOI: https://doi.org/10.1007/978-3-030-67731-2_1 (Invited)

4. Steven Chaplick, Magnús M. Halldórsson, Murilo S. de Lima, Tigran Tonoyan: Query minimization under stochastic uncertainty. Theor. Comput. Sci. 895: 75-95, 2021. DOI: https://doi.org/10.1016/j.tcs.2021.09.032
   Also: arXiv:2010.03517 [cs.DS]

5. Thomas Erlebach, Michael Hoffmann, Murilo S. de Lima: Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries. In: Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Saarland Informatics Campus, Saarbrücken, Germany, March 16-19, 2021. LIPIcs 117, 27:1-27:18, 2021. DOI: https://doi.org/10.4230/LIPIcs.STACS.2021.27
   Also: arXiv:2101.05032 [cs.DS]

6. Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter: Orienting (hyper)graphs under explorable stochastic uncertainty. In: Proceedings of the 29th Annual European Symposium on Algorithms (ESA 2021), Lisbon, Portugal, September 6-8, 2021. LIPIcs 204, 10:1--10:18, 2021. DOI: https://doi.org/10.4230/LIPIcs.ESA.2021.10
   Also: arXiv:2107.00572 [cs.DS]

7. Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter: Learning-Augmented Query Policies. arXiv:2011.07385 [cs.DS]

8. Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter: Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty.  In: Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022), Potsdam, Germany, September 5-7, 2022. LIPIcs 244, pp. 49:1--49:18, 2022. DOI: https://doi.org/10.4230/LIPIcs.ESA.2022.49
   Also: https://arxiv.org/abs/2206.15201 [cs.DS]

9. Thomas Erlebach, Michael Hoffmann, Murilo S. de Lima: Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries. Algorithmica, 15 September 2022. DOI: https://doi.org/10.1007/s00453-022-01035-6

10. Thomas Erlebach, Murilo de Lima, Nicole Megow, Jens Schlöter: Sorting and Hypergraph Orientation under Uncertainty with Predictions. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI 2023), Macao, SAR, China, pp. 5577-5585, 2023. DOI: https://doi.org/10.24963/ijcai.2023/619

11. Konstantinos Dogeas, Thomas Erlebach, Ya-Chun Liang: Scheduling with Obligatory Tests. In: 32nd Annual European Symposium on Algorithms (ESA 2024). To appear.
    Also: https://arxiv.org/abs/2406.16734 [cs.DS]

12. Evripidis Bampis, Konstantinos Dogeas, Thomas Erlebach, Nichole Megow, Jens Schlöter, Amitabh Trehan:  Competitive Query Minimization for Stable Matching with One-Sided Uncertainty. In:   International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024). To appear.
    Also: http://arxiv.org/abs/2407.10170 [cs.DS]

Background

A survey of known results on computing with uncertainty (until 2015) can be found here:

• Thomas Erlebach, Michael Hoffmann: Query-Competitive Algorithms for Computing with Uncertainty. Bulletin of the EATCS 116 (2015).