检索结果-内蒙古大学图书馆

Maximizing submodular functions under Matroid Constraints by Evolutionary Algorithms

EVOLUTIONARY COMPUTATION 2015年第4期23卷 543-558页

作者： Friedrich, Tobias Neumann, Frank Hasso Plattner Inst Potsdam Germany Univ Adelaide Sch Comp Sci Adelaide SA 5005 Australia

Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function f under a given set of constraints. In this paper, we investigate the runtime of a simple single objective evolutionary algorithm called (1 + 1) EA and a multiobjective evolutionary algorithm called GSEMO until they have obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints, we show that theGSEMOachieves a (1 - 1/e)-approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of k >= 2 matroids, we show that the (1 + 1) EA achieves a (1/k + delta)- approximation in expected polynomial time for any constant delta > 0. Turning to nonmonotone symmetric submodular functions with k >= 1 matroid intersection constraints, we show that the GSEMO achieves a 1/((k + 2)(1 + epsilon))-approximation in expected time O(n(k+6) log(n)/epsilon).

关键词： submodular functions matroid constraints approximation multiobjective optimization hypervolume indicator maximum cut runtime theory

来源：评论

学校读者我要写书评

暂无评论

Maximizing monotone submodular functions over the integer lattice

引用

MATHEMATICAL PROGRAMMING 2018年第1-2期172卷 539-563页

作者： Soma, Tasuku Yoshida, Yuichi Univ Tokyo Grad Sch Informat Sci & Technol Tokyo Japan Natl Inst Informat Tokyo Japan

The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a nonnegative monotone submodular function f : Zn +. R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time (1 -1/ e -)-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a (1-1/ e -)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property.

关键词： submodular functions Integer lattice DR-submodular functions

来源：评论

学校读者我要写书评

暂无评论

Maximization of submodular functions: Theory and enumeration algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第1期198卷 102-112页

作者： Goldengorin, Boris Univ Groningen Dept Operat NL-9700 AV Groningen Netherlands

submodular functions are powerful tools to model and solve either to optimality or approximately many operational research problems including problems defined on graphs. After reviewing some long-standing theoretical results about the structure of local and global maxima of submodular functions, Cherenin's selection rules and his Dichotomy Algorithm, we revise the above mentioned theory and show that our revision is useful for creating new non-binary branching algorithms and finding either approximation solutions with guaranteed accuracy or exact ones. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Maximization submodular functions Enumeration algorithms

来源：评论

学校读者我要写书评

暂无评论

Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations

引用

NATURAL COMPUTING 2021年第3期20卷 561-575页

作者： Quinzan, Francesco Goebel, Andreas Wagner, Markus Friedrich, Tobias Univ Potsdam Hasso Plattner Inst Potsdam Germany Univ Adelaide Adelaide SA Australia

A core operator of evolutionary algorithms (EAs) is the mutation. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this area of work, we propose a new mutation operator and analyze its performance on the (1 + 1) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the (1 + 1) EA on classes of problems for which results on the other mutation operators are available. We show that the (1 + 1) EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. We also consider the problem of maximizing a symmetric submodular function under a single matroid constraint and show that the (1 + 1) EA using our operator finds a (1/3)-approximation within polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve these problems and outperforms them with constant probability. Finally, we evaluate the performance of the (1 + 1) EA using our operator experimentally by considering two applications: (a) the maximum directed cut problem on real-world graphs of different origins, with up to 6.6 million vertices and 56 million edges and (b) the symmetric mutual information problem using a four month period air pollution data set. In comparison with uniform mutation and a recently proposed dynamic scheme, our operator comes out on top on these instances.

关键词： Evolutionary algorithms Mutation operators submodular functions Matroids

来源：评论

学校读者我要写书评

暂无评论

STRUCTURES OF POLYHEDRA DETERMINED BY submodular functions ON CROSSING FAMILIES

引用

MATHEMATICAL PROGRAMMING 1984年第2期29卷 125-141页

作者： FUJISHIGE, S Institute of Socio-Economic Planning University of Tsukuba 305 Sakura Ibaraki Japan

The present paper shows that for any submodular functionf on a crossing family with, if the polyhedron is nonempty, then there exist a unique distributive lattice with and a unique submodular function with such thatB(f) coincides with the base polyhedron associated with the submodular system. Here, iff is integer-valued, thenf 1 is also *** on this fact, we also show the relationship between the independent-flow problem considered by the author and the minimum cost flow problem considered by J. Edmonds and R. Giles.

关键词： submodular functions Crossing Families Base Polyhedra

来源：评论

学校读者我要写书评

暂无评论

THEORY OF submodular PROGRAMS - A FENCHEL-TYPE MIN MAX THEOREM AND SUBGRADIENTS OF submodular functions

引用

MATHEMATICAL PROGRAMMING 1984年第2期29卷 142-155页

作者： FUJISHIGE, S Institute of Socio-Economic Planning University of Tsukuba 305 Sakura Ibaraki Japan

We consider submodular programs which are problems of minimizing submodular functions on distributive lattices with or without constraints. We define a convex (or concave) conjugate function of a submodular (or supermodular) function and show a Fenchel-type min-max theorem for submodular and supermodular functions. We also define a subgradient of a submodular function and derive a necessary and sufficient condition for a feasible solution of a submodular program to be optimal, which is a counterpart of the Karush-Kuhn-Tucker condition for convex programs.

