7
votes
Combinatoric Problem in Stardew Valley about Keg Layout
I will generalize your problem somewhat. Define the "threshold" of a house to be the floor square which is adjacent to the door. You specified that the threshold should be in the middle of ...
- 78.3k
7
votes
Accepted
Combinatoric Problem in Stardew Valley about Keg Layout
For a proof for the $n$ is a multiple of $3$ case, consider growing the network of white spaces one square at a time. Each new white square can make at most $3$ new squares accessible (with the ...
- 5,633
2
votes
An Optimization Problem With Permutation Function
Let $S_m$ be the $0$-$1$ matrix with $S_{i,j} = 1$ if and only if $T_{i,j} \leq m$. Then $\min_\sigma \max_i T_{\sigma(i),i} \leq m$ if and only if the bipartite graph whose bipartite adjacency matrix ...
- 6,464
2
votes
Accepted
How to extend the $p \Rightarrow q$ constraint with logical AND within the $p$ statement for Big-M method?
Here are two approaches. The first one is to impose
$$a - M(2-x-y) \le u \le b + M(2-x-y). \tag1\label1$$
The second is to introduce binary (or just nonnegative) decision variable $z$ and impose
\...
- 47.4k
1
vote
Subset of index that minimizes a sum of real values
This is the optimization version of the subset sum problem.
- 47.4k
1
vote
Generate Max Number of Sequences Separated by Hamming Distance of 3
Edit: The following doesn't work. I may not have time to get back to it for a while, sorry.
The paper by Bogdanova et al available here constructs a code demonstrating $$A_4(7,4)\geq 128,$$ on page ...
- 9,567
1
vote
Finding a new MST for $G(V,E)$ after connecting a new vertex
This is exactly one step of Prim's algorithm. There we already have a minimum spanning tree of some subset of vertices $V'$ then we consider new vertex $v$ and it's incident edges along with the ...
- 21
1
vote
Accepted
Vertex packing for higher path lengths
After precomputing the distance matrix $D$, you can solve the problem via mixed integer linear programming as follows. Let $\bar{D}=\max_{i<j} D_{ij}$. Let binary decision variable $x_i$ indicate ...
- 47.4k
1
vote
Maximal disjoint clique finding algorithm
Your question is related to the exact cover problem.
In my opinion, it is a tough ( NP-complete ) problem.
There is an algorithm ( called DLX ) to tackle this problem.
Here are some relevant links:
[1]...
- 203
1
vote
Say $E_1,...E_n\subset\{1,2,...,k\}= K$, each $|E_i|=4$ and each $j\in K$ appear in at most $3$ sets $E_i$.
The 500pt belongs to me if the following proof is correct.
We give the bound $\frac{59}{140}k<\frac{3}{7}k$ by using a randomized algorithm introduced in the book ‘Probabilistic Method’ (Section 3....
- 341
Only top scored, non community-wiki answers of a minimum length are eligible