Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Orienting (hyper)graphs under explorable stochastic uncertainty   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(\alpha)$-competitive algorithm, where $f(\alpha)\in
[1.618+\epsilon,2]$ depends on the approximation ratio $\alpha$ 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.

9
The categories of this paper are: nlin
21
The categories of this paper are: adap-org
36
The categories of this paper are: cmp-lg
8
The categories of this paper are: hep-ex
28
The categories of this paper are: alg-geom
11
The categories of this paper are: hep-lat
23
The categories of this paper are: solv-int
16
The categories of this paper are: stat
12
The categories of this paper are: nucl-th
18
The categories of this paper are: econ
19
The categories of this paper are: eess
2
The categories of this paper are: math
31
The categories of this paper are: ao-sci
24
The categories of this paper are: dg-ga
14
The categories of this paper are: math-ph
37
The categories of this paper are: supr-con