A Modified Hopfield Network for the K-Median Problem

Cody Rossiter, The University of Western Ontario

Abstract

The k-median problem is a clustering problem where given n locations one wants to select k locations such that the total distance between every non-selected location and its nearest selected location is minimized. The problem has applications in several fields, including network design, resource allocation, and data mining.

There is currently limited research on applying neural networks to combinatorial optimization problems and we contribute by presenting a modified Hopfield network for the k-median problem. Hopfield networks are a type of neural network that can be applied to combinatorial optimization problems but often run slowly and produce poor solutions.

Our modifications address these speed and solution quality issues. We test our approach by comparing it with Haralampiev’s competition-based neural network and the local search algorithm of Arya, Garg, Khandekar, Meyerson, Munagala, and Pandit. Our network produces competitive results while running significantly faster on larger (n ≥ 300) problems. Furthermore, our network scales well and produces solutions for problems where n = 13509.