Questions tagged [discrete-optimization]

For questions about discrete optimization, which is a branch of optimization with discrete variables, opposed to continuous optimization in applied mathematics and computer science.

1,200 questions
Filter by
Sorted by
Tagged with
12k views

7 fishermen caught exactly 100 fish and no two had caught the same number of fish. Then there are three who have together captured at least 50 fish.

$7$ fishermen caught exactly $100$ fish and no two had caught the same number of fish. Prove that there are three fishermen who have captured together at least $50$ fish. Try: Suppose $k$th fisher ...
• 90.2k
37k views

Belt Balancer problem (Factorio)

So this question is inspired by the following thread: https://forums.factorio.com/viewtopic.php?f=5&t=25008 In it, the poster is examining an $8$-belt balancer (more on that to come) which he ...
• 4,020
1k views

square cake with raisins

Alice bakes a square cake, with $n$ raisins (= points). Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins. Note that a single ...
• 10.9k
404 views

• 93.7k
471 views

Best approximation of sum of unit vectors by a smaller subset

Let $v_1,\ldots,v_N$ be linear independent unit vectors in $\mathbb{R}^N$ and denote their scaled sum by $s_N = \frac{1}{N}\sum_{k=1}^N v_k.$ I would like to find a small subset of size $n$ among ...
• 2,747
995 views

• 1,295
149 views

In a party attended by $2015$ guests among any $5$ guests at most $6$ handshakes had been exchanged. Determine the maximal number of handshakes.

In a party attended by $2015$ guests among any $5$ guests at most $6$ handshakes had been exchanged. Determine the maximal possible number of handshakes. Turkey EGMO TST 2015 P6 Some findings: Say ...
• 90.2k
171 views

Maximal Number of Points in Co-Pareto-Front

Let $n \in \mathbb{N}$ be some big number and $d \in \mathbb{N}_{\geq 1}$ be a number of dimensions. Let furthermore $f : (\{0, \ldots, n\})^d \rightarrow \mathbb{B}$ be some monotone oracle function, ...
• 71
266 views

Find a generalized path cover of a square graph

Given a directed $n\times n$ square graph as shown in the figure with $n^2$ nodes. Find a set of directed paths $\mathcal P$ from $s$ to $t$ with the minimum cardinality (i.e, minimum number of paths ...
• 101
What's the smallest absolute value possible of a non-zero eigenvalue of an $n$ by $n$ square matrix whose entries are either $0$ or $1$ (all operations are over $\mathbb{R}$)?
Consider an integer programming problem with binary decision variables $x_1,\ldots,x_n \in \{0,1\}$. Im trying to model the constraint that enforces the maximum number of consecutive ones in ...