Skip to main content

Research Repository

Advanced Search

Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty

Bampis, Evripidis; Dürr, Christoph; Erlebach, Thomas; de Lima, Murilo Santos; Megow, Nicole; Schlöter, Jens

Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty Thumbnail


Authors

Evripidis Bampis

Christoph Dürr

Murilo Santos de Lima

Nicole Megow

Jens Schlöter



Abstract

Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node with minimum weight can be determined for each hyperedge. Querying a node has a cost and reveals the precise weight of the node, drawn from the given probability distribution. Using competitive analysis, we compare the expected query cost of an algorithm with the expected cost of an optimal query set for the given instance. For the general case, we give a polynomial-time f(α)-competitive algorithm, where f(α) ∈ [1.618+ε,2] depends on the approximation ratio α for an underlying vertex cover problem. We also show that no algorithm using a similar approach can be better than 1.5-competitive. Furthermore, we give polynomial-time 4/3-competitive algorithms for bipartite graphs with arbitrary query costs and for hypergraphs with a single hyperedge and uniform query costs, with matching lower bounds.

Citation

Bampis, E., Dürr, C., Erlebach, T., de Lima, M. S., Megow, N., & Schlöter, J. (2021). Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty. . https://doi.org/10.4230/lipics.esa.2021.10

Conference Name 29th Annual European Symposium on Algorithms (ESA 2021)
Conference Location Lisbon, Portugal (Virtual Conference)
Acceptance Date Jun 23, 2021
Online Publication Date Aug 31, 2021
Publication Date 2021
Deposit Date Dec 30, 2021
Publicly Available Date Mar 29, 2024
Publisher Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume 204
Pages 10:1-10:18
Series Title LIPIcs
DOI https://doi.org/10.4230/lipics.esa.2021.10

Files

Published Conference Proceeding (770 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
© Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and
Jens Schlöter;
licensed under Creative Commons License CC-BY 4.0
29th Annual European Symposium on Algorithms (ESA 2021).
Editors: Petra Mutzel, Rasmus Pagh, and Grzegorz Herman; Article No. 10; pp. 10:1–10:18
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany





You might also like



Downloadable Citations