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....
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 ...
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 ...
Top 50 recent answers are included
Related Tags
combinatorial-optimization × 426co.combinatorics × 166
graph-theory × 118
algorithms × 60
oc.optimization-and-control × 53
computational-complexity × 39
linear-programming × 35
reference-request × 28
linear-algebra × 28
integer-programming × 28
mg.metric-geometry × 27
discrete-geometry × 26
pr.probability × 22
nonlinear-optimization × 22
convex-optimization × 20
approximation-algorithms × 19
matrices × 16
inequalities × 16
traveling-salesman-problem × 14
extremal-graph-theory × 13
graph-colorings × 12
global-optimization × 12
np × 12
heuristics × 12
computer-science × 10