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

Computational Comparison of Major Proposed Methods for graph partitioning problem

JOURNAL OF ADVANCED COMPUTATIONAL INTELLIGENCE AND INTELLIGENT INFORMATICS 2019年第1期23卷 5-17页

作者： Rais, Helmi Md Abed, Saad Adnan Watada, Junzo Univ Teknol Petronas Dept Comp & Informat Sci Seri Iskandar 32610 Perak Malaysia Univ Teknol Petronas High Performance Cloud Comp Ctr Seri Iskandar 32610 Perak Malaysia

k-way graph partitioning is an NP-complete problem, which is applied to various tasks such as route planning, image segmentation, community detection, and high-performance computing. The approximate methods constitute a useful solution for these types of problems. Thus, many research studies have focused on developing meta-heuristic algorithms to tackle the graph partitioning problem. Local search is one of the earliest methods that has been applied efficiently to this type of problem. Recent studies have explored various types of local search methods and have improved them such that they can be used with the partitioning process. Moreover, local search methods are widely integrated with population-based approaches, to provide the best diversification and intensification for the problem space. This study emphasizes the local search approaches, as well as their combination with other graph partitioning approaches. At present, none of the surveys in the literature has focused on this class of state of the art approaches in much detail. In this study, the vital parts of these approaches including neighborhood structure, acceptance criterion, and the ways of combining them with other approaches, are highlighted. Additionally, we provide an experimental comparison that shows the variance in the performance of the reviewed methods. Hence, this study clarifies these methods to show their advantages and limitations for the targeted problem, and thus can aid in the direction of research flow towards the area of graph partitioning.

关键词： graph partitioning problem hill climbing simulated annealing tabu search multilevel approaches

来源：评论

学校读者我要写书评

暂无评论

On the sum-max graph partitioning problem

引用

THEORETICAL COMPUTER SCIENCE 2014年第1期540卷 143-155页

作者： Watrigant, Remi Bougeret, Marin Giroudeau, Rodolphe Koenig, Jean-Claude LIRMM Univ Montpellier II CNRS UMR 5506 F-34392 Montpellier 5 France

This paper tackles the following problem: given a connected graph G = (V E) with a weight function on its edges and an integer k <= vertical bar V vertical bar, find a partition of V into k clusters such that the sum (over all pairs of clusters) of the heaviest edges between the clusters is minimized. We first prove that this problem (and even the unweighted variant) cannot be approximated within a factor of 0 (n(1-epsilon)) unless P = NP, and cannot admit an FPT algorithm unless FPT = W[1]. Next, we develop several algorithms: we first present a greedy algorithm and prove that it achieves a tight approximation ratio smaller than k/2. Concerning the unweighted version of the problem, we study how the diameter of the input graph can influence its complexity, by obtaining negative results for graphs of low diameter, positive results for graphs of high diameter, and a polynomial-time approximation algorithm with an approximation ratio smaller than k/2 and depending on the diameter. We also highlight a link between the k-SPARSEST SUBgraph problem and the unweighted version. This allows us to develop several constant ratio approximation algorithms running in exponential time for general graphs, and in polynomial time in some restricted graph classes. Finally, we discuss the exact resolution for fixed k and the connections to a graph homomorphism problem. (C) 2013 Elsevier B.V. All rights reserved.

关键词： graph partitioning problem Approximation Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Contribution of copositive formulations to the graph partitioning problem

引用

OPTIMIZATION 2013年第1期62卷 71-83页

作者： Povh, Janez Inst Math Phys & Mech Ljubljana 1000 Slovenia Fac Informat Studies Novo Mesto 8000 Slovenia

This article provides analysis of several copositive formulations of the graph partitioning problem and semidefinite relaxations based on them. We prove that the copositive formulations based on results from Burer [S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120 (Ser. A) (2009), pp. 479495] and the author of the paper [J. Povh, Semidefinite approximations for quadratic programs over orthogonal matrices. J. Global Optim. 48 (2010), pp. 447463] are equivalent and that they both imply semidefinite relaxations which are stronger than the DonathHoffman eigenvalue lower bound [W.E. Donath and A.J. Hoffman, Lower bounds for the partitioning of graphs. IBM J. Res. Develop. 17 (1973), pp. 420425] and the projected semidefinite lower bound from Wolkowicz and Zhao [H. Wolkowicz and Q. Zhao, Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 9697 (1999), pp. 461479].

关键词： graph partitioning problem copositive programming semidefinite relaxation Primary: 90C22 90C27 Secondary: 65K05 90C10

来源：评论

学校读者我要写书评

暂无评论

