Multilevel graph partitioning: an evolutionary approach

Date

2005-05-01

Author

Kucupetek, S
Polat, Faruk
Oguztuzun, H

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

158
views

0
downloads

The graph partitioning problem is defined as that of dividing the vertices of an undirected graph into a set of balanced parts through the removal of a set of edges, whose size is to be minimized. A number of researchers have investigated multilevel schemes, which coarsen the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partitioning of the original graph. In this paper, a genetic algorithm for the coarsening phase of a multilevel scheme for graph partitioning is presented. The proposed approach has been demonstrated to improve the solution quality at the expense of running time.

Subject Keywords

Marketing, Management Science and Operations Research, Strategy and Management, Management Information Systems

URI

https://hdl.handle.net/11511/45955

Journal

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY

DOI

https://doi.org/10.1057/palgrave.jors.2601837

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

Multi-objective integer programming: A general approach for generating all non-dominated solutions Oezlen, Melih; Azizoğlu, Meral (Elsevier BV, 2009-11-16) In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical epsilon-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical epsilon-constraint method on the bi-objective integer programming problem for the sake of comple...
Neural network calibrated stochastic processes: forecasting financial assets Giebel, Stefan; Rainer, Martin (Springer Science and Business Media LLC, 2013-03-01) If a given dynamical process contains an inherently unpredictable component, it may be modeled as a stochastic process. Typical examples from financial markets are the dynamics of prices (e.g. prices of stocks or commodities) or fundamental rates (exchange rates etc.). The unknown future value of the corresponding stochastic process is usually estimated as the expected value under a suitable measure, which may be determined from distribution of past (historical) values. The predictive power of this estimati...
An efficient algorithm for the capacitated single item dynamic lot size problem Kırca, Ö. (Elsevier BV, 1990-3) A dynamic programming based algorithm is developed for the single item lot size problem with concave costs and arbitrary capacities. By making use of the extreme point properties of the problem, first the set of all feasible cumulative production levels that may occur in an optimal solution is generated. In the second stage, a dynamic programming procedure is carried out over this set. The worst case computational effort is equal to that of the standard dynamic programming approach but extensive computation...
A NEW HEURISTIC APPROACH FOR THE MULTIITEM DYNAMIC LOT-SIZING PROBLEM KIRCA, O; KOKTEN, M (Elsevier BV, 1994-06-09) In this paper a framework for a new heuristic approach for solving the single level multi-item capacitated dynamic lot sizing problem is presented. The approach uses an iterative item-by-item strategy for generating solutions to the problem. In each iteration a set of items are scheduled over the planning horizon and the procedure terminates when all items are scheduled. An algorithm that implements this approach is developed in which in each iteration a single item is selected and scheduled over the planni...
An interactive approach for multiobjective decision making Koksalan, M; Karasakal, Esra (Informa UK Limited, 2006-05-01) We develop an interactive approach for multiobjective decision-making problems, where the solution space is defined by a set of constraints. We first reduce the solution space by eliminating some undesirable regions. We generate solutions (partition ideals) that dominate portions of the efficient frontier and the decision maker (DM) compares these with feasible solutions. Whenever the decision maker prefers a feasible solution, we eliminate the region dominated by the partition ideal. We then employ an inte...

Citation Formats

S. Kucupetek, F. Polat, and H. Oguztuzun, “Multilevel graph partitioning: an evolutionary approach,” JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, pp. 549–562, 2005, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/45955.