Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to express an integer $n$ as the sum of integers $x_i$ below some threshold $t$, minimizing the number of $x$s, and maximizing a lower threshold $q$.

$$\min_{\# x} \max_{q} : \sum_i x_i = n \quad q\le x_i\le t$$

For example $n=7$, $t=3$ includes the cases $x=(2,1,1,1,1,1)$ which is too long, $x=(3,3,1)$ with $q=1$ and $x=(3,2,2)$ with $q=2$ which is the optimal solution.

(it's part of an FFT planner: kernels of different sizes can be combined where performance degrades for kernels larger than $t$, but using smaller kernels isn't optimal either, $3,3,1$ performs worse because of $1$ than $3,2,2$ would, for example, which is why $q$ should be maximized.)

Minimizing the number is trivial: $\#x = \lceil n/t\rceil$, so the problem becomes

$$\max_q : \sum_i x_i = n \quad q \le x_i \le t$$

I can't think of a way to maximize $q$ that isn't completely naive. Not sure what keywords I could use to look for a solution to this…

share|improve this question

1 Answer 1

up vote 1 down vote accepted

It is not clear whether you must have $x_i \lt t$ or is $x_i=t$ acceptable. I will assume $x_i=t$ is acceptable, but the changes for strictly less are easy-just set $t'=t-1$ and follow along.

You are right, the number of terms is $\#x= \lceil n/t\rceil$. Then if all the $x_i=t$ the sum will be $t\#x$, so you need to remove $r=t\#x-n$. To maximize $q$ you should spread this as evenly as possible, so you remove $\lfloor \frac r{\#x} \rfloor$ from all of them, which leaves you $r-\#x\lfloor \frac r{\#x} \rfloor$ to go and you can remove one more from each of that many $x_i$. It may sound naive, but it works. The result is that you have $$\#x= \lceil n/t\rceil\\r=t\#x-n$$

Leading to the partition $$\\r-\#x\lfloor \frac r{\#x} \rfloor \text { copies of }t-\lfloor \frac r{\#x} \rfloor-1\\ \#x-r+\#x\lfloor \frac r{\#x} \rfloor \text { copies of }t-\lfloor \frac r{\#x} \rfloor$$

share|improve this answer
    
and I was already trying to press this into some dynamic programming scheme, missed the forest for the trees there, thanks –  pascal Feb 5 '13 at 3:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.