DSLS: a simple and efficient local search algorithm for the maximum bisection problem

引用

JOURNAL OF HEURISTICS 2024年第1-2期30卷 43-65页

作者： Tian, Xinliang Ouyang, Dantong Zhou, Huisi Sun, Rui Zhang, Liming Jilin Univ Coll Comp Sci & Technol Changchun 130012 Peoples R China Jilin Univ Key Lab Symbol Computat & Knowledge Engn Minist Educ Changchun 130012 Peoples R China

The maximum bisection problem (max-bisection) belongs to a family of well-known graph partitioning problems with wide applications. In this study, we develop a simple and efficient local search algorithm called DSLS for max-bisection. The main idea in DSLS is the dynamic step strategy, which automatically adjusts the intensification and diversification to complete the search by changing the length of the step. Moreover, we design an efficient initial constructive method based on the degree information of the vertices, which provides high-quality initial solutions to the DSLS algorithm. In the data preprocessing, a reduction rule is proposed to cut down the size of benchmark graphs and improve the performance of the DSLS algorithm on benchmark graphs. We adopt 71 well-known benchmark graphs to evaluate our algorithm, and the experiments show that the DSLS algorithm is highly competitive with the state-of-the-art heuristic algorithms and discovers improved best-known results (new lower bounds) for 12 benchmark graphs.

关键词： Max-bisection graph partitioning problem Local search Heuristics

来源：评论

学校读者我要写书评

暂无评论

Genetic local search the graph partitioning problem under cardinality constraints

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2012年第1期52卷 157-167页

作者： Kochetov, Yu. A. Plyasunov, A. V. Russian Acad Sci Siberian Branch Sobolev Inst Math Novosibirsk 630090 Russia

For the graph partitioning problem under cardinality constraints, a genetic local search method is developed. At each iteration of the method, there is a set of local optima of the problem. This set is used to search for new local optima with a smaller error. The local search problem with certain polynomially searchable neighborhoods is proved to be tight PLS-complete. It is shown that, in the worst case, number of local improvements can be exponentially large for any pivoting rule. Numerical experiments are performed in the special case of edge weights equal to unity, when local search is a polynomial-time procedure. The results of the experiments indicate that the method is highly efficient and can be applied to large-scale problems.

关键词： graph partitioning problem tight PLS-completeness local search genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimized Lie-Trotter-Suzuki decompositions for two and three non-commuting terms

引用

ANNALS OF PHYSICS 2020年 418卷 168165-168165页

作者： Barthel, Thomas Zhang, Yikang Duke Univ Dept Phys Durham NC 27708 USA

Lie-Trotter-Suzuki decompositions are an efficient way to approximate operator exponentials exp(tH) when H is a sum of n (non-commuting) terms which, individually, can be exponentiated easily. They are employed in time-evolution algorithms for tensor network states, digital quantum simulation protocols, path integral methods like quantum Monte Carlo, and splitting methods for symplectic integrators in classical Hamiltonian systems. We provide optimized decompositions up to order t(6). The leading error term is expanded in nested commutators (Hall bases) and we minimize the 1-norm of the coefficients. For n = 2 terms, several of the optima we find are close to those in McLachlan (1995). Generally, our results substantially improve over unoptimized decompositions by Forest, Ruth, Yoshida, and Suzuki. We explain why these decompositions are sufficient to efficiently simulate any one- or two-dimensional lattice model with finite-range interactions. This follows by solving a partitioning problem for the interaction graph. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Lie-Trotter-Suzuki decomposition Quantum Hamiltonian simulation Symplectic integrators Splitting methods Hall basis graph partitioning problem

来源：评论

学校读者我要写书评

暂无评论

Automatic choroid layer segmentation using normalized graph cut

引用

IET IMAGE PROCESSING 2018年第1期12卷 53-59页

作者： Masood, Saleha Sheng, Bin Li, Ping Shen, Ruimin Fang, Ruogu Wu, Qiang Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai Peoples R China Macau Univ Sci & Technol Fac Informat Technol Macau Peoples R China Florida Int Univ Sch Comp & Informat Sci Miami FL 33199 USA Shanghai Jiao Tong Univ Affiliated Peoples Hosp 6 Shanghai Peoples R China

