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

Semidefinite programming and eigenvalue bounds for the graph partition problem

MATHEMATICAL PROGRAMMING 2015年第2期151卷 379-404页

作者： van Dam, Edwin R. Sotirov, Renata Tilburg Univ Dept Econometr & OR Warandelaan 2 NL-5000 LE Tilburg Netherlands

The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the sum of weights of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes of graphs and also show how to aggregate additional triangle and independent set constraints for graphs with symmetry. We present an eigenvalue bound for the graph partition problem of a strongly regular graph, extending a similar result for the equipartition problem. We also derive a linear programming bound of the graph partition problem for certain Johnson and Kneser graphs. Using what we call the Laplacian algebra of a graph, we derive an eigenvalue bound for the graph partition problem that is the first known closed form bound that is applicable to any graph, thereby extending a well-known result in spectral graph theory. Finally, we strengthen a known semidefinite programming relaxation of a specific quadratic assignment problem and the above-mentioned matrix-lifting semidefinite programming relaxation by adding two constraints that correspond to assigning two vertices of the graph to different parts of the partition. This strengthening performs well on highly symmetric graphs when other relaxations provide weak or trivial bounds.

关键词： graph partition problem Semidefinite programming Eigenvalues Strongly regular graph Symmetry

来源：评论

学校读者我要写书评

暂无评论

A strong formulation for the graph partition problem

引用

NETWORKS 2020年第2期75卷 183-202页

作者： Chopra, Sunil Shim, Sangho Northwestern Univ Kellogg Grad Sch Management Evanston IL USA Robert Morris Univ Sch Engn Math & Sci Moon Township PA 15090 USA

We develop a polynomial size extended graph formulation of the graph partition problem which dominates the formulation introduced by Chopra and Rao's study, and show that the extended graph formulation is tight on a tree. We introduce exponentially many valid inequalities to the Chopra-Rao formulation, which we call generalized arc inequalities (GAI), and develop a linear time algorithm to separate the most violated generalized arc inequality. We show that the polynomial size extended graph formulation is equivalent to the Chopra-Rao formulation augmented by the exponentially many GAI.

关键词： combinatorial optimization extended formulation extended graph formulation graph partition problem integer programming network clustering primal dual construction

来源：评论

学校读者我要写书评

暂无评论

partitioning graphs of supply and demand

引用

DISCRETE APPLIED MATHEMATICS 2009年第12期157卷 2620-2633页

作者： Ito, Takehiro Zhou, Xiao Nishizeki, Takao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

Assume that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive integer, called a supply or a demand. Each demand vertex can receive "power" from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C has exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in C. If G does not have such a partition, one wishes to partition G into connected components so that each component C either has no supply vertex or has exactly one supply vertex whose supply is no less than the sum of demands in C, and wishes to maximize the sum of demands in all components with supply vertices. We deal with such a maximization problem, which is NP-hard even for trees and strongly NP-hard for general graphs. In this paper, we show that the problem can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees - that is, graphs with bounded tree-width. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Demand graph partition problem Series-parallel graph Supply Partial k-tree

来源：评论

学校读者我要写书评

暂无评论

A general variable neighborhood search approach for the minimum load coloring problem

引用

OPTIMIZATION LETTERS 2023年第9期17卷 2065-2086页

作者： Herran, Alberto Manuel Colmenar, J. Mladenovic, Nenad Duarte, Abraham Univ Rey Juan Carlos Dept Comp Sci C Tulipan S-N Madrid 28933 Spain Khalifa Univ Dept Ind Engn Abu Dhabi U Arab Emirates Khalifa Univ Res Ctr Digital Supply Chain & Operat Management Abu Dhabi U Arab Emirates

