A heuristic method for solving the problem of partitioning graphs with supply and demand
From MaRDI portal
Publication:256649
DOI10.1007/S10479-015-1930-5zbMATH Open1332.90327arXiv1411.1080OpenAlexW1558032106MaRDI QIDQ256649FDOQ256649
Authors: Raka Jovanovic, Abdelkader Bousselham, Stefan Voß 
Publication date: 9 March 2016
Published in: Annals of Operations Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1411.1080
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
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Cites Work
- An Efficient Heuristic Procedure for Partitioning Graphs
- Approximability of partitioning graphs with supply and demand
- A bionomic approach to the capacitated \(p\)-median problem
- Lock-gain based graph partitioning
- Minimum cost partitions of trees with supply and demand
- Generating partitions of a graph into a fixed number of minimum weight cuts
- Computing finest mincut partitions of a graph and application to routing problems
- Expanding neighborhood GRASP for the traveling salesman problem
- A scatter search heuristic for the capacitated clustering problem
- A New Heuristic for Partitioning the Nodes of a Graph
- Modelling the power supply network -- hardness and approximation
- Parametric power supply networks (extended abstract)
- Tree \(t\)-spanners in outerplanar graphs via supply demand partition
- A method for solving traveling-salesman problems
- PARTITIONING TREES OF SUPPLY AND DEMAND
- An efficient memetic algorithm for the graph partitioning problem
- Balanced graph partitioning
Cited In (5)
- Partitioning of supply/demand graphs with capacity limitations: an ant colony approach
- A strongly polynomial time algorithm for the maximum supply rate problem on trees
- A heuristic approach for dividing graphs into bi-connected components with a size constraint
- Partition on trees with supply and demand: kernelization and algorithms
- A mixed integer program for partitioning graphs with supply and demand emphasizing sparse graphs
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)
