In this paper, we shall study a unified framework of robust submodular optimization. We study this problem both from a minimization and maximization perspective (previous work has only focused on variants of robust submodular maximization). We do this under a broad range of combinatorial constraints including cardinality, knapsack, matroid as well as graph based constraints such as cuts, paths, matchings and trees. Furthermore, we also study robust submodular minimization and maximization under multiple submodular upper and lower bound constraints. We show that all these problems are motivated by important machine learning applications including robust data subset selection, robust co-operative cuts and robust co-operative matchings. In each case, we provide scalable approximation algorithms and also study hardness bounds. Finally, we empirically demonstrate the utility of our algorithms on real world applications.
From a minimization perspective, several researchers have studied robust min-max combinatorial optimization (a special case of with modular functions) under different combinatorial constraints (see @cite_32 @cite_16 for a survey). Unfortunately these problems are NP hard even for constraints such as knapsack, s-t cuts, s-t paths, assignments and spanning trees where the standard linear cost problems are poly-time solvable @cite_32 @cite_16 . Moreover, the lower bounds on hardness of approximation is @math ( @math is the number of functions) for s-t cuts, paths and assignments @cite_7 and @math for spanning trees @cite_9 for any @math . For the case when @math is bounded (a constant), fully polynomial time approximation schemes have been proposed for a large class of constraints including s-t paths, knapsack, assignments and spanning trees @cite_24 @cite_52 @cite_16 . From an approximation algorithm perspective, the best known general result is an approximation factor of @math for constraints where the linear function can be exactly optimized in poly-time. For special cases such as spanning trees and shortest paths, one can achieve improved approximation factors of @math @cite_9 @cite_38 and @math Ignores @math factors @cite_8 . -1
@cite_38 @cite_7 @cite_8 @cite_9 @cite_32 @cite_52 @cite_24 @cite_16
2071335627 2886086760 2567804199 2001139415
This paper investigates, for the first time in the literature, the approximation of min–max (regret) versions of classical problems like shortest path, minimum spanning tree, and knapsack. For a constant number of scenarios, we establish fully polynomial-time approximation schemes for the min–max versions of these problems, using relationships between multi-objective and min–max optimization. Using dynamic programming and classical trimming techniques, we construct a fully polynomial-time approximation scheme for min–max regret shortest path. We also establish a fully polynomial-time approximation scheme for min–max regret spanning tree and prove that min–max regret knapsack is not at all approximable. For a non-constant number of scenarios, in which case min–max and min–max regret versions of polynomial-time solvable problems usually become strongly NP-hard, non-approximability results are provided for min–max (regret) versions of shortest path and spanning tree. In this paper the shortest path and the minimum spanning tree problems in a graph with @math nodes and @math cost scenarios (objectives) are discussed. In order to choose a solution the min-max criterion is applied. The minmax versions of both problems are hard to approximate within @math for any @math . The best approximation algorithm for the min-max shortest path problem, known to date, has approximation ratio of @math . On the other hand, for the min-max spanning tree, there is a randomized algorithm with approximation ratio of @math . In this paper a deterministic @math -approximation algorithm for min-max shortest path is constructed. For min-max spanning tree a deterministic @math -approximation algorithm is proposed, which works for a large class of graphs and a randomized @math -approximation algorithm, which can be applied to all graphs, is constructed. It is also shown that the approximation ratios obtained are close to the integrality gaps of the corresponding LP relaxations. An important question in theoretical computer science is to determine the best possible running time for solving a problem at hand. For geometric optimization problems, we often understand their complexity on a rough scale, but not very well on a finer scale. One such example is the two-dimensional knapsack problem for squares. There is a polynomial time (1 + ϵ)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1 ϵ, i.e., Ω(n221 ϵ). A double or triple exponential dependence on 1 ϵ is inherent in how this and several other algorithms for other geometric problems work. In this paper, we present an EPTAS for knapsack for squares, i.e., a (1+ϵ)-approximation algorithm with a running time of Oϵ(1)·nO(1). In particular, the exponent of n in the running time does not depend on ϵ at all! Since there can be no FPTAS for the problem (unless P = NP) this is the best kind of approximation scheme we can hope for. To achieve this improvement, we introduce two new key ideas: We present a fast method to guess the Ω(221 ϵ) relatively large squares of a suitable near-optimal packing instead of using brute-force enumeration. Secondly, we introduce an indirect guessing framework to define sizes of cells for the remaining squares. In the previous PTAS each of these steps needs a running time of Ω(n221 ϵ) and we improve both to Oϵ(1) · nO(1). We complete our result by giving an algorithm for two-dimensional knapsack for rectangles under (1 + ϵ)-resource augmentation. In this setting, we also improve the best known running time of Ω(n1 ϵ1 ϵ) to Oϵ(1) · nO(1) and compute even a solution with optimal profit, in contrast to the best previously known polynomial time algorithm for this setting that computes only an approximation. We believe that our new techniques have the potential to be useful for other settings as well. We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum-cost spanning tree, minimum-weight perfect matching, traveling salesman and Steiner tree problems. Our technique produces approximation algorithms that run in @math time and come within a factor of 2 of optimal for most of these problems. For instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. Our running time of @math time compares favorably with the best strongly polynomial exact algorithms running in @math time for dense graphs. A similar result is obtained for the 2-matching problem and its variants. We also derive the first approximation algorithms for many NP-complete problems, including the non-fixed point-to-point connection problem, the exact path partitioning problem and complex location-design problems. Moreover, for the prize-collecting traveling salesman or Steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [Math. Programming, 59 (1993), pp. 413--420].