Approximating minimum multicuts by evolutionary multi-objective algorithms

Loading...
Thumbnail Image

Date

2008-06

Journal Title

Journal ISSN

Volume Title

Publisher

Alternative Title(s)

Abstract

It has been shown that simple evolutionary algorithms are able to solve the minimum cut problem in expected polynomial time when using a multi-objective model of the problem. In this paper, we generalize these ideas to the NP-hard minimum multicut problem. Given a set of k terminal pairs, we prove that evolutionary algorithms in combination with a multi-objective model of the problem are able to obtain a k-approximation for this problem in expected polynomial time.

Description

Table of contents

Keywords

Subjects based on RSWK

Citation