## 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