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

A polynomial time algorithm for finding a minimum 4-partition of a submodular function

MATHEMATICAL PROGRAMMING 2024年第1-2期207卷 717-732页

作者： Hirayama, Tsuyoshi Liu, Yuhao Makino, Kazuhisa Shi, Ke Xu, Chao Toshiba Digital Solut Corp Kawasaki Japan Univ Elect Sci & Technol China Chengdu Peoples R China Kyoto Univ Kyoto Japan

In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f : 2(V) -> R, computing a k-partition {V-1, ... , V-k} of V with minimum Sigma k(i=1) f(V-i). The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for fixed k <= 3. In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem.

关键词： submodular function Polynomial time Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Graph Algorithm Based submodular function for Sparsest Cut Problem

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2023年第0期

作者： Zhang, Xiaoyan Chang, Hong Guo, Longkun Du, Donglei Zou, Gaokai Xiong, Yuanyuan Nanjing Normal Univ Sch Math Sci & Inst Math Nanjing 210023 Peoples R China Fuzhou Univ Sch Math & Stat Fuzhou 350108 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada Fuzhou Univ Sch Comp & Data Sci Fuzhou 350108 Peoples R China

Sparsest cut problems are very important graph partitions, which have been widely applied in expander graphs, Markov chains, and image segmentation. In this paper, we study the edge-weighted version of the Sparse Cut Problem, which minimizes the ratio of the total weight of edges between blocks and the total weight of edges incident to vertices in one block. We first prove that the problem is even NP-hard for an edge-weighted graph with bridges. Then, we combine and generalize submodular functions and principal partition to design a graph algorithm to improve the initial bipartition, which runs in polynomial time by using network flow as its subroutines.

关键词： Bipartition sparsest cut problem sparsity submodular function principal partition

来源：评论

学校读者我要写书评

暂无评论

Fault-Tolerant Total Domination via submodular function Approximation 17th

Fault-Tolerant Total Domination via Submodular Function Appr...

引用

17th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Lamprou, Ioannis Sigalas, Ioannis Vaxevanakis, Ioannis Zissimopoulos, Vassilis Natl & Kapodistrian Univ Athens Dept Informat & Telecommun Athens Greece

ISBN: (纸本)9783031203497;9783031203503

In total domination, given a graph G = (V, E), we seek a minimum-size set of nodes S subset of V, such that every node in V \ S has at least one neighbor in S and every node in S also has at least one neighbor in S. We define the fault-tolerant version of total domination, where we extend the requirement for nodes in V \ S. Any node in V \ S must have at least m neighbors in S. Let Delta denote the maximum degree in G. We prove a first 1+ ln(Delta + m - 1) approximation for fault-tolerant total domination. To prove our result, we develop a general submodular function approximation framework we believe is of independent interest.

关键词： Fault-tolerant Total domination Dominating set Approximation algorithms submodular function

来源：评论

学校读者我要写书评

暂无评论

IMPROVED RANDOMIZED ALGORITHM FOR k-submodular function MAXIMIZATION

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第1期35卷 1-22页

作者： Oshima, Hiroki Univ Tokyo Grad Sch Informat Sci & Technol Dept Math Informat Tokyo Japan

submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the TwentySeventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404-413] gave a randomized k/(2k 1)-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a k(2)+1/2k(2)+1 -approximation for k >= 3. We also give a randomized root 17-3/ -approximation algorithm for k = 3. We use the same framework used in Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and Zivny [ACM Trans. Algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities.

关键词： submodular function k-submodular function randomized algorithm approximation

来源：评论

学校读者我要写书评

暂无评论

MAXIMIZING A MONOTONE submodular function WITH A BOUNDED CURVATURE UNDER A KNAPSACK CONSTRAINT

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2019年第3期33卷 1452-1471页

作者： Yoshida, Yuichi Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan

We consider the problem of maximizing a monotone submodular function under a knapsack constraint. We show that, for any fixed epsilon > 0, there exists a polynomial-time algorithm with an approximation ratio 1- c/e - epsilon, where c is an element of [0, 1] is the (total) curvature of the input function. This approximation ratio is tight up to c for any c is an element of [0, 1]. To the best of our knowledge, this is the first result for a knapsack constraint that incorporates the curvature to obtain an approximation ratio better than 1 - 1/e, which is tight for general submodular functions. As an application of our result, we present a polynomial-time algorithm for the budget allocation problem with an improved approximation ratio.

关键词： submodular function curvature knapsack constraints

来源：评论

学校读者我要写书评

暂无评论

Approximating Robust Parameterized submodular function Maximization in Large-Scales

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2019年第4期36卷 1950022.1-1950022.24页

作者： Yang, Ruiqi Xu, Dachuan Jiang, Yanjun Wang, Yishui Zhang, Dongmei Beijing Univ Technol Dept Operat Res & Sci Comp 100 Pingleyuan Beijing 100124 Peoples R China Ludong Univ Sch Math & Stat Sci 186 Hongqi Middle Rd Yantai 264025 Shandong Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China

We study a robust parameterized submodular function maximization inspired by [Mitrovic, S, I Bogunovic, A Norouzi-Fardand Jakub Tarnawski (2017). Streaming robust submodular maximization: A partitioned thresholding approach. In Proc. NIPS, pp. 4560-4569] and [Bogunovic, I, J Zhao and V Cevher (2018). Robust maximization of nonsubmodular objectives. In Proc. AISTATS, pp. 890-899]. In our setting, given a parameterized set function, there are two additional twists. One is that elements arrive in a streaming style, and the other is that there are at most tau items deleted from the algorithm's memory when the stream is finished. The goal is to choose a robust set from the stream such that the robust ratio is maximized. We propose a two-phase algorithm for maximizing a normalized monotone robust parameterized submodular function with a cardinality constraint and show the robust ratio is close to a constant as k -> infinity. In the end, we empirically demonstrate the performance of our algorithm on deletion robust support selection problem.

关键词： submodular function robust stream approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Rough set methods in feature selection via submodular function

引用

SOFT COMPUTING 2017年第13期21卷 3699-3711页

作者： Zhu, Xiao-Zhong Zhu, William Fan, Xin-Nan Hohai Univ Coll IOT Engn Changzhou 213022 Peoples R China Minnan Normal Univ Lab Granular Comp Zhangzhou 363000 Peoples R China

Attribute reduction is an important problem in data mining and machine learning in that it can highlight favorable features and decrease the risk of over-fitting to improve the learning performance. With this regard, rough sets offer interesting opportunities for this problem. Reduct in rough sets is a subspace of attributes/features which are jointly sufficient and individually necessary to satisfy a certain criterion. Excessive attributes may reduce diversity and increase correlation among features, a lower number of attributes may also receive nearly equal to or even higher classification accuracy in some specific classifiers, which motivates us to address dimensionality reduction problems with attribute reduction from the joint viewpoint of the learning performance and the reduct size. In this paper, we propose a new attribute reduction criterion to select lowest attributes while keeping the best performance of the corresponding learning algorithms to some extent. The main contributions of this work are twofold. First, we define the concept of k-approximate-reduct, instead of the limitation to minimum reduct, which provides an important view to reveal the connection between the size of attribute reduct and the learning performance. Second, a greedy algorithm for attribute reduction problems based on mutual information is developed, and submodular functions are used to analyze its convergence. By the property of diminishing return of the submodularity, there is a solid guarantee for the reasonability of the k-approximate-reduct. It is noted that rough sets serve as an effective tool to evaluate both the marginal and joint probability distributions among attributes in mutual information. Extensive experiments in six real-world public datasets from machine learning repository demonstrate that the selected subset by mutual information reduct comes with higher accuracy with less number of attributes when developing classifiers naive Bayes and radial basis function ne

关键词： Attribute reduction Granular computing Mutual information Rough set submodular function

来源：评论

学校读者我要写书评

暂无评论

Faster approximation algorithms for maximizing a monotone submodular function subject to a b-matching constraint

引用

INFORMATION PROCESSING LETTERS 2016年第9期116卷 578-584页

作者： Fujii, Kaito Kyoto Univ Grad Sch Informat Sakyo Ku 36-1 Yoshida Honmachi Kyoto 6068501 Japan

Maximizing a monotone submodular function subject to a b-matching constraint is increasing in importance due to its application to the content spread maximization problem, but few practical algorithms are known other than the greedy algorithm. The best approximation scheme so far is the local search algorithm, proposed by Feldman, Naor, Schwartz, and Ward [8] (2011). It obtains a 1/(2 + 1/k + is an element of)-approximate solution for an arbitrary positive integer k and positive real number is an element of. For graphs with n vertices and m edges, the running time of the local search algorithm is O(b(k+1) (Delta - 1)(k)nm is an element of(-1)) where Delta is the maximum degree, which is impractical for large problems. In this paper, we present two new algorithms for this problem. One is a find walk algorithm that runs in O(bm) time and achieves 1/4-approximation. It is faster than the greedy algorithm whose approximation ratio is 1/3. The other one is a randomized local search algorithm that is a faster variant of the local search algorithm. In expectation, it runs in O(b(k+1) (Delta - 1)(k-1)m log 1/is an element of) time and obtains a (1/(2 + 1/k) - is an element of)-approximate solution. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Approximation algorithms submodular function b-Matching

来源：评论

学校读者我要写书评

暂无评论

On Multiplicative Weight Updates for Concave and submodular function Maximization 15

On Multiplicative Weight Updates for Concave and Submodular ...

引用

6th Conference on Innovations in Theoretical Computer Science (ITCS)

作者： Chekuri, Chandra Jayram, T. S. Vondrak, Jan Univ Illinois Dept Comp Sci Urbana IL 61801 USA IBM Almaden Res Ctr San Jose CA 95120 USA

ISBN: (纸本)9781450333337

We develop a continuous-time framework based on multiplicative weight updates to approximately solve continuous optimization problems. The framework allows for a simple and modular analysis for a variety of problems involving convex constraints and concave or submodular objective functions. The continuous-time framework avoids the cumbersome technical details that are typically necessary in actual algorithms. We also show that the continuous-time algorithms can be converted into implementable algorithms via a straightforward discretization process. Using our framework and additional ideas we obtain significantly faster algorithms compared to previously known algorithms to maximize the multilinear relaxation of a monotone or non-monotone submodular set function subject to linear packing constraints.

关键词： submodular function multiplicative weight updates

来源：评论

学校读者我要写书评

暂无评论

Sliding Window Bi-objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone submodular functions 18th

Sliding Window Bi-objective Evolutionary Algorithms for Opti...

引用

18th International Conference on Parallel Problem Solving from Nature (PPSN)

作者： Yan, Xiankun Neumann, Aneta Neumann, Frank Univ Adelaide Sch Comp & Math Sci Optimisat & Logist Adelaide SA Australia

ISBN: (纸本)9783031700545;9783031700552

Variants of the GSEMO algorithm using multi-objective formulations have been successfully analyzed and applied to optimize chance-constrained submodular functions. However, due to the effect of the increasing population size of the GSEMO algorithm considered in these studies from the algorithms, the approach becomes ineffective if the number of trade-offs obtained grows quickly during the optimization run. In this paper, we apply the sliding-selection approach introduced in [21] to the optimization of chance-constrained monotone submodular functions. We theoretically analyze the resulting SW-GSEMO algorithm which successfully limits the population size as a key factor that impacts the runtime and show that this allows it to obtain better runtime guarantees than the best ones currently known for the GSEMO. In our experimental study, we compare the performance of the SW-GSEMO to the GSEMO and NSGA-II on the maximum coverage problem under the chance constraint and show that the SW-GSEMO outperforms the other two approaches in most cases. In order to get additional insights into the optimization behavior of SW-GSEMO, we visualize the selection behavior of SW-GSEMO during its optimization process and show it beats other algorithms to obtain the highest quality of solution in variable instances.

关键词： chance constraints submodular function evolutionary algorithms runtime analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：