-------------------------------------------------------------------------------------
We are proud to announce the release of our maximum cut data reduction
algorithms. 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. 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.
The framework is build such that the reduction rules can be easily
combined with any maximum cut solver (such as MQLib, LocalSolver or BiqMac).
* open source implementation / website
http://algo2.iti.kit.edu/schulz/maxcut/
https://github.com/Amtrix/fpt-max-cut
We are glad for any comments and error reports (or even bug fixes) that
you send us.
Damir Ferizovic, Demian Hespe, Sebastian Lamm, Matthias Mnich, Christian
Schulz, Darren Strash
Karlsruhe Institute of Technology (KIT)
Technische Universität Hamburg
University of Vienna
Hamilton College
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
