New answers tagged combinatorial-optimization
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....
- 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 ...
- 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 ...
- 58.2k
Top 50 recent answers are included