Questions tagged [packing-and-covering]
The packing-and-covering tag has no usage guidance.
206
questions
0
votes
0
answers
62
views
Random covering on rectangles
Let $\mathrm{Rect}$ denote the class of axis-parallel rectangles $r: \mathbb{R}^2 \to \{0,1\}$, assigning $1$ if the point is inside the rectangle and $0$ otherwise. Let $\mathcal{D}$ be a ...
- 159
0
votes
0
answers
10
views
Enumerating the directed vertex-disjoint cycle covers of digraphs
A directed cycle-cover of a digraph $D$ is in the sense of this post equivalent to a perfect matching in the related undirected biadjacency graph $B$ in which the edges connect a vertex $u$ of $D$ in ...
- 12.8k
2
votes
0
answers
330
views
Who contributed [GT13] to "Computers and Intractability"?
This is a followup to my question How does the complexity of calculating the Permanent imply the NP completeness of directed 3-cycle cover?
Question:
who contributed problem [GT13] PARTITION INTO ...
- 12.8k
11
votes
1
answer
287
views
Do lattices with small covering radius have sublattices with small covering radius?
For me a lattice is a discrete subgroup of $\mathbb R^n$. The linear span of a lattice, written $\Lambda \otimes \mathbb R$, is the $\mathbb R$-vector subspace of $\mathbb R^n$ generated by $\Lambda$. ...
- 141k
5
votes
1
answer
251
views
Is the maximal packing density of identical circles in a circle always an algebraic number?
There is a lot of interest in the maximal density of equal circle packing in a circle. And I thought that knowing whether or not the solution is always algebraic or not would be useful.
My original ...
- 63
2
votes
0
answers
142
views
How many unit cubes are needed to 'hide' a unit cube fully in 3D?
Question: What is the smallest number of nonoverlapping unit cubes that can hide a unit cube C - in the sense that every ray emanating from the boundary of C meets the interior or the boundary of one ...
- 5,827
30
votes
2
answers
2k
views
Packing an upwards equilateral triangle efficiently by downwards equilateral triangles
Consider the problem of packing an upwards-pointing unit equilateral triangle "efficiently" by downwards-pointing equilateral triangles, where "efficiently" means that there is ...
- 112k
2
votes
0
answers
39
views
Covering base sets $X$ with a subset family satisfying a "partial covering property"
Let $X$ be an $n$ element base set. Suppose I have a subset family $\mathscr{F} \subset 2^X$ satisfying the following property:
(*) For any subset $Y \subset X$, we can find an element $F \in \mathscr{...
- 374
0
votes
1
answer
106
views
Fractal sets and dimensions
Can we construct two sets $E$ and $F$ meeting the following criteria
$\dim_H(E) = \dim_H(F) = \dim_H(E ∩ F)$
$\dim_P(E), \dim_P(F)$, and $\dim_P(E ∩ F)$ are distinct?
Here $\dim_H$ denotes the ...
- 39
0
votes
0
answers
34
views
Packing number lower bound for sparse vectors
Let $t \in (0, 1)$ and define $P_t(k)$ to be cardinality of the largest set of $t$-separated points (i.e., for any distinct pair of points, the Euclidean distance is strictly larger than $t > 0$) ...
- 1
0
votes
0
answers
11
views
What are known tightest bounds on packing number over hypothesis class with semi-metric distance?
Let $\mathcal{H}$ denotes a hypothesis class we define the semi-metric on $\mathcal {H}$:
$\|h_1 - h_2 \|_{\mathcal{L}_1} = \underset{x \sim \mathcal{D}}{\mathbb{P}}[h_1(x) \neq h_2(x)]$.
Are there ...
- 159
1
vote
0
answers
151
views
Optimal covering trails for every $k$-dimensional cubic lattice $\mathbb{N}^k := \{(x_1, x_2, \dots, x_n) : x_i \in \mathbb{N} \wedge n \geq 3\}$
After a dozen years spent investigating this particular class of problems, I finally give up and I wish to ask you if any improvement is achievable from here on.
The general problem is as follows:
Let ...
- 1,305
3
votes
1
answer
397
views
Electricity division and bin packing
In the electricity division problem, there is a powerhouse that supplies $s$ kilowatt of electricity. There are $n$ households. The connection size of household $i$ is $d_i$.
The problem is that $s &...
- 3,509
8
votes
3
answers
1k
views
How many non-orthogonal vectors fit into a complex vector space?
I am sitting on a problem, where I have a complex vector space of dimension $D$ and a set of normalized vectors $\{v_k\}$, $k\in\{1,2,\dots,N\}$ that are supposed to satisfy
$$\lvert\langle v_j\vert ...
11
votes
1
answer
397
views
Smallest sphere containing three tetrahedra?
What is the smallest possible radius of a sphere which contains 3 identical plastic tetrahedra with side length 1?
- 111