The minimum load coloring problem consists of finding a 2-coloring function that assign either a color red or blue to each node of a graph such that the (maximum) load is minimized, i.e., to reduce as much as possible the number of edges with, at least, one endpoint colored in red (symmetrically, in blue). This NP-complete problem arises in Wavelength Division Multiplexing (WDM) technology and it has been used for broadcast WDM networks. In this paper, several procedures based on the Variable Neighborhood Search (VNS) methodology are proposed and compared on a set of random graphs and DIMACS benchmarks. Experimental results show that the proposed VNS variant exhibits a remarkable performance in comparison with the state-of-the-art methods. In particular, our approach achieves the best results in 48 out of 52 considered instances by employing, on average, less than 7 seconds. These results are further confirmed by conducting statistical tests.

关键词： Metaheuristics Variable neighborhood search graph coloring problem graph partition problem

来源：评论

学校读者我要写书评

暂无评论

Vertex decomposition method for wirelength problem and its applications to enhanced hypercube networks

引用

IET COMPUTERS AND DIGITAL TECHNIQUES 2019年第2期13卷 87-92页

作者： Arockiaraj, Micheal Liu, Jia-Bao Shalini, Arul Jeya Loyola Coll Dept Math Chennai 600034 Tamil Nadu India Anhui Jianzhu Univ Sch Math & Phys Hefei 230601 Anhui Peoples R China Womens Christian Coll Dept Math Chennai 600006 Tamil Nadu India

In this study, the authors discuss the vertex congestion of any embedding from the guest graph into the host graph and outline a rigorous mathematical method to compute the wirelength of that embedding. Further, they show that the computation of the optimal wirelength depends on finding optimal solutions for another graph partition problem such as edge isoperimetric problem in that guest graph. On the other side, they consider an important variant of the popular hypercube network, the enhanced hypercube, and obtain the nested optimal solutions for the edge isoperimetric problem. As a combined output, they illustrate the authors' technique by embedding enhanced hypercube into a caterpillar and from that reducing the linear layout of the enhanced hypercube. As another application of their technique, they embed the hypercube as well as the enhanced hypercube on the two rows extended grid structure with optimal wirelength for the first time and showing that the existing edge congestion technique cannot be used to solve this problem.

关键词： graph theory computational geometry hypercube networks host graph outline rigorous mathematical method optimal wirelength graph partition problem edge isoperimetric problem guest graph popular hypercube network nested optimal solutions embedding enhanced hypercube existing edge congestion technique vertex decomposition method wirelength problem enhanced hypercube networks authors study vertex congestion

来源：评论

学校读者我要写书评

暂无评论

Bisecting a 4-connected graph with three resource sets

引用

DISCRETE APPLIED MATHEMATICS 2007年第11期155卷 1441-1450页

作者： Ishii, Toshimasa Iwata, Kengo Nagamochi, Hiroshi Mazda Motor Corp Hiroshima 7308670 Japan Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

Let G = (V, E) be an undirected graph with a node set V and an arc set E. G has k pairwise disjoint subsets T-1, T-2,..., T-k of nodes, called resource sets, where vertical bar T-i vertical bar is even for each i. The partition problem with k resource sets asks to find a partition V-1 and V-2 of the node set V such that the graphs induced by V-1 and V-2 are both connected and vertical bar V-1 n T-i vertical bar = vertical bar V-2 boolean AND T-i vertical bar = vertical bar T-i vertical bar/2 holds for each i = 1. 2,..., k. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of k = 1. On the other hand, it is known that if G is (k + 1)-connected for k = 1, 2, then a bisection exists for any given resource sets, and it has been conjectured that for k >= 3, a (k + 1)-connected graph admits a bisection. In this paper, we show that for k = 3, the conjecture does not hold, while if G is 4-connected and has K-4 as its subgraph, then a bisection exists and it can be found in O(vertical bar V vertical bar(3) log vertical bar V vertical bar) time. Moreover, we show that for an arc-version of the problem, the (k + 1)-edge-connectivity suffices for k = 1, 2, 3. (c) 2007 Elsevier B.V. All rights reserved.

关键词： graph algorithm graph partition problem graph connectivity embedding

来源：评论

学校读者我要写书评

暂无评论

Semidefinite relaxations for partitioning, assignment and ordering problems

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2012年第4期10卷 321-346页

作者： Rendl, F. Alpen Adria Univ Klagenfurt Inst Math A-9020 Klagenfurt Austria

