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

A Note on submodular function minimization with Covering Type Linear Constraints

ALGORITHMICA 2018年第10期80卷 2957-2971页

作者： Kamiyama, Naoyuki Kyushu Univ Inst Math Ind Fukuoka Japan JST PRESTO Kawaguchi Saitama Japan

In this paper, we consider the non-negative submodular function minimization problem with covering type linear constraints. Assume that there exist m linear constraints, and we denote by the number of non-zero coefficients in the ith constraints. Furthermore, we assume that . For this problem, Koufogiannakis and Young proposed a polynomial-time -approximation algorithm. In this paper, we propose a new polynomial-time primal-dual approximation algorithm based on the approximation algorithm of Takazawa and Mizuno for the covering integer program with -variables and the approximation algorithm of Iwata and Nagano for the submodular function minimization problem with set covering constraints. The approximation ratio of our algorithm is , where is the maximum size of a connected component of the input submodular function.

关键词： submodular function minimization Primal-dual approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A note on submodular function minimization by Chubanov's LP algorithm

引用

DISCRETE OPTIMIZATION 2019年 33卷 140-145页

作者： Fujishige, Satoru Kyoto Univ Res Inst Math Sci Kyoto 6068502 Japan

Recently Dadush et al. (2017) have devised a polynomial submodular function minimization (SFM) algorithm based on their LP algorithm. In the present note we also show a weakly polynomial algorithm for SFM based on the recently developed linear programming feasibility algorithm of Chubanov (2017) to stimulate further research on SFM. (C) 2019 Elsevier B.V. All rights reserved.

关键词： submodular function minimization Base polyhedra Chubanov's algorithm

来源：评论

学校读者我要写书评

暂无评论

Hypergraphic submodular function minimization

引用

DISCRETE MATHEMATICS 2013年第22期313卷 2650-2655页

作者： Miklos, Zoltan Eotvos Lorand Univ Dept Operat Res ELTE Egervary Res Grp Pazmany Peter Setany 1-C H-1117 Budapest Hungary

We generalize the results of Angles d'Auriac, Igloi, Preissmann and Sebo [1,6] concerning graphic submodular function minimization. They use a subroutine due to Padberg and Wolsey (1983) [5] that cannot be adapted to hypergraphs. Instead of their approach we consider fractional orientations and the push-relabel method Goldberg and Tarjan (1988) [4]. The complexity of the resulting algorithm in a hypergraph is O(n(4) + n(3)m), where n, m are the number of nodes and hyperedges, respectively. (C) 2013 Elsevier B.V. All rights reserved.

关键词： submodular function minimization Push-relabel method

来源：评论

学校读者我要写书评

暂无评论

Sparse submodular function minimization 64

Sparse Submodular Function Minimization

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Graur, Andrei Jiang, Haotian Sidford, Aaron Stanford Univ Management Sci & Engn Stanford CA 94305 USA Microsoft Res Redmond WA USA

ISBN: (纸本)9798350318944

