Largest differencing method: Difference between revisions

Revision as of 21:52, 18 November 2020

Revision as of 21:56, 18 November 2020

Line 2:

== An approximate algorithm ==

The '''largest differencing heuristic<ref>{{cite journal|last1=Michiels|first1=Wil|last2=Korst|first2=Jan|last3=Aarts|first3=Emile|year=2003|title=Performance ratios for the Karmarkar–Karp differencing method|journal=Electronic Notes in Discrete Mathematics|volume=13|pages=71–75|citeseerx=10.1.1.107.1332|doi=10.1016/S1571-0653(04)00442-1}}</ref>''' (also called the '''Karmarkar-Karp heuristic''') sorts the numbers in descending order. For ''k''=2, it worksoperates asin followstwo phases. ItIn the first phase, it takes the two largest numbers, removes them from ''S'', and replaces them with their difference (this represents a decision to put each of these numbers in a different subset). It proceeds in this way until a single number remains, which is the sum-difference. TheIn subsetsthe cansecond phase, the subsets beare reconstructed by [[backtracking]]. The runtime complextiy of the approximate algorithm is O(''n'' log ''n'').<ref name="hayes">{{citation|last=Hayes|first=Brian|title=The Easiest Hard Problem|date=March–April 2002|magazine=[[American Scientist]]|volume=90|issue=2|pages=113–117|publisher=Sigma Xi, The Scientific Research Society|jstor=27857621|authorlink=Brian Hayes (scientist)}}</ref>

For example, if S = {8,7,6,5,4}, then the resulting difference-sets are 6,5,4,1, then 4,1,1, then 3,1 then 2, which can be backtracked to the 2-way partitions {3},{1}, then {4},{1,1}, then {4,7}, {1,8}, then {4,7,5}, {8,6}, where the sum-difference is 2. Note that this partition is not optimal: in the partition {8,7}, {6,5,4} the sum-difference is 0.

On random instances, this approximate algorithm performs much better than [[greedy number partitioning]]. However, it is still bad for instances where the numbers are exponential in the size of the set.<ref name="hayes" />

== Implementation ==

The following [[Java (programming language)|Java]] code implements the first phase of Karmarkar–Karp. It uses a [[Heap (data structure)|heap]] to efficiently find the pair of largest remaining numbers.<syntaxhighlight lang="java">

int karmarkarKarpPartition(int[] baseArr) {

// create max heap

PriorityQueue<Integer> heap = new PriorityQueue<Integer>(baseArr.length, REVERSE_INT_CMP);

for (int value : baseArr) {

heap.add(value);

}

while(heap.size() > 1) {

int val1 = heap.poll();

int val2 = heap.poll();

heap.add(val1 - val2);

}

return heap.poll();

}

</syntaxhighlight>

== An exact algorithm ==