关键词： submodular functions Supermodular functions Subgradients Fenchel's Duality Theorem Karush-Kuhn-Tucker Condition

来源：评论

学校读者我要写书评

暂无评论

Min-Max Partitioning of Hypergraphs and Symmetric submodular functions

引用

COMBINATORICA 2023年第3期43卷 455-477页

作者： Chandrasekaran, Karthekeyan Chekuri, Chandra Univ Illinois Urbana IL 61820 USA

We consider the complexity of minmax partitioning of graphs, hypergraphs and (symmetric) submodular functions. Our main result is an algorithm for the problem of partitioning the ground set of a given symmetric sub modular functionf:2(V)?Rintoknon-empty partsV(1),V-2,...,V-k to minimize max(i)(k)=1f(V-i). Our algorithm runsinn(O)(k(2))Ttime, wheren=|V|andTis the time to evaluatefon a given set;hence,this yields a polynomial time algorithm for any fixedkin the evaluation oracle *** an immediate corollary, for any fixedk, there is a polynomial-time algorithm forthe problem of partitioning a given hypergraphH=(V,E)intoknon-empty partsto minimize the maximum capacity of the parts. The complexity of this problem,termedMinmax- Hypergraph-k-Part, was raised by Lawler in 1973 (Networks3:275-285, 1973). In contrast to our positive result, the reduction in Chekuri and Li(Theory Comput 16(14):1-8, 2020) implies that whenkis part of the input,Minmax-Hypergraph-k-Partis hard to approximate to within an almost polynomial factorunder the Exponential Time Hypothesis (ETH)

关键词： Hypergraphs submodular functions Partitioning

来源：评论

学校读者我要写书评

暂无评论

Improving graph partitions using submodular functions

引用

DISCRETE APPLIED MATHEMATICS 2003年第2期131卷 535-553页

作者： Patkar, SB Narayanan, H Indian Inst Technol Dept Math Bombay 400076 Maharashtra India Indian Inst Technol Dept Elect Engn Bombay 400076 Maharashtra India

We investigate into the role of submodular functions in designing new heuristics and approximate algorithms to some NP-hard problems arising in the field of VLSI Design Automation. In particular, we design and implement efficient heuristic for improving a bipartition of a graph in the sense of ratioCut (Discrete Appl. Math. 90 (1999) 3;29th Annual Symposium on Foundations of Computer Science, 1988, p. 422). We also design an approximate algorithm for another NP-hard problem which is a dual of the well-known NP-hard problem of finding a densest k-subgraph of a graph (see J. Algorithms 34 (2000) 203;Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993, p. 692). Our algorithms are based on submodular function and are implementable in polynomial time using efficient network flow based subroutines. To the best of our knowledge our algorithms are the first ones to use submodular functions based approach for the problems considered here. We also describe the experimental results which provide the evidence of our heuristic for improving the ratioCut. (C) 2002 Elsevier B.V. All rights reserved.

关键词： submodular functions VERY large scale integration of circuits ALGORITHMS BIPARTITE graphs

来源：评论

学校读者我要写书评

暂无评论

Improved Streaming Algorithms for Maximizing Monotone submodular functions Under a Knapsack Constraint 16th

Improved Streaming Algorithms for Maximizing Monotone Submod...

引用

16th International Algorithms and Data Structures Symposium (WADS)

作者： Huang, Chien-Chung Kakimura, Naonori Ecole Normale Super CNRS Paris France Keio Univ Yokohama Kanagawa Japan

ISBN: (纸本)9783030247669;9783030247652

In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a (0.4 - epsilon)-approximation algorithm requiring only a single pass through the data. This improves on the currently best (0.363 - epsilon)-approximation algorithm. The required memory space depends only on the size of the knapsack capacity and e.

关键词： submodular functions Streaming algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration Problems on submodular functions 22

Reconfiguration Problems on Submodular Functions

引用

15th ACM International Conference on Web Search and Data Mining (WSDM)

作者： Ohsaka, Naoto Matsuoka, Tatsuya NEC Corp Ltd Tokyo Japan

ISBN: (纸本)9781450391320

Reconfiguration problems require finding a step-by-step transformation between a pair of feasible solutions for a particular problem. The primary concern in Theoretical Computer Science has been revealing their computational complexity for classical problems. This paper presents an initial study on reconfiguration problems derived from a submodular function, which has more of a flavor of Data Mining. Our submodular reconfiguration problems request to find a solution sequence connecting two input solutions such that each solution has an objective value above a threshold in a submodular function f : 2([n]) -> R+ and is obtained from the previous one by applying a simple transformation rule. We formulate three reconfiguration problems: Monotone submodular Reconfiguration (MSReco), which applies to influence maximization, and two versions of Unconstrained submodular Reconfiguration (USReco), which apply to determinantal point processes. Our contributions are summarized as follows: We prove that MSReco and USReco are both PSPACE-complete. We design a 1/2-approximation algorithm for MSReco and a 1/n-approximation algorithm for (one version of) USReco. We devise inapproximability results that approximating the optimum value of MSReco within a (1-1+epsilon/m(2))-factor is PSPACE-hard, and we cannot find a (5/6 + epsilon)-approximation for USReco. We conduct numerical study on the reconfiguration version of influence maximization and determinantal point processes using real-world social network and movie rating data.

关键词： reconfiguration submodular functions approximation algorithms influence maximization determinantal point processes

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：