New answers tagged ds.algorithms
1
If you want to solve this in practice, you could express it as as an instance of integer linear programming and solve with an ILP solver.
Let's see how to test whether there is a way to fit $n$ channels in the given range, using an ILP solver. (You can then use binary search on $n$.) Introduce $n$ variables, $f_1,\dots,f_n$, to represent the $n$ ...
6
Theorem 1. The given problem is NP-hard, by reduction from MAX-CUT.
Proof. Call the given problem Positive Discrepancy Cut (PDC). Define weighted PDC to be the generalization where the input is a graph $G=(V,E)$ with polynomially bounded (possibly negative) integer edge weights, and the goal is to determine whether there is a positive-weight cut. To prove ...
Top 50 recent answers are included