Semidefinite optimization is a strong tool in the study of NP-hard combinatorial optimization problems. On the one hand, semidefinite optimization problems are in principle solvable in polynomial time (with fixed precision), on the other hand, their modeling power allows to naturally handle quadratic constraints. Contrary to linear optimization with the efficiency of the Simplex method, the algorithmic treatment of semidefinite problems is much more subtle and also practically quite expensive. This survey-type article is meant as an introduction for a non-expert to this exciting area. The basic concepts are explained on a mostly intuitive level, and pointers to advanced topics are given. We provide a variety of semidefinite optimization models on a selection of graph optimization problems and give a flavour of their practical impact.

关键词： Combinatorial optimization Semidefinite programming graph partition problem Ordering problem

来源：评论

学校读者我要写书评

暂无评论

A new multi-level algorithm for balanced partition problem on large scale directed graphs

引用

Advances in Aerodynamics 2021年第1期3卷 398-412页

作者： Xianyue Li Yufei Pang Chenxia Zhao Yang Liu Qingzhen Dong School of Mathematics and Statistics Lanzhou UniversityLanzhouGansu730000China State Key Laboratory of Aerodynamics MianyangSichuan621000China Computational Aerodynamics Institute China Aerodynamics Research and Development CenterMianyangSichuan621000China.

graph partition is a classical combinatorial optimization and graph theory problem,and it has a lot of applications,such as scientific computing,VLSI design and clustering *** this paper,we study the partition problem on large scale directed graphs under a new objective function,a new instance of graph partition *** firstly propose the modeling of this problem,then design an algorithm based on multi-level strategy and recursive partition method,and finally do a lot of simulation *** experimental results verify the stability of our algorithm and show that our algorithm has the same good performance as *** addition,our algorithm is better than METIS on unbalanced ratio.

关键词： graph partition problem Large scale graphs Directed graphs Multi-level strategy

来源：评论

学校读者我要写书评

暂无评论

Approximability of partitioning graphs with supply and demand

引用

JOURNAL OF DISCRETE ALGORITHMS 2008年第4期6卷 627-650页

作者： Ito, Takehiro Demaine, Erik D. Zhou, Xiao Nishizeki, Takao Tohoku Univ Grad Sch Informat Sci Aoba Yama 6-6-05 Sendai Miyagi 9808579 Japan MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive "power" from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in C, and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless P = NP. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Approximation algorithm Demand FPTAS graph partition problem MAXSNP-hard Series-parallel graph Supply

来源：评论

学校读者我要写书评

暂无评论

A PARALLEL COMPUTATION BASED ON MEAN-FIELD THEORY FOR COMBINATORIAL OPTIMIZATION AND BOLTZMANN MACHINES

引用

SYSTEMS AND COMPUTERS IN JAPAN 1994年第12期25卷 86-97页

作者： QIAN, F HIRATA, H CHIBA UNIV FAC ENGNCHIBA 263JAPAN

This paper proposes a parallel mean-field approximation algorithm based on the mean-field theory. In the parallel mean-field algorithm, a stable configuration at each temperature is obtained by applying the mean-field approximation to each element in the state space of a system, so that an actual state is replaced with a mean state, and by sequentially updating the mean field. This makes the convergence of a learning process faster than those in the simulated annealing algorithm and the Boltzmann machine. This paper examines Peterson's idea from the viewpoint of the mean learning algorithm and constructs a parallel learning algorithm confirming the existence of its stable distribution. To improve the processing speed of the proposed method further, this paper introduces a new temperature scheduling method (maximum entropy cooling schedule) by reexamining the temperature schedule of the Monte Carlo process and analyzing changes of the maximum entropy at a transition of a mean field of the system. Computer simulations show that the proposed method produces the same results as the conventional method but with shorter computation time, and also that the proposed maximum-entropy cooling schedule agrees with a thermodynamic analogy.

关键词： MEAN FIELD THEORY BOLTZMANN MACHINE SIMULATED ANNEALING graph partition problem COOLING SCHEDULE

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：