New answers tagged

2

Your greedy approach works. Let's first find an abstraction of your problem that makes it easier to come up with a proof: We have a family $F$ of sets of consecutive integers in $\{1,\ldots,k\}$ (we will call them intervals) that is closed under taking subintervals, i.e. for any $a\leq b\leq c\leq d$, if $\{a,\ldots,d\} \in F$, then $\{b,\ldots,c\} \in F$ ...


0

I found an FPTAS for a very similar problem: finding a partition such that the largest sum is as small as possible. This problem is equivalent to the problem of identical-machines scheduling: there are $m$ identical machines (in our case $m=3$), and $n$ jobs with different processing times, and we need to assign jobs to machines such that the latest ...


Top 50 recent answers are included