New answers tagged combinatorial-optimization
0
I do not answer the ultimate question which is to prove or disprove the conjecture. But I hereby post the dynamic programming algorithm for solving any given set of parameters.
Let $\bigg(\begin{matrix}c_B&l_B&n_B \\c_W&l_W&n_W\end{matrix}\hspace{2ex} m\bigg)$ denote the maximal expected number of defects to be found with $n_B$ black and $n_W$...
1
Because all your variables are binary, you can linearize the problem by introducing, for $i<j$, variables $y_{i,j} \ge 0$ to represent the product $x_i x_j$, together with linear constraints
\begin{align}
y_{i,j} &\le x_i\\
y_{i,j} &\le x_j\\
y_{i,j} &\ge x_i+x_j−1
\end{align}
A derivation via conjunctive normal form is given here.
Now use an ...
2
This is also too long for a comment but it shows where the real problem lies.
With the new formulation, the complementary expectation of the sum of two cut sides is just of the form
$$
\frac {\sum_i a_i^2(|\cos\theta_i|+|\sin\theta_i|)}{\max_i(a_i|\cos\theta_i|)+\max_i(a_i|\sin\theta_i|)}
$$
where $a_i$ are the sides and the angles $\theta_i$ that the sides $...
2
Let the vertices of the triangle be $A$, $B$, and $C$, which we also use for the angle measures, opposite the sides of lengths $a$, $b$ and $c$ respectively.
Suppose we know that in the ideal configuration, a horizontal line cuts the triangle at $A$, and a vertical line cuts the triangle at $B$. Let $\theta$ be the angle between the horizontal line and side $...
1
A bit too long for a comment, here's one suggestion: take $a\lt b\lt c$ and use $(0,0)$ and $(c,0)$ as two points of the triangle. The third point $(x,y)$ (taking $y\gt 0$ WLOG) can be found in whatever usual way you prefer. Now, instead of rotating the triangle, rotate the lines: we can parametrize the pencils of lines as being in the directions $(\cos\...
Top 50 recent answers are included
