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

#### Related Tags

combinatorial-optimization × 260co.combinatorics × 101

graph-theory × 65

algorithms × 31

oc.optimization-and-control × 29

computational-complexity × 28

linear-programming × 22

reference-request × 19

linear-algebra × 16

convex-optimization × 16

discrete-geometry × 15

nonlinear-optimization × 15

mg.metric-geometry × 14

matrices × 13

integer-programming × 13

pr.probability × 11

global-optimization × 9

approximation-algorithms × 9

np × 8

graph-colorings × 7

nt.number-theory × 5

computer-science × 5

additive-combinatorics × 5

extremal-graph-theory × 5

bipartite-graphs × 5