-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
executable file
·141 lines (110 loc) · 8.5 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Design by Free CSS Templates
http://www.freecsstemplates.org
Released for free under a Creative Commons Attribution 2.5 License
Name : Old Stairwell
Description: A two-column, fixed-width design with dark color scheme.
Version : 1.0
Released : 20130313
-->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="google-site-verification" content="TKhkDFKyhvcrubOqVQVf7xQG4bUSzAuJlXiN4_Ts7yQ" />
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Data Reduction for Maximum Cut</title>
<meta name="keywords" content="Maximum cut, algorithm engineering, kernelization, data reduction" />
<meta name="description" content="The main project data reduction for maximum cut." />
<link rel="shortcut icon" type="image/x-icon" href="favicon.ico">
<link href="http://fonts.googleapis.com/css?family=Open+Sans:400,300,600,700" rel="stylesheet" type="text/css">
<link href="default.css" rel="stylesheet" type="text/css" media="all" />
<!--[if IE 6]>
<link href="default_ie6.css" rel="stylesheet" type="text/css" />
<![endif]-->
</head>
<body>
<div id="wrapper">
<div id="header">
<div id="logo">
<h1><a href="#" style="color:red">Data Reduction for Maximum Cut</a> </h1>
Damir Ferizovic, Demian Hespe, Sebastian Lamm, Matthias Mnich, Christian Schulz, Darren Strash
</div>
</div>
<div id="page">
<div id="content">
<h2>Overview</h2>
The (unweighted) Max Cut problem is to partition the vertex set of a given graph G=(V,E) into two sets S and V \ S so as to maximize the total number of edges between those two sets. Such a partition is called a maximum cut. Computing a maximum cut of a graph is a well-known problem in the area of computer science; it is one of Karp's 21 NP-complete problems. Furthermore, its weighted variant is one of Karp's 21 NP-complete problems. </br> </br>
Kernelization is a general theoretical framework for preprocessing instances of NP-hard problems into (generally smaller) instances with bounded size, via the repeated application of data reduction rules. For the fundamental Max Cut problem, kernelization algorithms are theoretically highly efficient for various parameterizations. However, the efficacy of these reduction rules in practice---to aid solving highly challenging benchmark instances to optimality---remains entirely unexplored.
We engineered a new suite of efficient data reduction rules that subsume most of the previously published rules, and demonstrate their significant impact on benchmark data sets, including synthetic instances, and data sets from the VLSI and image segmentation application domains. Our experiments reveal that current state-of-the-art solvers can be sped up by up to multiple orders of magnitude when combined with our data reduction rules. On social and biological networks in particular, kernelization enables us to solve four instances that were previously unsolved in a ten-hour time limit with state-of-the-art solvers; three of these instances are now solved in less than two seconds. Here, we provide the implementation of the algorithms.
<br>
<br>
<br><br>
<b style="color:red">News:</b> <br>
<b> 8th January 2024:</b> We moved this website to github. <br>
<b> 7th January 2020:</b> Our paper has been presented at ALENEX'20. <br>
<b> 8th January 2020:</b> Initial release of code. <br>
<b>26th May 2019:</b> Published ArXiv Report. Link to <a href="https://arxiv.org/abs/1905.10902">PDF</a>.<br>
<p></p>
<br>
<h2>License</h2>
The program is licenced under MIT. <br>
If you publish results using our algorithms, <b>please acknowledge</b> our work by quoting the following paper (<a href="http://arxiv.org/pdf/1702.04164.pdf">PDF</a>):<br><br>
<b> @inbook{doi:10.1137/1.9781611976007.3, <br>
             author = {Damir Ferizovic and Demian Hespe and Sebastian Lamm and Matthias Mnich and Christian Schulz and Darren Strash}, <br>
             title = {Engineering Kernelization for Maximum Cut}, <br>
             booktitle = {2020 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX)}, <br>
             chapter = {}, <br>
             pages = {27-41},<br>
             doi = {10.1137/1.9781611976007.3},<br>
             URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611976007.3},<br>
             eprint = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.3}<br>
}
<!--</b>-->
<!--<b>@inproceedings{maxCutDataReduction2020, <br>-->
<!--             author = {Damir Ferizovic and -->
<!--Demian Hespe and -->
<!--Sebastian Lamm and -->
<!--Matthias Mnich and -->
<!--Christian Schulz and -->
<!--Darren Strash},<br> -->
<!--             title = {Engineering Kernelization for Maximum Cut}, <br>-->
<!--             booktitle = {Proceedings of Algorithm Engineering and Experimentation (ALENEX'20), 2020}, <br>-->
<!--             year = {2020}, <br>-->
<!--             url = {http://arxiv.org/abs/1905.10902}, <br>-->
<!--             archivePrefix = {arXiv}, <br>-->
<!--             eprint = {1905.10902}<br>-->
<!--}</b>-->
<br><br>
</ul>
<p></p>
<h2>Download</h2>
<ul>
<li> Code available on GitHub <a href="https://github.com/DataReductionMaxCut/fpt-max-cut">here</a>
</ul>
<h2>Support</h2>
<ul>
<li> Write us an <a href="mailto:[email protected]?subject=SupportRequestMaxCut">email</a> if you need support!
<li>We are glad for any comments and error reports (or even bug fixes or feature requests) that you send us.
</ul>
<h2>Other Open Source Projects</h2>
<ul>
<li> <a href="https://kahip.github.io">KaHIP</a> -- Karlsruhe High Quality Partitioning
<li> <a href="https://kahip.github.io">ParHIP</a> -- Parallel High Quality Partitioning
<li> <a href="https://karlsruhemis.github.io">KaMIS</a> -- Karlsruhe Maximum Independent Sets
<li> <a href="https://karlsruhelongestpaths.github.io">KaLP</a> -- Karlsruhe Longest Paths
<li> <a href="https://vieclus.github.io">VieClus</a> -- Vienna Graph Clustering
<li> <a href="https://karlsruhedraw.github.io">KaDraw</a> -- Karlsruhe Graph Drawing
<li> <a href="https://viennamapping.github.io">VieM</a> -- Vienna Process Mapping
<li> <a href="https://github.com/sebalamm/KaGen/"> KaGen </a> -- Karlsruhe Graph Generation
<li> <a href="https://github.com/kahypar/kahypar"> KaHyPar </a> -- Karlsruhe Hypergraph Partitioning
</ul>
</a>
</div>
</div>
<div id="footer">
<p>Copyright (c) 2020. Site maintained by Christian Schulz. All rights reserved. Initial release: January 2024. See main site for impressum. Design by <a href="http://www.freecsstemplates.org">FCT</a>.</p>
</div>
</div>
</body>
</html>