A heuristic method for solving the problem of partitioning graphs with supply and demand

DOI10.1007/S10479-015-1930-5MaRDI QIDQ256649zbMATH OpenOpenAlexFDO

Authors Raka Jovanovic, Abdelkader Bousselham, Stefan Voß

Publication date 9 March 2016

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.1080

zbMATH Keywords

greedy algorithmdemand nodegraph partitioningsupply node

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: In this paper we present a greedy algorithm for solving the problem of the maximum partitioning of graphs with supply and demand (MPGSD). The goal of the method is to solve the MPGSD for large graphs in a reasonable time limit. This is done by using a two stage greedy algorithm, with two corresponding types of heuristics. The solutions acquired in this way are improved by applying a computationally inexpensive, hill climbing like, greedy correction procedure. In our numeric experiments we analyze different heuristic functions for each stage of the greedy algorithm, and show that their performance is highly dependent on the properties of the specific instance. Our tests show that by exploring a relatively small number of solutions generated by combining different heuristic functions, and applying the proposed correction procedure we can find solutions within only a few percent of the optimal ones.

Recommendations

• A mixed integer program for partitioning graphs with supply and demand emphasizing sparse graphs
• Partitioning of supply/demand graphs with capacity limitations: an ant colony approach
• Partitioning graphs of supply and demand
• An efficient approach for large scale graph partitioning
• Approximability of partitioning graphs with supply and demand

Cites work

• A New Heuristic for Partitioning the Nodes of a Graph
• A bionomic approach to the capacitated \(p\)-median problem
• A method for solving traveling-salesman problems
• A scatter search heuristic for the capacitated clustering problem
• An Efficient Heuristic Procedure for Partitioning Graphs
• An efficient memetic algorithm for the graph partitioning problem
• Approximability of partitioning graphs with supply and demand
• Balanced graph partitioning
• Computing finest mincut partitions of a graph and application to routing problems
• Expanding neighborhood GRASP for the traveling salesman problem
• Generating partitions of a graph into a fixed number of minimum weight cuts
• Lock-gain based graph partitioning
• Minimum cost partitions of trees with supply and demand
• Modelling the power supply network -- hardness and approximation
• PARTITIONING TREES OF SUPPLY AND DEMAND
• Parametric power supply networks (extended abstract)
• Tree \(t\)-spanners in outerplanar graphs via supply demand partition

Cited in

(5)

• Partitioning of supply/demand graphs with capacity limitations: an ant colony approach
• A heuristic approach for dividing graphs into bi-connected components with a size constraint
• A strongly polynomial time algorithm for the maximum supply rate problem on trees
• A mixed integer program for partitioning graphs with supply and demand emphasizing sparse graphs
• Partition on trees with supply and demand: kernelization and algorithms

This page was built for publication: A heuristic method for solving the problem of partitioning graphs with supply and demand

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q256649)