Benchmark for the k-cut problem

This page compares the performance of several heuristics, which can be downloaded from this page.

The evaluated instances are hypergraphs with 100 to 400 vertices and 500 to 1000 hyperedges. These instances are available here.

The heuristics were tested for two values of k: k = 10 and k = 50. The tables below present a side-by-side comparison of their performance, including solution cost and computation time.

Detailed results for k = 10 are available here, and for k = 50, they are available here.

Performance Comparison of Heuristics for k = 10

	Solution Cost				CPU (in seconds)
Heuristic	Fast	GHT	Hyb	Pack	Fast	GHT	Hyb	Pack
Instance
h_100_1000	965	961	961	961	0.001	0.098	0.100	0.053
h_100_500	438	436	436	438	0.001	0.050	0.075	0.025
h_200_1000	439	439	439	439	0.002	0.200	0.300	0.100
h_200_500	129	129	129	129	0.001	0.100	0.500	0.300
h_400_1000	124	124	124	124	0.003	0.400	1.900	1.500
h_400_500	41	40	40	40	0.002	0.200	5.700	5.400

Performance Comparison of Heuristics for k = 50

	Solution Cost				CPU (in seconds)
Heuristic	Fast	GHT	Hyb	Pack	Fast	GHT	Hyb	Pack
Instance
h_100_1000	4020	4066	4066	4066	0.011	0.100	0.200	0.060
h_100_500	1897	1878	1878	1878	0.003	0.054	0.079	0.028
h_200_1000	2236	2236	2236	2223	0.010	0.200	0.300	0.100
h_200_500	951	947	941	947	0.004	0.100	0.500	0.400
h_400_1000	921	909	900	909	0.008	0.400	1.900	1.500
h_400_500	344	341	347	342	0.004	0.300	6.600	6.400