All Questions
Tagged with co.combinatorics packing-and-covering
32 questions
2
votes
0
answers
48
views
Maximum coverage of an orthogonal polygon using $k$ rectangles
I have an orthogonal polygon (all edges are horizontal or vertical) which is convex (no holes in any row of column of the polygon).
I would like to cover as much as possible of this orthogonal polygon ...
- 21
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{...
- 384
3
votes
1
answer
406
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,549
1
vote
0
answers
137
views
A comparison between packing and covering as classes of problems
We continue from Bounds for the Dispersal Problem in convex regions and Bounds for minimax facility location in a convex region
Let us consider the classes of problems:
Given a convex region $R$ and ...
- 5,979
0
votes
1
answer
182
views
A variation of Set Cover
Suppose we have $n$ sets $\{S_i\}_{i=1}^n$, each containing exactly $k$ of the numbers from $1,...,n$. The union of all these sets will cover $1,...,n$. We know $i \in S_i$ for all $i$. We need to ...
- 1
5
votes
1
answer
230
views
Covering unit-radius balls with unit-diameter objects
Let $d$ be a norm-based metric in $\mathbb{R}^2$. We are given a $d$-ball with radius 1, and we would like to cover it with objects with diameter 1. How many objects are needed?
In the $\ell_1$ metric,...
- 3,549
4
votes
0
answers
144
views
Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$
We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...
- 1,677
7
votes
1
answer
186
views
$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary
Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...
- 1,677
2
votes
2
answers
273
views
Number of edge-disjoint cycles in a holey graph
Let $\Gamma$ be a connected graph with $H^1(\Gamma) \cong \mathbb{Z}^d$. Can we give a lower bound (preferably of the form $\gg d$) on the maximal number of edge-disjoint cycles one can find in $\...
- 20.2k
22
votes
1
answer
886
views
Happy ants never leave compact domain?
I am curious if the following seemingly simple question has an easy answer?
Consider an ant population of $N$ ants that lives in $\mathbb R^2$. Each ant can be labeled by some coordinate $x\in \mathbb ...
- 124
7
votes
1
answer
1k
views
Elementary precise estimate of the covering number of euclidean balls by hypercubes
I am looking for a straightforward way to upper bound the covering number of a $d$-dimensional euclidean ball by $\ell_\infty$-balls of radius $\varepsilon$, which I will call cubes of sidelength $2\...
- 172
1
vote
1
answer
347
views
Upper bounds for high-dimensional spherical codes given the covering radius
I assume that this sort of question has already been considered at great length. Nevertheless, I could not find an answer to this question in the related literature.
Given a constant $a\in (0,2]$, ...
- 1,677
2
votes
0
answers
131
views
Optimal way to group points in the plane into clusters
Consider a strictly decreasing sequence $d = (d_k)_{k\ge 1}$ of distances in $(0,1)$. Given a constant $C>2$, we say that $d$ has the $C$-grouping property if any finite non-empty subset $S$ (of ...
- 1,761
2
votes
2
answers
279
views
Combinatorial optimization problem with interdependent constraints on points in $[0,1]$
We are given a set $S$ of $n$ real numbers in $[0,1]$, with $0,1\in S$, and a value $\alpha\in(0,1/2)$. For each ordered triplet $(i,j,k)$ of values contained in $S$ (with $i\le j \le k$), we define ...
- 1,677
5
votes
1
answer
114
views
Packing in uniform domains
Given $N$ points $X:=(x_i)_{i \in \{1,..,N\}}$, we now define a score function $S:X \rightarrow \mathbb{N}$ that is $S(X)= \sum_{i=1}^N S(x_i)$ where the score of $S(x_i)$ is
$$S(x_i) = 2* \vert \{x_j;...
- 536
5
votes
0
answers
313
views
Trade-off between covering number, ball radius and diameter of $d$-dimensional shapes
Given any $d$-dimensional shape $X$ in the Euclidean space, let $\ell(X)$ be the length of the longest line segment connecting two points of $X$. How can we prove the following statement?
There exists ...
- 1,677
3
votes
0
answers
134
views
Two questions on counterexamples to Borsuk's conjecture and ball-packings
In 1933 Karol Borsuk conjectured the following
Can every bounded subset $E$ of $\mathbb{R}^d$ be partitioned into $(d+1)$ sets, each of which has a smaller diameter than $E$?
Whilst new to this ...
- 31
5
votes
0
answers
199
views
Existence of a honeycomb composed by nearly-hyperspherical $d$-dimensional cells having the same shape and size
Let $\mathcal{H}$ the class of all honeycombs composed by $d$-dimensional cells $C$ having all the same shape and size in a $d$-dimensional space $\mathcal{S}$.
Let $s(C)$ and $\ell(C)$ be ...
- 1,677
3
votes
2
answers
365
views
When can any graph $G$ be expressed as a union of $\alpha(G)$ complete graphs?
If for any graph $H$ we define $\alpha(H)$ to be the cardinality of any maximum size indepedent set in $H$. Then under what conditions can any graph $G$ be expressed as a union of $\alpha(G)$ complete ...
- 2,506
4
votes
0
answers
146
views
Tiling squares with oblongs
An oblong is a rectangle whose width and length are consecutive integers: 1x2, 2x3, 3x4, etc. Does N exist such that it is possible to split the first N oblongs into 2 or more non-intersecting sets so ...
- 3,707
6
votes
0
answers
1k
views
How to pack 27 $a\times b\times c$ blocks into a cube of side $a+b+c$ with some kind of symmetry?
Recently I stumbled on the problem quoted here about a geometric proof of the AM-GM inequality $$(a_1+\cdots+a_n)^n\ge n^n a_1\cdots a_n$$ by packing $n^n$ rectangular $ n$-dimensional boxes of sides $...
- 13.4k
10
votes
0
answers
497
views
Which finite sets could be packed into a square?
This question is inspired by an interesting visualization of the finite levels of von Neumann's hierarchy on Adam P. Goucher's blog, Complex Projective 4-Space.
The problem starts with a two-...
2
votes
2
answers
170
views
Counting triples family with double shared elements
We have a set of elements $S=\{1,2,3, . . . , N\}$ and family $F$ of $N$ triples of elements in $S$ ($N$ is a multiple of 3). Each element of $S$ appears in exactly three triples. The elements in each ...
- 2,993
9
votes
1
answer
274
views
Integer sets with forbidden differences
Given a finite set $S$ of positive integers, and a positive integer $n$, let $F(n,S)$ be the largest possible cardinality of a subset of {$1,2,\dots,n$} no two of whose elements differ by a number in $...
- 19.7k
1
vote
0
answers
124
views
The smallest disk containing all cirular arcs
In a comment to my recent question about covering segments by a disk, Gerhard Paseman has suggested a generalisation: replacing the segments of the original $n$-gon by a simple closed (say, convex) ...
- 13.4k
16
votes
5
answers
712
views
The smallest disk containing all sides of an $n$-gon
Start with a regular $n$-gon of side 1 and consider its sides as open segments that can be moved around in the plane, allowing only translations. Two segments may not intersect.
What is the radius ...
- 13.4k
13
votes
0
answers
751
views
$\epsilon$-nets with respect to the cut norm
The cut norm $||A||\_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
- 794
6
votes
0
answers
199
views
A polynomial counting some packings in $\mathbb Z/N\mathbb Z$
Given two integers $n$ and $N$ such that $N>{n+1\choose 2}$, we denote by $\alpha_n(N)$
the number of elements $(x_1,\dots,x_n)$ in $(\mathbb Z/N\mathbb Z)^n$ such that the
$2n$ elements $x_1,x_1+1,...
- 17.9k
0
votes
0
answers
189
views
Packing Icons Onto A screen
You are trying to pack icons onto a screen that is divided into n horizontal rows of uniformly varying size. The rows narrow by a fixed ratio as one goes up the screen from the bottom. Since the icons ...
9
votes
0
answers
193
views
Asymptotics of packing
Define $m(n,k,l)$ as the maximal size of a family $k$-element subsets of $[n]$ having the property that the intersection of every two sets is less than $l$.
As stated on wikipedia, in 1985 Rödl ...
- 393
18
votes
4
answers
1k
views
Pennies on a carpet problem
I recently read the following "open problem" titled "Pennies on a carpet" in "An Introduction To Probability and Random Processes" by Baclawski and Rota (page viii of book, page 10 of following pdf),...
- 4,952
13
votes
1
answer
3k
views
Is there a version of König's theorem for tripartite 3-graphs?
I would like to know if there exists a version of König's theorem for tripartite $3$-graphs.
In other words, let $G = (V,T)$ be a tripartite $3$-graph. That is, $V$ is a set of vertices (with $V$ ...
- 131