2026-07-22T01:18:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14591 2024-03-06T10:54:23Z ddc:004 open_access

Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty Bampis, Evripidis Dürr, Christoph Erlebach, Thomas de Lima, Murilo Santos Megow, Nicole Schlöter, Jens Explorable uncertainty queries stochastic optimization graph orientation selection problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Evripidis Bampis and Christoph Dürr and Thomas Erlebach and Murilo Santos de Lima and Nicole Megow and Jens Schlöter 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.10 urn:nbn:de:0030-drops-145910 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.10 eng https://creativecommons.org/licenses/by/4.0/legalcode