New answers tagged

0 votes

A non-trivial combinatorial optimization

This is NP-hard even for $d=1$ by reduction from the (strongly NP-hard) Product Partition problem. Lemma 1. The problem (with either objective function) is NP-hard, even for $d=1$. Proof sketch. Given ...
Neal Young's user avatar
  • 10.1k

Top 50 recent answers are included