Largest differencing method: Difference between revisions

Revision as of 08:09, 15 October 2021

Revision as of 08:10, 15 October 2021

Line 82:

== Min-max subsequence problem ==

In the ''min-max subsequence problem'', the input is a multiset of ''n'' numbers and an integer parameter ''k'', and the goal is to order the numbers such that the largest sum of each block of adjacent ''k'' numbers is as small as possible. The problem occurs in the design of video servers.<ref>Wil Michiels (2004). "Performance Ratios for Differencing Methods". Technische Universiteit Eindhoven, 2004. https://www.elibrary.ru/item.asp?id=8860464</ref> This problem can be solved in polytime for ''k''=2, but it is strongly NP-hard for ''k≥''3. A variance of the differencing method can applied to this problem.<ref>{{Cite journal|last=Michiels|first=Wil|last2=Korst|first2=Jan|date=2001|title=Min–max subsequence problems in multi-zone disk recording|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/jos.80|journal=Journal of Scheduling|language=en|volume=4|issue=5|pages=271–283|doi=10.1002/jos.80|issn=1099-1425}}</ref>

== 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 ==