Related Experiment Video
Updated: Jan 23, 2026
03:31
Author Spotlight: Enhancement of Salient Object Detection for Smart Grid Applications
Published on: December 15, 2023
1.0K
An approximation algorithm for graph partitioning via deterministic annealing neural network
Zhengtian Wu1, Hamid Reza Karimi2, Chuangyin Dang3
1School of Electronic and Information Engineering, Suzhou University of Science and Technology, Suzhou, China; Department of Mechanical Engineering, Politecnico di Milano, Milan, Italy.
Summary
This study introduces a deterministic annealing neural network algorithm to find approximate solutions for the NP-hard graph partitioning problem. The novel method effectively identifies high-quality solutions, outperforming existing algorithms in simulations.
Area of Science:
- Computer Science
- Operations Research
- Artificial Intelligence
Background:
- Graph partitioning is a critical NP-hard combinatorial optimization problem with broad industrial applications.
- Existing methods for graph partitioning often struggle to find optimal or near-optimal solutions efficiently.
Purpose of the Study:
- To develop and evaluate a novel deterministic annealing neural network algorithm for solving the graph partitioning problem.
- To demonstrate the effectiveness of this new approach in obtaining high-quality approximate solutions.
Main Methods:
- The proposed algorithm utilizes a continuation method, reducing a barrier parameter from a large positive number to zero.
- It finds minimum points of a barrier problem by iteratively updating Lagrange multipliers in a feasible descent direction.
- The algorithm inherently satisfies variable bounds (0 to 1) within its iterative procedure.
Main Results:
- The deterministic annealing neural network algorithm successfully generated approximate solutions for the graph partitioning problem.
- Comparative simulations on 100 test samples showed the proposed algorithm's effectiveness against four established algorithms.
Conclusions:
- The deterministic annealing neural network algorithm offers a viable and effective approach for tackling the graph partitioning problem.
- This method provides a promising alternative for complex optimization tasks in industry and management.
Related Concept Videos
01:26Linearization and Approximation
49
Linearization is a mathematical technique used to approximate complex, nonlinear functions with simpler linear models in the vicinity of a chosen reference point. The method is based on the idea that, although a function may be difficult to evaluate exactly, its behavior near a specific input value can often be closely approximated by the tangent line at that point. This approach is particularly useful when small deviations from a known value are involved.Consider the square root function, for...
49
01:29Application of Linearization and Approximation
83
A drone flying through complex terrain often relies on more than one sensing method to estimate small changes in altitude. Along with direct measurements, air pressure provides a useful indirect indicator of vertical movement. Atmospheric pressure decreases as altitude increases, and this relationship is commonly described using an exponential model. Although accurate, converting pressure measurements into altitude values requires calculations that are too complex to perform repeatedly during...
83
01:28Accuracy, limits, and approximation
1.1K
Accuracy, limits, and approximations are common in many fields, especially in engineering calculations. These concepts are imperative for ensuring that a given value is as close as possible to its true value.
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
Accuracy is defined as the closeness of the measured value to the true or actual value. In engineering mechanics, repeated measurements are taken during theoretical or experimental analyses to ensure that the result is precise and accurate.
The accuracy of any solution is based on the...
1.1K
01:07Ogive Graph
6.7K
An ogive graph is sometimes called a cumulative frequency polygon. It is one type of frequency polygon that shows cumulative frequency. In other words, the cumulative percentages are added to the graph from left to right. An ogive graph plots cumulative frequency on the vertical y-axis and class boundaries along the horizontal x-axis. It’s very similar to a histogram; only instead of rectangles, an ogive displays a single point where the top right of the rectangle would be. Creating this...
6.7K
01:30Graphing Antiderivatives
49
The concept of an antiderivative is fundamental in calculus, describing how a function's values accumulate over time. This process is closely related to physical motion, such as the movement of a rolling ball. As the ball progresses, its position changes in response to variations in velocity, just as an antiderivative graph reflects the cumulative effect of the original function's values.Graphing an antiderivative requires interpreting how a function's values influence the shape of its...
49
01:07Bar Graph
21.5K
A bar graph is also called a bar chart and consists of bars that are separated from each other. It either uses horizontal or vertical bars to show comparisons among categories. The bars can be rectangles, or they can be rectangular boxes (used in three-dimensional plots). One axis of the graph represents the specific categories being compared, and the other axis shows a discrete value. In this graph, the length of the bar for each category is proportional to the number or percent of individuals...
21.5K