All Questions
Tagged with combinatorics algorithms
1,042
questions
0
votes
0
answers
13
views
Counting cliques in polynomial time
Let $G$ be a disconnected graph such that every connected component is a $k$-clique, $k \geq 2$. That is, a connected component of $G$ can be a single edge, or a triangle, or a $K_4$ and so on. Is it ...
- 339
4
votes
0
answers
58
views
+50
What is the current best algorithm to find if a simply connected region is uniquely tileable with dominoes?
I was reading both Thurston's and Fournier's papers on algorithms which detect whether or not a simply connected region is tileable using dominoes (1 by 2 rectangles) when I came across the section in ...
- 365
2
votes
0
answers
40
views
Dividing $N$ coins into at most $K$ groups such that I can get any number of coins by selecting whole groups
Problem
Inspired from Dividing $100$ coins into $7$ groups such that I can choose any number of coins by selecting whole groups . I am interested in the number of possible ways we can get such a split....
- 1,153
1
vote
0
answers
27
views
Knapsack with fixed number of bins?
Constant: d, a fixed number of bins/sacks
Input:
$v_1,v_2,...,v_n$ item profits,
$0<w_1,w_2,...,w_n\leq1$ item weights.
Output: $B_1,B_2,...,B_d$ which are d subsets of $\{1,2,...,n\}$ s.t. they ...
- 11
1
vote
1
answer
33
views
Testing for strong homomorphism in polynomial time
Let $G$ and $H$ be graphs. We say that a map $f:V(G)\rightarrow V(H)$ is a strong homomorphism if for all $u,v\in V(G)$ it holds that $(u,v)\in E(G)$ if, and only if, $(f(u),f(g))\in E(H)$.
Fix $H$ ...
- 823
0
votes
0
answers
35
views
Minimum number of measurements required to find heaviest and lightest from a group of idetntical looking balls having distinct weights.
You are given 68 identical looking balls, each with a distinct weight. You are given a common balance using which you can compare weights of any two pair of balls with a single measurement. Describe ...
- 9
2
votes
0
answers
44
views
Does every collection of edges between two sets of vertices in a plane have a "perimeter" edge suitable for induction inwards?
Joel Hamkins posted this nice problem: https://x.com/JDHamkins/status/1790582025977577591
I quote:
Suppose you have 1000 white points and 1000 black points in the plane, no three collinear. Can you ...
- 9,315
3
votes
1
answer
161
views
How to solve a given combinatorial problem?
Given $n$ balls, which are numbered from $1$ to $n$, and also $n$ boxes, which are also numbered from $1$ to $n$. Initially, $i$-th ball is placed at $i$-th box. Then we are doing the following ...
- 33
1
vote
0
answers
86
views
Is there a measure that produces given values (probabilities or cardinals) for sets $A_1,\dots, A_n$ and all their intersections $A_i\cap A_j, ... $?
Assume that values (e.g., probabilities or cardinals) of a measure on a finite set $\Omega$ are given for sets $A_1,\dots, A_n$ and all of their intersections $A_i, A_i\cap A_j, A_i\cap A_j\cap A_k, ....
- 8,340
1
vote
1
answer
44
views
find the number of ways to distribute 30 students into 6 classes where there is max 6 students per classroom
here is the full question:
Use inclusion/exclusion to find the number of ways of distributing 30
students into six classrooms assuming that each classroom has a maximum capacity
of six students.
Let $...
- 15
0
votes
1
answer
35
views
create a recurrence relation for the number of ways of creating an n-length sequence with a, b, and c where "cab" is only at the beginning
This is similar to a problem called forbidden sequence where you must find a recurrence relation for the number of ways of creating an n-length sequence using 0, 1, and 2 without the occurrence of the ...
- 15
1
vote
1
answer
73
views
Generate superset with maximum overlap
I have a set $S$ with a total of 20000 items. I am also given a list $L$ of 0.5 million sets, with each set having 1-20 elements from the original set. I am given an integer $n$. Now I need a new set $...
- 129
0
votes
1
answer
56
views
Reordering algorithm to fragment consecutive sequences of ones as much as possible
Recently, I came across the following problem:
Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$.
We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$.
We call a &...
- 1
0
votes
1
answer
26
views
Choosing k elements with multiple weights maximizing the minimum weight
Consider the following optimisation problem.
Given a set $S$ with $q$ weight functions $w_1, \ldots, w_q: S\rightarrow \mathbb{R}_+$ and a constant $1\leq k\leq |S|-1$.
Find an $X\subset S, |X|=k$ ...
- 31
0
votes
0
answers
21
views
One to one mapping that maximize the minimum absolute difference
Given two sequences $a_0 \leq a_1 \leq \ldots \leq a_{n-1}$ and $b_0 \leq b_1 \leq \ldots \leq b_{n-1}$. We want to find a one-to-one mapping $\pi:[n-1] \rightarrow [n-1]$ such that
$$
\max \min_{i} |...
