New answers tagged

1 vote

Can we say this nonlinear integer programming problem is NP-hard?

It is NP-hard. Below is a reduction from the partition problem. The partition problem asks for a list of positive integers $x_1,\dots,x_n$ whether it can be partitioned into two subsets with equal sum....
icecuber's user avatar
  • 128
0 votes

Reliability of ILP approach to number-theoretic optimization

I would suggest using exact ILP solvers to rule out errors that are rooted in limited precision. QSopt_ex for example works with exact rational numbers. Another more recent exact solver is SCIP of the ...
Manfred Weis's user avatar
  • 12.4k
1 vote
Accepted

Maximizing a sum minus its maximal summand

It is true. The proof rests on several observations. The first one is that if you want to maximize $\sum_i i\pi_i$ under the condition $\pi_j\le B_i$ with any prescribed $B_i$, then your best bet is ...
fedja's user avatar
  • 58.2k

Top 50 recent answers are included