In this paper we look at the classical set-maxima problem. We give a new result using a sparse lattice of subsets. We then extend this to a geometric setting. Let @math be a set of @math points in a plane and @math be a set of convex regions. Let a key value be assigned to each point. The problems is to determine for each convex region of @math the point having the largest key. We give a parameterized result for the comparison complexity.
@cite_4 showed that this can be generalized using weighted matroids. One of the canonical examples of matroids is the graphic matroid. Generalized to binary matroids (since graphic matroids are also regular) this has been termed by Liberatore as the fundamental path maxima problem over such matroids. A cographic matroid is a dual of a graphic matroid. For a cographic matroid the problem can be solved in @math ( @cite_3 ) comparisons. Liberatore generalized these results to a restricted class of matroids that can be constructed via direct-sums and 2-sums and gave a @math -comparison algorithm ( @cite_4 ). @cite_0 proposed an algorithm that chose a rank sequence randomly. They show that the expected number of comparisons in their algorithm is @math which is optimal according to the comparison tree complexity. The randomized algorithm can solve a more general problem of computing the largest @math elements for each subset @math .
@cite_0 @cite_4 @cite_3
2011193572 2774807875 2089729462 2022013502
Abstract For the problem maxlcub; Z ( S ): S is an independent set in the matroid X rcub;, it is well-known that the greedy algorithm finds an optimal solution when Z is an additive set function (Rado-Edmonds theorem). Fisher, Nemhauser and Wolsey have shown that, when Z is a nondecreasing submodular set function satisfying Z (∅)=0, the greedy algorithm finds a solution with value at least half the optimum value. In this paper we show that it finds a solution with value at least 1 (1 + α) times the optimum value, where α is a parameter which represents the ‘total curvature’ of Z . This parameter satisfies 0≤α≤1 and α=0 if and only if the set function Z is additive. Thus the theorems of Rado-Edmonds and Fisher-Nemhauser-Wolsey are both contained in the bound 1 (1 + α). We show that this bound is best possible in terms of α. Another bound which generalizes the Rado-Edmonds theorem is given in terms of a ‘greedy curvature’ of the set function. Unlike the first bound, this bound can prove the optimality of the greedy algorithm even in instances where Z is not additive. A third bound, in terms of the rank and the girth of X , unifies and generalizes the bounds (e−1) e known for uniform matroids and 1 2 for general matroids. We also analyze the performance of the greedy algorithm when X is an independence system instead of a matroid. Then we derive two bounds, both tight: The first one is [1−(1−α K ) k ] α where K and k are the sizes of the largest and smallest maximal independent sets in X respectively; the second one is 1 ( p +α) where p is the minimum number of matroids that must be intersected to obtain X . Consider a setting where robots must visit sites represented as nodes in a graph, but each robot may fail when traversing an edge. The goal is to find a set of paths for a team of robots which maximizes the expected number of nodes collectively visited, while guaranteeing that the paths satisfy a notion of “independence” formalized by a matroid (e.g. limits on team size, number of visits to regions), and that the probabilities that each robot survives to its destination are above a given threshold. We call this problem the Matroid Team Surviving Orienteers (MTSO) problem, which has broad applications such as environmental monitoring in risky regions and search and rescue in dangerous conditions. We present the MTSO formally and detail numerous examples of matroids in a path planning context. We then propose an approximate greedy algorithm for selecting a feasible set of paths and prove that the value of the output is within a factor p s p s + λ of the optimum, where p s is the per-robot survival probability threshold and 1 λ ≤ 1 is the approximation factor of an oracle routine for the well known orienteering problem. We demonstrate the efficiency of our approach by applying it to a scenario where a team of robots must gather information while avoiding pirates in the Coral Triangle. A number of recent results on optimization problems involving submodular functions have made use of the "multilinear relaxation" of the problem. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of "symmetry gap". Our main result is that for any fixed instance that exhibits a certain "symmetry gap" in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, e.g. the optimality of (1-1 e)-approximation for monotone submodular maximization under a cardinality constraint, and the impossibility of (1 2+epsilon)-approximation for unconstrained (non-monotone) submodular maximization. It follows from our result that (1 2+epsilon)-approximation is also impossible for non-monotone submodular maximization subject to a (non-trivial) matroid constraint. On the algorithmic side, we present a 0.309-approximation for this problem, improving the previously known factor of 1 4-o(1).As another application, we consider the problem of maximizing a non-monotone submodular function over the bases of a matroid. A (1 6-o(1))-approximation has been developed for this problem, assuming that the matroid contains two disjoint bases. We show that the best approximation one can achieve is indeed related to packings of bases in the matroid. Specifically, for any k≫=2, there is a class of matroids of fractional base packing number nu = k (k-1), such that any algorithm achieving a better than (1-1 nu)-approximation for this class would require exponentially many value queries. On the positive side, we present a 1 2 (1-1 nu-o(1))-approximation algorithm for the same problem. Our hardness results hold in fact for very special symmetric instances. For such symmetric instances, we show that the approximation factors of 1 2 (for submodular maximization subject to a matroid constraint) and 1-1 nu (for a matroid base constraint) can be achieved algorithmically and hence are optimal. We study a generalization of the classical secretary problem which we call the "matroid secretary problem". In this problem, the elements of a matroid are presented to an online algorithm in random order. When an element arrives, the algorithm observes its value and must make an irrevocable decision regarding whether or not to accept it. The accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. This paper presents an O(log k)-competitive algorithm for general matroids (where k is the rank of the matroid), and constant-competitive algorithms for several special cases including graphic matroids, truncated partition matroids, and bounded degree transversal matroids. We leave as an open question the existence of constant-competitive algorithms for general matroids. Our results have applications in welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid.