Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms

• URL: http://arxiv.org/abs/2006.12773v2
• Date: Tue, 8 Sep 2020 06:31:59 GMT
• Title: Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms
• Authors: Anh Viet Do, Frank Neumann
• Abstract summary: A simple evolutionary algorithm called GSEMO has been shown to achieve good approximation for submodular functions efficiently. We extend theoretical results to partition matroid constraints which generalize cardinality constraints.
• Score: 16.691265882753346
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many important problems can be regarded as maximizing submodular functions under some constraints. A simple multi-objective evolutionary algorithm called GSEMO has been shown to achieve good approximation for submodular functions efficiently. While there have been many studies on the subject, most of existing run-time analyses for GSEMO assume a single cardinality constraint. In this work, we extend the theoretical results to partition matroid constraints which generalize cardinality constraints, and show that GSEMO can generally guarantee good approximation performance within polynomial expected run time. Furthermore, we conducted experimental comparison against a baseline GREEDY algorithm in maximizing undirected graph cuts on random graphs, under various partition matroid constraints. The results show GSEMO tends to outperform GREEDY in quadratic run time.

Related papers

• Sliding Window Bi-Objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular Functions [10.506038775815094]
  In this paper, we apply the sliding-selection approach introduced in [21] to the optimization of chance-constrained monotone submodular functions. We show that the SW-GSEMO algorithm successfully limits the population size as a key factor that impacts the runtime.
  arXiv  Detail & Related papers  (2024-07-13T00:28:29Z)
• Submodular Maximization under the Intersection of Matroid and Knapsack Constraints [23.0838604893412]
  We consider the problem of submodular operations under the intersection of two commonly used constraints, i.e., $k$matroid constraint and $m$-knapsack constraint. We prove that SPROUTOUT can achieve a SPR-time approximation guarantee better than incorporating state-of-the-art algorithms. Experiments on the applications of movie recommendation and weighted max-cut demonstrate the superiority of SPROUT++ in practice.
  arXiv  Detail & Related papers  (2023-07-18T02:37:14Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm. We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
  arXiv  Detail & Related papers  (2022-09-15T07:22:58Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  Minimax problems extend beyond the continuous domain to mixed continuous-discrete domains or even fully discrete domains. We introduce the class of convex-submodular minimax problems, where the objective is convex with respect to the continuous variable and submodular with respect to the discrete variable. Our proposed algorithms are iterative and combine tools from both discrete and continuous optimization.
  arXiv  Detail & Related papers  (2021-11-01T21:06:35Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences [44.11102526976392]
  This paper studies the problem class of maximizing monotone submodular functions over sequences. EAs can achieve good approximation guarantees for solving the problem classes of submodular optimization. Empirical studies on various applications, e.g., accomplishing tasks, maximizing information gain, search-and-tracking and recommender systems, show the excellent performance of the GSEMO.
  arXiv  Detail & Related papers  (2021-04-20T10:36:10Z)
• Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms [11.807734722701786]
  Here the constraint involves components and the constraint can only be violated with a small probability of alpha. We show that the algorithm GSEMO obtains the same worst case performance guarantees for monotone submodular functions. Our experimental results show that the use of evolutionary multi-objective algorithms leads to significant performance improvements.
  arXiv  Detail & Related papers  (2020-06-20T00:17:44Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.