We consider the problem of maximizing a monotone submodular function under noise. There has been a great deal of work on optimization of submodular functions under various constraints, resulting in algorithms that provide desirable approximation guarantees. In many applications, however, we do not have access to the submodular function we aim to optimize, but rather to some erroneous or noisy version of it. This raises the question of whether provable guarantees are obtainable in presence of error and noise. We provide initial answers, by focusing on the question of maximizing a monotone submodular function under a cardinality constraint when given access to a noisy oracle of the function. We show that: - For a cardinality constraint @math , there is an approximation algorithm whose approximation ratio is arbitrarily close to @math ; - For @math there is an algorithm whose approximation ratio is arbitrarily close to @math . No randomized algorithm can obtain an approximation ratio better than @math ; -If the noise is adversarial, no non-trivial approximation guarantee can be obtained.
Combinatorial optimization with noisy inputs can be largely studied through consistent (independent noisy answers when querying the oracle twice) and inconsistent oracles. For inconsistent oracles, it usually suffices to repeat every query @math times, and eliminate the noise. To the best of our knowledge, submodular optimization has been studied under noise only in instances where the oracle is inconsistent or equivalently small enough so that it does not affect the optimization @cite_43 @cite_3 . One line of work studies methods for reducing the number of samples required for optimization (see e.g. @cite_1 @cite_5 ), primarily for sorting and finding elements. On the other hand, if two identical queries to the oracle always yield the same result, the noise can not be averaged out so easily, and one needs to settle for approximate solutions, which has been studied in the context of tournaments and rankings @cite_54 @cite_71 @cite_56 .
@cite_54 @cite_1 @cite_3 @cite_56 @cite_43 @cite_71 @cite_5
1986978101 2038435918 1566959760 2952149393 2111790732
We present a polynomial time approximation scheme (PTAS) for the minimum feedback arc set problem on tournaments. A simple weighted generalization gives a PTAS for Kemeny-Young rank aggregation. This paper studies the depth of noisy decision trees in which each node gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tight bounds are given on the number of queries to input variables required to compute threshold functions, the parity function and symmetric functions. In the noisy comparison tree model, tight bounds are given on the number of noisy comparisons for searching, sorting, selection and merging. The paper also studies parallel selection and sorting with noisy comparisons, giving tight bounds for several problems. Many set functionsF in combinatorial optimization satisfy the diminishing returns propertyF (A[fXg) F (A) F (A 0 [fXg) F (A 0 ) forA A In this paper we study noisy sorting without re-sampling. In this problem there is an unknown order @math for all pairs @math , where @math is a constant and @math for all @math and @math . It is assumed that the errors are independent. Given the status of the queries the goal is to find the maximum likelihood order. In other words, the goal is find a permutation @math that minimizes the number of pairs @math where @math . The problem so defined is the feedback arc set problem on distributions of inputs, each of which is a tournament obtained as a noisy perturbations of a linear order. Note that when @math and @math is large, it is impossible to recover the original order @math . It is known that the weighted feedback are set problem on tournaments is NP-hard in general. Here we present an algorithm of running time @math and sampling complexity @math that with high probability solves the noisy sorting without re-sampling problem. We also show that if @math is an optimal solution of the problem then it is close'' to the original order. More formally, with high probability it holds that @math and @math . Our results are of interest in applications to ranking, such as ranking in sports, or ranking of search items based on comparisons by experts. We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants:1. Each comparison is erroneous with independent probability 1-p. 2. At each stage k comparisons can be performed in parallel and a noisy answer is returned. We present a (classical) algorithm which solves both variants optimally (with respect to p and k), up to an additive term of O(loglog n), and prove matching information-theoretic lower bounds. We use the algorithm to improve the results of , presenting an exact quantum search algorithm in an ordered list of expected complexity less than (log2 n) 3.