In this paper we study the problem of minimizing a submodular function f : 2(V) -> R that is guaranteed to have a k-sparse minimizer. We give a deterministic algorithm that computes an additive epsilon-approximate minimizer of such f in (O) over tilde (poly(k) log(|f|/epsilon) parallel depth using a polynomial number of queries to an evaluation oracle of f, where |f| = max(S subset of V) |f(S)|. Further, we give a randomized algorithm that computes an exact minimizer of f with high probability using (O) over tilde(|V|.poly(k)) queries and polynomial time. When k = (O) over tilde (1), our algorithms use either nearly-constant parallel depth or a nearly-linear number of evaluation oracle queries. All previous algorithms for this problem either use delta(|V|) parallel depth or Omega(|V|(2)) queries. In contrast to state-of-the-art weakly-polynomial and strongly-polynomial time algorithms for SFM, our algorithms use first-order optimization methods, e.g., mirror descent and follow the regularized leader. We introduce what we call sparse dual certificates, which encode information on the structure of sparse minimizers, and both our parallel and sequential algorithms provide new algorithmic tools for allowing first-order optimization methods to efficiently compute them. Correspondingly, our algorithm does not invoke fast matrix multiplication or general linear system solvers and in this sense is more combinatorial than previous state-of-the-art methods.

关键词： submodular function minimization convex optimization sparsity query complexity parallel complexity

来源：评论

学校读者我要写书评

暂无评论

A Polynomial Lower Bound on the Number of Rounds for Parallel submodular function minimization 62

A Polynomial Lower Bound on the Number of Rounds for Paralle...

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Chakrabarty, Deeparnab Chen, Yu Khanna, Sanjeev Dartmouth Coll Hanover NH 03755 USA Univ Penn Philadelphia PA 19104 USA

ISBN: (纸本)9781665420556

The problem of minimizing a submodular function (SFM) is a common generalization of several fundamental combinatorial optimization problems, including minimum s-t cuts in graphs and matroid intersection. It is well-known that a submodular function can be minimized with only poly(N) function evaluation queries where N denotes the universe size. However, all known polynomial query algorithms for SFM are highly adaptive, requiring at least N rounds of adaptivity. A natural question is if SFM can be efficiently solved in a highly parallel manner, namely, with poly(N) queries using only poly-logarithmic rounds of adaptivity. An important step towards understanding the adaptivity needed to solve SFM efficiently was taken in the very recent work of Balkanski and Singer who showed that any SFM algorithm with poly(N) queries. This left open the possibility of efficient SFM algorithms with poly-logarithmic rounds of adaptivity. In this work, we strongly rule out this possibility by showing that any, possibly randomized, algorithm for submodular function minimization making poly(N) queries requires (Omega) over tilde (N-1/3) rounds of adaptivity. In fact, we show a polynomial lower bound on the number of rounds of adaptivity even for algorithms that make up to 2(N1-delta) queries, for any constant d > 0.

关键词： submodular function minimization Parallel Algorithms Lower Bounds

来源：评论

学校读者我要写书评

暂无评论

Improved Lower Bounds for submodular function minimization 63

Improved Lower Bounds for Submodular Function Minimization

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Chakrabarty, Deeparnab Graur, Andrei Jiang, Haotian Sidford, Aaron Dartmouth Coll Dept Comp Sci Hanover NH 03755 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA Univ Washington Paul G Allen Sch Comp Sci & Engn Seattle WA 98195 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA

ISBN: (纸本)9781665455190

We provide a generic technique for constructing families of submodular functions to obtain lower bounds for submodular function minimization (SFM). Applying this technique, we prove that any deterministic SFM algorithm on a ground set of n elements requires at least Omega(n log n) queries to an evaluation oracle. This is the first super-linear query complexity lower bound for SFM and improves upon the previous best lower bound of 2n given by [Graur et al., ITCS 2020]. Using our construction, we also prove that any (possibly randomized) parallel SFM algorithm, which can make up to poly(n) queries per round, requires at least Omega(n/ log n) rounds to minimize a submodular function. This improves upon the previous best lower bound of (Omega) over tilde (n(1/3)) rounds due to [Chakrabarty et al., FOCS 2021], and settles the parallel complexity of query-efficient SFM up to logarithmic factors due to a recent advance in [Jiang, SODA 2021]. Index

关键词： submodular function minimization lower bound query complexity parallel complexity

来源：评论

学校读者我要写书评

暂无评论

Geometric Rescaling Algorithms for submodular function minimization

引用

MATHEMATICS OF OPERATIONS RESEARCH 2021年第3期46卷 1081-1108页

作者： Dadush, Dan Vegh, Laszlo A. Zambelli, Giacomo Ctr Wiskunde & Informat NL-1098 XG Amsterdam Netherlands London Sch Econ & Polit Sci London WC2A 2AE England

We present a new class of polynomial-time algorithms for submodular function minimization (SFM) as well as a unified framework to obtain strongly polynomial SFM algorithms. Our algorithms are based on simple iterative methods for the minimum-norm problem, such as the conditional gradient and Fujishige-Wolfe algorithms. We exhibit two techniques to turn simple iterative methods into polynomial-time algorithms. First, we adapt the geometric rescaling technique, which has recently gained attention in linear programming, to SFM and obtain a weakly polynomial bound O((n(4) center dot EO + n(5))log(nL)). Second, we exhibit a general combinatorial black box approach to turn EL-approximate SFM oracles into strongly polynomial exact SFM algorithms. This framework can be applied to a wide range of combinatorial and continuous algorithms, including pseudo-polynomial ones. In particular, we can obtain strongly polynomial algorithms by a repeated application of the conditional gradient or of the Fujishige-Wolfe algorithm. Combined with the geometric rescaling technique, the black box approach provides an O((n(5) center dot EO + n(6))log(2) n) algorithm. Finally, we show that one of the techniques we develop in the paper can also be combined with the cutting-plane method of Lee et al., yielding a simplified variant of their O(n(3)log(2) n center dot EO + n(4)log(O(1))n) algorithm.

关键词： submodular function minimization gradient methods rescaling

来源：评论

学校读者我要写书评

暂无评论

Combinatorial Algorithms for submodular functionminimization and Related Problems

Combinatorial Algorithms for Submodular FunctionMinimization...

引用

作者： Price, Christopher University of Waterloo

学位级别：master

submodular functions are common in combinatorics;examples include the cut capacity function of a graph and the rankfunction of a matroid. The submodular function minimization problemgeneralizes the classical minimum cut problem and also contains anumber of other combinatorial optimization problems as specialcases. In this thesis, we study submodular function minimizationand two related problems: matroid polyhedron membership and matroidintersection. A significant contribution concerns algorithms forthe latter problems due to Cunningham. In particular, we identifyand correct errors in the original proofs of the running timebounds for these algorithms

关键词： algorithms combinatorial optimization submodular function minimization

来源：评论

学校读者我要写书评

暂无评论

On the complexity of submodular function minimisation on diamonds

引用

DISCRETE OPTIMIZATION 2011年第3期8卷 459-477页

作者： Kuivinen, Fredrik Linkopings Univ Dept Comp & Informat Sci SE-58183 Linkoping Sweden

Let (L: boolean AND, boolean OR) be a finite lattice and let n be a positive integer. A function f : L-n -> R is said to be submodular if f(a boolean AND b) + f(a boolean OR b) Z and an integer m such that min(x i... 详细信息

Let (L: boolean AND, boolean OR) be a finite lattice and let n be a positive integer. A function f : L-n -> R is said to be submodular if f(a boolean AND b) + f(a boolean OR b) <= f(a) + f(b) for all a, b is an element of L-n. In this article we study submodular functions when L is a diamond. Given oracle access to f we are interested in finding x is an element of L-n such that f(x) = min(y is an element of Ln) f(y) as efficiently as possible. We establish a min-max theorem, which states that the minimum of the submodular function is equal to the maximum of a certain function defined over a certain polyhedron;and a good characterisation of the minimisation problem, i.e., we show that given an oracle for computing a submodular f : L-n -> Z and an integer m such that min(x is an element of Ln) f(x) = there is a proof of this fact which can be verified in time polynomial in n and max(t is an element of Ln) log vertical bar f(t)vertical bar;and a pseudopolynomial-time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular f : L-n -> Z one can find min(t is an element of Ln) f(t) in time bounded by a polynomial in n and max(t is an element of Ln) vertical bar f(t)vertical bar. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization submodular function minimization Lattices Diamonds

来源：评论

学校读者我要写书评

暂无评论

A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2010年第3期19卷 369-393页

作者： Fanghaenel, Diana Liers, Frauke Univ Cologne Inst Informat D-50969 Cologne Germany

Given a graph G=(V,E) with edge weights w (e) aa"e, the optimum cooperation problem consists in determining a partition of the graph that maximizes the sum of weights of the edges with nodes in the same class plus the number of the classes of the partition. The problem is also known in the literature as the optimum attack problem in networks. Furthermore, a relevant physics application exists. In this work, we present a fast exact algorithm for the optimum cooperation problem. Algorithms known in the literature require |V|-1 minimum cut computations in a corresponding network. By theoretical considerations and appropriately designed heuristics, we considerably reduce the numbers of minimum cut computations that are necessary in practice. We show the effectiveness of our method by presenting results on instances coming from the physics application. Furthermore, we analyze the structure of the optimal solutions.

关键词： Optimum attack problem submodular function minimization Potts glass with many states

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：