All Questions
24
questions
14
votes
1
answer
337
views
$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.
$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.
There was no information about $n$ in a original problem.
Attempt: Choose at random and ...
- 90.7k
1
vote
1
answer
54
views
Minimize the sum of components of a hypercube under a system of $0,1$ equations.
Let $x_1, \dots, x_5, y_1, \dots, y_4$ be a total of nine variables taking values merely in $\{0, 1\} \subset \Bbb{Z}$. Therefore a solution is a point on a hypercube.
These are the constraint ...
0
votes
0
answers
31
views
What is the name of following optimization problem and algorithms to solve them
Let $S=\{1,\ldots,n\}$ be a set and $w_i (\geq 0)$ be the weight of element $i$. Let $R_j, j = 1,\ldots,m$ be subsets of $S$, called the restriction sets. Choose elements from set $S$ to maximize ...
- 101
15
votes
2
answers
1k
views
Domination problem with sets
Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
of $M$, satisfying:
(1) $|S_i|\leq 3,i=1,2,...,k$
(2) Any element of $M$ is an element of at least $4$ sets among
$S_1,....,...
- 90.7k
2
votes
1
answer
962
views
Optimal permutation of sequence using a graph based approach
I am stuck with an optimization problem in one of my projects which requires me to find a permutation $\Sigma = \{x_{\sigma_1}, x_{\sigma_2}, \ldots, x_{\sigma_N}\}$ of a sequence $\{x_1, x_2, \ldots, ...
- 482
1
vote
1
answer
78
views
Groups that cover weighted set
I am trying to find an efficient algorithm to give solutions to the following problem.
There is a set of unknown groups of elements $g_1$, $g_2$, $g_3$, etc. that together contain and cover a set of ...
- 11
3
votes
3
answers
129
views
Efficient algorithm for optimization problem.
I had an interesting interview problem today. Let's assume that we have n boxes, containing many numbers. For instance, let's say $n=4$, and four boxes contain the following numbers:
...
- 391
4
votes
1
answer
395
views
Algorithm to find shortest path to net values across nodes
I have an undirected graph $G = (V, E)$ with nodes $V$ and edges $E$.
Each node $v$ has an associated number $n_v \in \mathbf{Z}$
Let us define for any two nodes $v, w \in V$ connected by an edge $e ...
- 595
2
votes
2
answers
689
views
Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version
I am coordinating cookie-baking events with kindergarten kids. This turns out to be a challenging problem, and I could use a little help:
We would like a general way of creating 'fair' cookie-baking ...
- 123