Optical coherence tomography is an immersive technique for depth analysis of retinal layers. Automatic choroid layer segmentation is a challenging task because of the low contrast inputs. Existing methodologies carried choroid layer segmentation manually or semi-automatically. The authors proposed automated choroid layer segmentation based on normalised cut algorithm, which aims at extracting the global impression of images and treats the segmentation as a graph partitioning problem. Due to the structure complexity of retinal and choroid layers, the authors employed a series of pre-processing to make the cut more deterministic and accurate. The proposed method divided the image into several patches and ran the normalised cut algorithm on every patch separately. The aim was to avoid insignificant vertical cuts and focus on horizontal cutting. After processing every patch, the authors acquired a global cut on the original image by combining all the patches. Later the authors measured the choroidal thickness which is highly helpful in the diagnosis of several retinal diseases. The results were computed on a total of 525 images of 21 real patients. Experimental results showed that the mean relative error rate of the proposed method was around 0.4 when compared with the manual segmentation performed by the experts.

关键词： image segmentation graph theory eye medical image processing mean relative error rate retinal disease choroidal thickness measurement graph partitioning problem image segmentation normalised cut algorithm retinal layer depth analysis optical coherence tomography slicing approach automatic choroid layer segmentation

来源：评论

学校读者我要写书评

暂无评论

Solving the m-Way graph partitioning problem Using a Genetic Algorithm

引用

IEEJ TRANSACTIONS ON ELECTRICAL AND ELECTRONIC ENGINEERING 2011年第5期6卷 483-489页

作者： Chen, Zhi-Qiang Wang, Rong-Long Univ Fukui Fac Engn Dept Elect & Elect Engn Fukui 910 Japan

The m-way graph partitioning problem is of central importance in combinatorial optimization. It has many important applications in fields such as VLSI circuit design, task allocation in distributed computing systems, and network partitioning. In this paper, we propose an efficient genetic algorithm to solve this problem. The proposed method searches a large solution space and finds the best possible solution by adjusting the intensification and diversification automatically during the optimization process. The proposed method is tested on a large number of instances and compared with some existing algorithms. The experimental results show that the proposed algorithm is superior to its competitors in terms of computation time and solution quality. (C) 2011 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.

关键词： genetic algorithm graph partitioning problem combinatorial optimization problems NP-complete problem

来源：评论

学校读者我要写书评

暂无评论

Distance-Based Exponential Probability Models for Constrained Combinatorial problems 18th

Distance-Based Exponential Probability Models for Constraine...

引用

18th Conference of the Spanish-Association-for-Artificial-Intelligence (CAEPIA)

作者： Ceberio, Josu Mendiburu, Alexander Lozano, Jose A. Univ Basque Country UPV EHU Paseo Manuel Lardizabal 1 Donostia San Sebastian 20018 Spain BCAM Alameda Mazarredo 14 Bilbao 48009 Spain

ISBN: (纸本)9783030003746;9783030003739

Estimation of Distribution Algorithms (EDAs) have already demonstrated their utility when solving a broad range of combinatorial problems. However, there is still room for methodological improvement when approaching problems with constraints. The great majority of works in the literature implement repairing or penalty schemes, or use ad-hoc sampling methods in order to guarantee the feasibility of solutions. In any of the previous cases, the behavior of the EDA is somehow denaturalized, since the sampled set does not follow the probability distribution estimated at that step. In this work, we present a general method to approach constrained combinatorial optimization problems by means of EDAs. This consists of developing distance-based exponential probability models defined exclusively on the set of feasible solutions. In order to illustrate this procedure, we take the 2-partition balanced graph partitioning problem as a case of study, and design efficient learning and sampling methods to use distance-based exponential probability models in EDAs.

关键词： Constraint Estimation of Distribution Algorithm Distance-based exponential model graph partitioning problem

来源：评论

学校读者我要写书评

暂无评论

Operation of shunting yards: train-to-yard assignment problem

引用

Journal of Business Economics 2017年第4期87卷 465-486页

作者： Otto, Alena Pesch, Erwin Department of Management Information Science University of Siegen Kohlbettstraße 15 Siegen 57068 Germany Center of Advanced Studies in Management HHL Leipzig Jahnallee 59 Leipzig 04109 Germany

A multiple shunting yard as a major freight rail yard consists of several sub-yards of limited capacities. Our research question is how to assign the railcars of inbound trains among the sub-yards such that the number of re-assignments is minimized. We denote this problem as train-to-yard assignment problem (TYAP) and prove its strong NP-hardness. Moreover, our computational experiments show that the lower bounds of IBM ILOG CPLEX are poor and not competitive to our lower bounds that can be computed in a fraction of a second. Because of their low computational complexity, our lower bounds can be repeatedly calculated in any enumeration algorithm such as branch and bound or bounded dynamic programming without contributing substantially to the overall runtime. © 2016, Springer-Verlag Berlin Heidelberg.

关键词： Freight transportation graph partitioning problem Multiple yards Shunting yard

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：