I'm a little stumped on this question (and I don't know the name of it, which is why I've excluded it from the title). I need to describe an algorithm that finds a solution to an NP-Hard problem given an oracle that can solve the decision problem. Here is the problem :

Suppose two $n\times2$ arrays $A$ and $B$ represent sales amounts for two products A and B respectively. In year $i$, strategy 1 sees A sell $A[i][1]$ units and B sell $B[i][1]$ units; similarly, in strategy 2, A sells $A[i][2]$ units and B sells $B[i][2]$ units. A long-term strategy, $L$, is an $n$-element array $S$, where $S[i]$ denotes the chosen strategy for year $i$ (i.e. if $S[i] = 1$, then strategy 1 is chosen for year $i$).

The goal is to minimise the difference in sales figures between product A and B over an $n$ year period. We want to find if the absolute difference between sales figures is less than some value $s$:

$$ \left |\sum_{i=1}^nA[i][L[i]] - \sum_{i=1}^nB[i][L[i]] \right| \leq s $$

An oracle exists that can solve any instance of the decision problem. It takes $A, B, s$ parameters, returning TRUE if a solution exists for the inputs. Write an algorithm that outputs a long-term strategy $L$ with an imbalance of at most $s$ if one exists, using the oracle. Analyse time complexity.

I've already proven that the problem is NP-hard, by proving a polynomial-time Karp reduction from the Partition problem. I'm not sure where to go from here...

  • $\begingroup$ Have you seen any examples of search-to-decision reductions? Try to follow them. Usually you guess a small part of the solution, and use the decision oracle to check whether the guess leads to a solution. If so, you simplify the instance, and repeat. $\endgroup$ – Yuval Filmus May 5 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.