<p>Kim and Moon (2004) compare variants of Kernighan-Lin which combine the usual gain and a lock-based gain, which is relative to the locked vertices. You can combine two gain functions in the range $-n\ldots n$ using an implementation of Fiduccia-Matheyses with $O(n^2)$ buckets.</p>

<p>Kim, Moon, <a href="http://dx.doi.org/10.1023/B%3aHEUR.0000019985.94952.eb" rel="nofollow">Lock-gain based Graph Partitioning</a>, J Heuristics, 10, 37-57, 2004.</p>

CC BY-SA 2.5
2010-11-24T00:49:06.120Z
2010-11-24T00:49:06.120Z
Marcus Ritt
<p>I want to know if there is an algorithm like KERNIGHAN-LIN for graph partitioning that can handle several (different) gain functions.</p>

<p>Is there some technique to combine gain functions in one algorithm?</p>

<p>The KL algorithm and its gain function is defined here for example:</p>

<p><a href="http://www.cs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html#link_4.2" rel="nofollow">http://www.cs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html#link_4.2</a></p>

CC BY-SA 2.5
2010-11-23T17:13:23.123Z
Could you please provide some motivation and explain why you are interested in this question?
Kaveh
CC BY-SA 2.5
2010-11-24T01:37:37.657Z
My guess would be that the OP wants to use the Kernighan-Lin algorithm to do multi-criterion optimization.
Peter Shor 
<graph-theory><graph-algorithms>
Kernighan–Lin algorithm and multiple gain functions
YAKOVM
# Kernighan–Lin algorithm and multiple gain functions

(Asked by: username_0 on 2010-11-23)

I want to know if there is an algorithm like KERNIGHAN-LIN for graph partitioning that can handle several (different) gain functions.

Is there some technique to combine gain functions in one algorithm?

The KL algorithm and its gain function is defined here for example:

<http://www.cs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html#link_4.2>

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Could you please provide some motivation and explain why you are interested in this question?  
> **username_2**: My guess would be that the OP wants to use the Kernighan-Lin algorithm to do multi-criterion optimization.  

---

## 1 answers

### Answer by username_3 on 2010-11-24. Score: 5 | Accepted answer

Kim and Moon (2004) compare variants of Kernighan-Lin which combine the usual gain and a lock-based gain, which is relative to the locked vertices. You can combine two gain functions in the range $-n\ldots n$ using an implementation of Fiduccia-Matheyses with $O(n^2)$ buckets.

Kim, Moon, [Lock-gain based Graph Partitioning](http://dx.doi.org/10.1023/B%3aHEUR.0000019985.94952.eb), J Heuristics, 10, 37-57, 2004.


---

