\section{Geometric Packing Dimension}
\label{sec:gpd}

We first formally define the geometric packing dimension $\textsf{gpd}(\mathcal{F})$ of a set family $\mathcal{F}$. 

\begin{definition}[Geometric Packing Dimension]
	For a set family $\mathcal{F}$ on a finite universe $U$, we say that the geometric packing dimension $\textsf{gpd}(\mathcal F)$ is the smallest integer $d$ such that there is an embedding $f: U \rightarrow [0,1]^d$ from $U$ to $d$-dimensional axis parallel rectangles such that for every subset $S \subseteq U, S = \{s_1, s_2, \ldots, s_t\}$, $S \in \mathcal F$ if and only if the set of $d$-dimensional rectangles $\{ f(s_1), f(s_2), \ldots, f(s_t)\}$ fit in $\mathbf{1}^d$. If no such $d$ exists, we say that $\textsf{gpd}(\mathcal F)$ is infinite. 
\end{definition}



\subsection{GPD of downward closed set families}

Before proving~\Cref{thm:gpd-infinite}, we prove a couple of lemmas. 
First, we give a sufficient condition for three $d$-dimensional rectangles to fit inside the $d$-dimensional unit cube.

\begin{figure}[b]
    \centering
    
    \begin{subfigure}[b]{0.45\textwidth}
        \includegraphics{images/3d.pdf}
        \caption{$|\set{j_{12},j_{23},j_{31}}|=3$}
    \end{subfigure}
    \begin{subfigure}[b]{0.45\textwidth}
        \includegraphics{images/2d.pdf}
        \caption{$|\set{j_{12},j_{23},j_{31}}|=2$}
    \end{subfigure}
    
    \caption{Interaction between $\mathbf{v_1,v_2,v_3}$ from \Cref{lem:gpd-triple} projected on $j_{12},j_{23},j_{31}$.}
    \label{fig:threeitems}
\end{figure}

\begin{lemma}
\label{lem:gpd-triple}
Consider three $d$-dimensional rectangles $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3 \in [0,1]^d$, and suppose $j_{12} \in [d]$ is such that $v_{1,j_{12}} + v_{2,j_{12}} \leq 1$, and similarly, define $j_{23}$ and $j_{13}$. If $\left|\{ j_{12}, j_{23}, j_{31} \} \right| \geq 2 $, then the three rectangles fit inside the unit $d$-dimensional cube. 
\end{lemma}
\begin{proof}
First, we consider the case when $\left|\{ j_{12}, j_{23}, j_{31} \} \right| = 3$, i.e., the three indices are all distinct. Then, we give the following positions $\mathbf{p}_1, \mathbf{p}_2, \mathbf{p}_3$: we set $p_{i,l}=0 \, \forall i \in [3], l \notin \{ j_{12}, j_{23}, j_{31}\}$, and the rest of the values are set as follows. 
\begin{equation*}
	\begin{aligned}[c]
		p_{1,j_{12}} &= 0 \\ 
		p_{1,j_{23}} &= 0 \\ 
		p_{1,j_{31}} &= v_{3,j_{13}}  		
	\end{aligned}
	\qquad \qquad
	\begin{aligned}[c]
		p_{2,j_{12}} &= v_{1,j_{12}} \\ 
		p_{2,j_{23}} &= 0 \\ 
		p_{2,j_{31}} &=   0		
	\end{aligned}
	\qquad \qquad
\begin{aligned}[c]
	p_{3,j_{12}} &=  0\\ 
	p_{3,j_{23}} &= v_{2,j_{23}} \\ 
	p_{3,j_{31}} &=   0		
\end{aligned}
\end{equation*}
With these parameters, we can observe that the three subsets $[\mathbf{p}_i, \mathbf{p}_i +\mathbf{v}_i), i \in [3]$ are mutually disjoint. 

Next, we consider the case when $\left|\{ j_{12}, j_{23}, j_{31} \} \right| = 2$ (See \cref{fig:threeitems} for an illustration). Without loss of generality, suppose that $j_{12}=j_{31}$. We give the following positions $\mathbf{p}_1, \mathbf{p}_2, \mathbf{p}_3$: we set $p_{i,l}=0 \, \forall i \in [3], l \notin \{ j_{12}, j_{23}\}$, and the rest of the values are set as follows. 
\begin{equation*}
	\begin{aligned}[c]
		p_{1,j_{12}} &= 0 \\ 
		p_{1,j_{23}} &= 0 
	\end{aligned}
	\qquad \qquad
	\begin{aligned}[c]
		p_{2,j_{12}} &= v_{1,j_{12}} \\ 
		p_{2,j_{23}} &= 0 
	\end{aligned}
	\qquad \qquad
	\begin{aligned}[c]
		p_{3,j_{12}} &=   v_{1,j_{12}}\\ 
		p_{3,j_{23}} &= v_{2,j_{23}}  
	\end{aligned}
\end{equation*}
Similar to the above case, we have that the three subsets $[\mathbf{p}_i, \mathbf{p}_i +\mathbf{v}_i), i \in [3]$ are mutually disjoint. 
\end{proof}

Finally, we need the following technical lemma. 
\begin{lemma}
\label{lem:gpd-1}
Suppose $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3 \in [0,1]^d$ be three $d$-dimensional rectangles such that there exists $j \in [d]$ such that $v_{i_1,j} + v_{i_2,j} \leq 1$ for every $i_1, i_2 \in [3], i_1 \neq i_2$, and $v_{i_1,l} + v_{i_2,l} > 1$ for every $i_1, i_2 \in [3], i_1 \neq i_2, l \in [d], l \neq j$. Then, $v_{1,j} + v_{2,j}+v_{3,j} \leq 1$ if and only if the three rectangles fit inside the $d$-dimensional unit cube. 
\end{lemma}

\begin{proof}
	Suppose that $v_{1,j} + v_{2,j}+v_{3,j} \leq 1$. Then, we give the following positions $\mathbf{p}_1, \mathbf{p}_2, \mathbf{p}_3$: we set $p_{i,l}=0 \, \forall i \in [3], l \notin \{ j\}$, and the rest of the values are set as follows. 
	\begin{align*}
		p_{1,j} &= 0 \\ 
		p_{2,j} &= v_{1,j} \\ 
		p_{3,j} &= v_{1,j} + v_{2,j}
	\end{align*}
We have that the three subsets $[\mathbf{p}_i, \mathbf{p}_i +\mathbf{v}_i), i \in [3]$ are mutually disjoint. 

Now, suppose that there exist positions $\mathbf{p}_1, \mathbf{p}_2, \mathbf{p}_3$ such that the three subsets $[\mathbf{p}_i, \mathbf{p}_i +\mathbf{v}_i), i \in [3]$ are mutually disjoint. Consider $i_1, i_2 \in [3], i_1 \neq i_2$. 
As $v_{i_1,l} + v_{i_2,l} > 1$ for every $ l \in [d], l \neq j$, for $[\mathbf{p}_{i_1}, \mathbf{p}_{i_1} +\mathbf{v}_{i_1})$ to be disjoint from $[\mathbf{p}_{i_2}, \mathbf{p}_{i_2} +\mathbf{v}_{i_2})$, we need that $[p_{i_1, j}, p_{i_1,l}+v_{i_1,l}) \cap [p_{i_1, j}, p_{i_1,l}+v_{i_1,l})  = \phi$. As this is true for every distinct pair of indices $i_1, i_2 \in [3]$, we obtain that $[p_{i,j}, p_{i,j}+v_{i,j}), i \in [3]$ are mutually disjoint, which proves that $\sum_{i=1}^3 v_{i,j} \leq 1$. 
\end{proof}

We are now ready to prove that there are downward closed set systems without isolated elements that have infinite packing dimension. 
\gpdinfinite*

\begin{proof}
Fix an integer $n \geq 2$. Our counterexample is the following lines set system $\mathcal{F}$: 
\begin{enumerate}
\item The elements of the family are $U = \mathbb{F}_3^n$. 
\item  The set family consists of all the subsets of $U$ of size at most $2$, and sets of size $3$ of the form $\mathbf{u}, \mathbf{u}+\mathbf{v}, \mathbf{u}+2\mathbf{v}$, where $\mathbf{u}, \mathbf{v} \neq 0$ are elements of $U$, and the addition of vectors is the usual coordinatewise modulo $3$ addition of $\mathbb{F}_3$.   
\end{enumerate}
We claim that $\textsf{gpd}(\mathcal F)$ is infinite. 

Suppose for contradiction that there is a mapping $f: U \rightarrow [0,1]^d$ from $U$ to $d$-dimensional rectangles that is a valid geometric packing dimension embedding. Consider an arbitrary element $a \in U$, and arbitrary elements $b_1, b_2 \in U \setminus \{a\}$. Let $i_1 \in [d] $ be such that $f(a)_{i_1} + f(b_1)_{i_1} \leq 1 $, and similarly define $i_2$. Note that such $i_1, i_2$ exist, since $\{a,b_1\}, \{a,b_2\} \in \mathcal F$, and using~\Cref{lem:gpd-pair}.

First, we consider the case when $i_1 \neq i_2$. 
As there is a coordinate $j \in [d]$ where $f(b_1)_j + f(b_2)_j \leq 1$, we can infer that $\{a, b_1, b_2\} \in \mathcal{F}$ using~\Cref{lem:gpd-triple}. Now, consider an arbitrary element $b_3 \in U \setminus \{a, b_1, b_2 \}$. Note that there exists $i_3 \in [d]$ such that $f(a)_{i_3} + f(b_3)_{i_3} \leq 1$. However, there exists $\ell \in \{1,2\}$ such that $i_\ell \neq i_3$, implying that $a, b_3, b_\ell$ are a line, contradicting the fact that $a, b_1, b_2$ form a line in $\mathbb{F}_3^n$. 

Now, suppose that for every choice of $a, b_1, b_2 \in U$, no such distinct $i_1, i_2$ exist. Recall that for every pair of elements $a, b \in U$, there exists $l \in [d]$ such that  $f(a)_l + f(b)_l \leq 1$. 
The absence of such distinct $i_1, i_2$ implies that there is a single coordinate $j \in [d]$ such that for every pair of elements $a, b \in U$,  $f(a)_j + f(b)_j \leq 1$, and $f(a)_l + f(b)_l > 1$ for every $l \neq j$. However, using~\Cref{lem:gpd-1}, this implies that $f' : U \rightarrow [0,1]$ defined as $f'(u) = f(u)_j$ is a valid $1$-dimensional geometric embedding of $\mathcal{F}$. 

Finally, we prove that $\textsf{gpd} (\mathcal F)  \neq 1$, finishing the proof. 
Pick 2 disjoint sets $S_1,S_2\in \mathcal F$ of size 3. Note that such sets are guaranteed to exist, when $n \geq 2$. 
Observe that for any set $S\in \mathcal F$ of size 3 there exists $u\in S$ with $f'(u)\leq 1/3$.
Let $u_1\in S_1$ and $u_2\in S_2$ be such that $f'(u_1)\leq 1/3$ and $f'(u_2)\leq 1/3$.
Pick $d\in \mathbb F^n$ such that $d\ne 0,u_2-u_1,u_1-u_2$.
Now, consider the set $S_3=\set{u_1+d,u_2+d,2u_2-u_1+d}$.
Again, let $u_3\in S_3$ be such that $f'(u_3)\leq 1/3$.
Since $d\ne 0,u_2-u_1,u_1-u_2$, $u_3\ne u_1,u_2,2u_2-u_1$ hence $\set{u_1,u_2,u_3}\not\in \mathcal F$.
But, $f'(u_1)+f'(u_2)+f'(u_3)\leq 1$, a contradiction.
\end{proof}

\subsection{GPD of bounded set systems}

In this subsection, we prove~\Cref{thm:gpd-simple}. First, we define induced matching of a downward closed set system $\mathcal F$. 

\begin{definition}[Induced matching]
	Let $\mathcal{F} \subseteq 2^U$ be a downward closed set system. We say it has an induced matching of size $k$ if there exist $k$ mutually disjoint sets $U_1, U_2, \ldots, U_k \in \mathcal F$, each with cardinality at least two, such that for every non-empty set $S \in \mathcal F$, $S \cap U_i \neq \phi$ for at most one $i \in [k]$. That is, $\mathcal F$ restricted to $\bigcup_{i \in [k]}U_i$ is a disjoint union of complete set systems. 
\end{definition}

We now show that the existence of a large induced matching implies that the geometric packing dimension of the set system is large as well. 

\begin{lemma}
\label{lem:matching}
	Suppose that $\mathcal F \subseteq 2^U$ has an induced matching of size $k$. Then, either $\textsf{gpd}(\mathcal F)$ is infinite, or is at least $k$. 
\end{lemma}	

\begin{proof}
	As $\mathcal F$ has an induced matching of size $k$, there exist $k$ mutually disjoint sets $U_1, U_2, \ldots, U_k \in \mathcal F$ such that for every $S$ with $S \cap U_i \neq \phi, S \cap U_j \neq \phi$ for $i,j \in [k], i \neq [k]$, then $S \notin \mathcal F$. Suppose for contradiction that $\textsf{gpd}(\mathcal F) < k$, i.e., there exists a function $f : U \rightarrow [0,1]^d$ with $d < k$ that is a valid geometric packing. First, we consider $2k$ arbitrary distinct elements $a_1, a_2, \ldots, a_k , b_1, b_2, \ldots, b_k \in U$ such that $a_i, b_i \in U_i $ for every $i \in [k]$. As $\{ a_i, b_i \} \in \mathcal F$, using~\Cref{lem:gpd-pair}, we can conclude that there exists $s_i \in [d]$ such that $f(a_i)_{s_i}+f(b_i)_{s_i} \leq 1$. 
	
	We claim that $s_i \neq s_j$ for every $i,j \in [k], i \neq j$. Suppose for contradiction that there exists $i, j \in [k], i \neq j$ such that $s_i = s_j$. Note that we have $f(a_i)_{s_i}+f(b_i)_{s_i} \leq 1$, and $f(a_j)_{s_i}+f(b_j)_{s_i} \leq 1$. However, by the induced matching property that $\{ a_i, a_j\} \notin \mathcal F$, using~\Cref{lem:gpd-pair}, we get that $f(a_i)_{s_i}+f(a_j)_{s_i} >1 $. Similarly, we obtain that $f(a_i)_{s_i}+f(b_j)_{s_i} >1$, $f(b_i)_{s_i}+f(a_j)_{s_i} >1$ and $f(b_i)_{s_i}+f(b_j)_{s_i} >1  $, a contradiction. 
\end{proof}

We are now ready to prove~\Cref{thm:gpd-simple}. 
\bounded*
\begin{proof}


Consider the graph $G=(V(G),E(G))$ defined as follows. 
\begin{enumerate}
    \item The vertex set $V(G)$ is the family of sets in $\mathcal F$ that have cardinality at least two.
    \item There is an edge between two (distinct) sets $S_1,S_2\in \mathcal F$ if there exists a set $S\in \mathcal F$ with $S \cap S_1 \neq \phi, S \cap S_2 \neq \phi$ ($S$ could be equal to either $S_1$ or $S_2$ as well).
\end{enumerate}
 As there are no isolated elements in $\mathcal{F}$, there are at least $\frac{|U|}{k}$ vertices in $G$.
Furthermore, as each set in $\mathcal F$ has cardinality at most $k$ and each element appears in at most $B$ elements, the maximum degree of the graph $G$ is at most $(kB)^2$. 
Therefore, there must be an independent set $\mathcal M$ of size at least $\frac{| V(G)|}{(kB)^2+1}$ in $G$. By definition, the independent sets in $G$ are exactly the induced matchings in $\mathcal F$. Thus, there is an induced matching of size at least $\frac{|V(G)|}{(kB)^2+1}$ in $\mathcal F$.
Hence, by~\Cref{lem:matching} we get that $\textsf{gpd}(\mathcal F)\geq \frac{|U|}{k(k^2B^2+1)}$.
\end{proof}

\section{Introduction}
\label{sec:intro}

In the Geometric Bin Packing (GBP) problem, the input is a set of $d$-dimensional rectangles, and the objective is to pack them\footnote{In this work, we study the case where rotations are not allowed and GBP will refer to this case unless stated otherwise.} into a minimum number of unit $d$-dimensional cubes.
The problem is widely applicable in practice and has received a lot of attention in the approximation algorithms community.
It is one of the two most extensively studied generalizations of Bin Packing (the other being Vector Bin Packing), which corresponds to the case when $d=1$.
Bin Packing is a classical NP-Hard problem and has an asymptotic\footnote{The asymptotic approximation ratio of an algorithm corresponds to the case when the optimal value is large enough.} PTAS~\cite{VegaL81}. 
Already for $d=2$, i.e., the problem of packing (2-dimensional) rectangles in square boxes, a PTAS can not be obtained unless $\P=\text{NP}$.
 The best known algorithm for this 2-dimensional setting is by Bansal and Khan~\cite{BansalK14} with an approximation ratio of 1.406, and the best hardness result is $1+\frac{1}{2196}$ due to Chlebik and Chleb{\'i}kov{\'a}~\cite{CC09}. 

Typically, multidimensional packing problems have two variants: when the dimension $d$ is part of the input size, or when $d$ is a fixed constant independent of the input.
The key difference is that when $d$ is fixed, the algorithms are allowed to run in time $n^{f(d)}$ for an arbitrary function $f$.
On the algorithmic side, even with fixed $d$, the best known algorithm has an approximation ratio\footnote{$T_\infty$ denotes the Harmonic constant.
It is defined as $T_\infty =\sum_{i=1}^\infty \frac{1}{t_i-1}$ with $t_1=2$ and $t_{i+1}=t_i(t_i-1)+1$.
} $T_{\infty}^{d-1}$
~\cite{Caprara02}, whereas the hardness is still the non-existence of PTAS from the $2$-dimensional case.
For the GBP, for both the cases, previously, no hardness of approximation growing with $d$ is known, and this has been one of the ten open problems in a recent survey on multidimensional packing problems~\cite{ChristensenKPT17}. Note that obtaining hardness for the case when $d$ is part of the input is an easier than (and a necessary step towards) showing hardness for the fixed $d$ case. 

In this work, we obtain a strong inapproximability result for GBP when $d$ is part of the input. 
\begin{restatable}{thm}{main}
\label{thm:main_informal}
Geometric Bin Packing is hard to approximate within $d^{1-\epsilon}$ factor for instances with $d$-dimensional items, for every $\epsilon>0$ when $d$ is part of the input unless NP=ZPP. 
\end{restatable}

Our proof is a direct reduction from graph coloring, similar to the hardness of $d$-dimensional Vector Bin Packing due to Chekuri and Khanna~\cite{CK04}. 

When $d$ is a fixed constant, in a recent work~\cite{Sandeep21}, $\Omega(\log d)$ hardness for Vector Bin Packing has been obtained. This result is obtained by a reduction from the set cover problem via \textit{packing dimension} of set systems, which is the minimum dimension in which the set cover of a set system can be embedded as a Vector Bin Packing problem. 
In the set cover problem, the input is a set family $\mathcal{F}$ on a universe $U$, and the objective is to find the minimum number of sets from $\mathcal{F}$ whose union is $U$. The Vector Bin Packing problem can be formulated as a set cover problem, by letting ``configuration'' of vectors to be a set of vectors that fit in a unit cube, and the objective is to find the minimum number of configurations whose union covers all the vectors. The inapproximability result for the problem is obtained by reversing this reduction, i.e., by embedding the set cover problem as a Vector Bin Packing problem such that the configurations in the Vector Bin Packing instance are exactly the sets in the set cover problem. The minimum dimension of the Vector Bin Packing instance that we can output this way starting with a set cover instance of a set family $\mathcal F$ is precisely the packing dimension of the set family $\mathcal F$. 

In this work, we study the analogous notion for the Geometric Bin Packing problem. In particular, we define the \emph{Geometric Packing Dimension} $\textsf{gpd}(\mathcal F)$ of a set system $\mathcal F \subseteq 2^U$ on a universe $U$ to be the smallest integer $d$ such that there is an embedding of the elements of $\mathcal F$ to $d$-dimensional rectangles such that a set $S $ of elements is in $\mathcal F$ if and only if the corresponding rectangles fit in a $d$-dimensional unit cube. If no such an embedding exists, then we say that $\mathcal F$ has no finite $\textsf{gpd}$. 
By obtaining such an embedding in polynomial time, we can get a direct reduction from the set cover problem on $\mathcal F$ to a GBP instance with dimension $\textsf{gpd}(\mathcal F)$. 
The goal is to find set families that have small packing dimension where set cover is hard, thus implying hardness of approximation for the GBP problem. In this work, while we fall short of this objective, we formally introduce and study $\textsf{gpd}$ of set families, and prove a couple of properties of it.

For a set family $\mathcal F$ on a universe $U$, $\textsf{gpd}(\mathcal F)$ being finite is equivalent to the fact that there exists a Geometric Bin Packing instance where the rectangles correspond to the elements of $U$, and the configurations are exactly the sets in $\mathcal F$. It is an interesting question, then, to characterize which set families $\mathcal F$ have finite $\textsf{gpd}(\mathcal F)$. 
Similar to the packing dimension~\cite{Sandeep21}, two conditions are necessary for a set system $\mathcal F$ to have a finite $\textsf{gpd}$: first, the set system should be downward closed, i.e., for every $S \in \mathcal F$ and $T \subseteq S$, $T \in \mathcal F$ as well. Second, the set system should not have any isolated elements, i.e., for every $i \in U$, there is $S \in \mathcal F$ such that $i \in S$. In~\cite{Sandeep21}, the author proves that these two conditions are sufficient for a set system to have a finite packing dimension. However, we show that this does not hold for the geometric packing dimension. 

\begin{restatable}{thm}{gpdinfinite}
\label{thm:gpd-infinite}
	There is a set system $\mathcal F$ that is downward closed and has no isolated elements such that $\textsf{gpd}(\mathcal F)$ is not finite. 
\end{restatable}

Our construction is obtained using a set system defined via lines in $\mathbb{F}_3^n$. The key property that we use is that while the set system is dense enough, every pair of elements appear in exactly one set. 

As mentioned earlier, the main motivation behind defining the Geometric Packing Dimension is to find set systems $\mathcal F$ with small $\textsf{gpd}(\mathcal F)$, yet set cover is hard on them. 
We are interested in set families that are structured, to let $\textsf{gpd}$ be a fixed constant independent of the input, yet set cover is hard to approximate on them. One such set families are the $(k,B)$-bounded set systems, where each set has size at most $k$, and each element appear in at most $B$ sets, where $k,B$ are fixed constants. In fact, for the $d$-dimensional Vector Bin Packing, these set systems are used to show the inapproximability result in~\cite{Sandeep21}. However, we show that bounded set systems have very large $\textsf{gpd}$.
This rules out any direct reduction from set cover instances that are bounded, to the GBP problem.


\begin{restatable}{thm}{bounded}
\label{thm:gpd-simple}
	Let $\mathcal F \subseteq 2^U$ be a set family that is $(k,B)$-bounded with $k,B$ constants and has no isolated elements. Then, either $\textsf{gpd}(\mathcal F)$ is not finite, or it is at least $\Omega(|U|)$. 
\end{restatable}

Our proof is obtained by studying the induced matching of set families. The bounded set systems have a large induced matching, and that implies that $\textsf{gpd}$ has to be large as well. 


\subsection{Related Work.}
Bin Packing is a classical NP-complete problem.
de la Vega and Lueker~\cite{VegaL81} used the linear grouping technique to obtain a PTAS.
The best algorithm known has an additive error of $O(\log \texttt{OPT})$ due to Hoberg and Rothvo{\ss}~\cite{HR17}.
It is still an open problem to determine if an additive error of 1 is possible or not.

For Geometric Bin Packing Problem when $d=2$, some of the recent work include the $T_\infty+\epsilon$ approximation~\cite{Caprara02}.
Bansal, Caprara, and Sviridenko~\cite{BCS09} improved it further using their Round and Approx framework to obtain a $1+\ln(T_\infty)\approx 1.52$ approximation.
Finally, Bansal and Khan~\cite{BansalK14} gave the $1+\ln(1.5)\approx 1.406$ approximation by showing the Round and Approx framework applies to the $1.5+\epsilon$ approximation due to Jansen and Pr{\"a}del~\cite{JP16}.
When $d>2$, the $T_\infty^{d-1}$ by Caprara~\cite{Caprara02} stands as the current best.
On the hardness side, Bansal et~al.~\cite{BCKS06} showed that there is no PTAS even for $d=2$, unless $\P=\text{NP}$.
This was later improved by Chlebik and Chleb{\'i}kov{\'a}~\cite{CC09} to $1+\frac{1}{2196}$ by modifying the construction in \cite{BCKS06}. 
As stated earlier the $1+\frac{1}{2196}$ bound is the best hardness result known even for higher dimensions.

Vector Bin Packing is another well-studied generalization of the Bin Packing Problem.
When $d$ is part of the input, there is a $(d+\epsilon)$-approximation due to de la Vega and Luekar~\cite{VegaL81}.
On the hardness side, a simple modification\footnote{This modification is due to Jan Vondr{\'a}k which appeared in \cite{BEK06}} to the reduction by Chekuri and Khanna~\cite{CK04} gives a $d^{1-\epsilon}$ hardness.
When $d$ is not part of the input the barrier of was broken by Chekuri and Khanna~\cite{CK04} by giving $\ln d + 2 + \gamma$ appoximation.\footnote{$\gamma$ denotes the Euler-Mascheroni constant. It is defined as $\gamma=\lim_{n\to \infty} \sum_{k=1}^{n}\frac{1}{k}-\ln n$.}
This was improved to $\ln d + 1$, and then to $\ln (d+1) + 0.807$ by Bansal, Caprara and Sviridenko~\cite{BCS09} and Bansal, Eli\'a\v{s} and Khan~\cite{BEK06}, respectively.
Recently, Sandeep~\cite{Sandeep21} improved the lower bound to $\Omega(\ln d)$ from $1+\frac{1}{599}$ due to Ray~\cite{Ray21} and Woeginger~\cite{Woeginger97}.

For a more comprehensive review of the recent works on approximation algorithms for Bin Packing and related problems, we refer the reader to the survey by Christensen et~al.~\cite{ChristensenKPT17}.

\subsection{Preliminaries.} 
\textbf{Notations.} We use $[n]$ to denote $\{1,2,\ldots,n\}$. A set family or set system $\mathcal{F} \subseteq 2^U$ is a family of subsets of $U$. We use boldface letters to denote $d$-dimensional vectors or rectangles. For a $d$-dimensional rectangle $\mathbf u$, we use $u_i$ to denote the $i$th coordinate, and for a $d$-dimensional rectangle $\mathbf v_i$, we use $v_{i,j}$ to denote the $j$th coordinate. 
$\mathbb F_k$ denotes a field of characteristic $k$. 

We call an element $e$ of a set family $\mathcal{F}$ as \emph{isolated} if there is no set of cardinality at least two containing $e$.
\begin{definition}
    For a given set system $\mathcal F\subseteq 2^U$ we say an element $e\in U$ is isolated if $\set{e}\subsetneq S$ implies $S\not \in \mathcal F$.
\end{definition}

\medskip \noindent \textbf{Packing $d$-dimensional rectangles. }
As mentioned earlier, in this work, we only consider the setting where we do not allow rotations of the rectangles. Thus, a set of $d$-dimensional rectangles $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k \in (0,1]^d$ where $\mathbf{v}_i = \{ v_{i,1}, v_{i,2}, \ldots, v_{i,d}\}, i \in [k]$ fit in the $d$-dimensional unit cube $\mathbf{1}^d$ if and only if there exist positioning of these rectangles such that they all fit in $\mathbf{1}^d$, and they don't intersect with each other, i.e., there exist $\mathbf{p}_1, \mathbf{p}_2, \ldots, \mathbf{p}_k \in [0,1]^d$ where $\mathbf{p}_i = \{ p_{i,1}, p_{i,2}, \ldots, p_{i,d}\}, i \in [k]$ such that the following two conditions hold: 
\begin{enumerate}
	\item First, the rectangles fit inside the unit cube, i.e., for every $i \in [k], l \in [d]$, $ p_{i,l} + v_{i,l} \leq 1$. 
	\item The rectangles don't intersect with each other, i.e., the $k$ subsets of $[0,1]^d$ for $i \in [k]$ 
	\[
	[\mathbf{p}_i, \mathbf{p}_i + \mathbf{v}_i) := [p_{i,1}, p_{i,1}+v_{i,1}) \times 	[p_{i,2}, p_{i,2}+v_{i,2}) \times \dots \times 	[p_{i,d}, p_{i,d}+v_{i,d})
	\]
	are mutually disjoint. 
\end{enumerate} 
\section{Reduction from Graph Coloring}

Do we have the following? 
\begin{theorem}
Given a graph $G=([n],E)$, there is a $d$-dimensional embedding with $d \leq \binom{n}{2},$ $v_1, v_2, \ldots, v_n \in [0,1]^d$ such that for every set $S \subseteq [n]$, $S$  is a clique iff $\{ v_i: i \in S \}$ fit in $\textbf{1}^d$ (with no rotations.)
\end{theorem}

\begin{proof}
We define the vectors $v_i \in [0,1]^{|E|}$ as follows: 
\[
(v_i)_j = \begin{cases}
1, \text{ if }i\notin e_j \\ 
0.5, \text{ otherwise.}
\end{cases}
\]

First, suppose that indices $i,j \in [n]$ are such that $(i,j)$ are not adjacent in $G$. We claim that $v_i, v_j$ do not fit in $\textbf{1}^d$. Without loss of generality, we can assume that there are integers $p,q,r$ such that $v_i = (1,\ldots, 1, 0.5, \ldots, 0.5, 1, \ldots, 1)$ where there are $p$ $1$s followed by $q$ $0.5$s and $p$ $1$s. Similarly, $v_j = (1,\ldots, 1, 1, \ldots, 1, 0.5, \ldots, 0.5)$. Suppose for contradiction that $v_i$ and $v_j$ fit in $\textbf{1}^d$ i.e., there exists $\textbf{u}_i \in [0,1]^d$ and $\textbf{u}_j \in [0,1]^d$ such that $[u_i, u_i + v_i ) \cap [u_j, u_j+v_j) = \phi$. However, note that $(0.5, \ldots, 0.5) $ (or a slight modification if needed) is in the intersection. 

Second, we define the vectors $u_1, u_2, \ldots, u_n \in [0,1]^d$ as follows: 
\[
(u_i)_j = \begin{cases}
0, \text { if } i \notin e_j \\
0,  \text { if } i \in e_j, e_j = (i, i'), i<i' \\
0.5, \text{ otherwise.}
\end{cases}
\]
We claim that if a subset $S = \{ i_1, i_2, \ldots, i_s\}$ is a clique in $G$, then the cuboids $[u_{i_1}, u_{i_1}+v_{i_1}), \ldots, [u_{i_s}, u_{i_s}+v_{i_s})$ are mutually disjoint. 
\end{proof}

Thus, the minimum number of cubes needed to cover the vectors is equal to the chromatic number of $\overline{G}$.


\section{Geometric Packing Dimension}

Similar to the vector packing dimension, we can define the geometric packing dimension $\textsf{gpd}(\mathcal{F})$ of a set family $\mathcal{F}$. 

\begin{theorem}
There exist set families $\mathcal{F}$ that are downward closed such that $\textsf{gpd}(\mathcal{F})$ is not finite. 
\end{theorem}

\begin{proof}
Our counterexample is the following ``lines'' set system $\mathcal{F}$: fix an integer $n \geq 2$. The elements of the family are $U = \mathbb{F}_3^n$, or we can think of $\{0,1,2\}^n$. The set family consists of all the subsets of $U$ of size at most $2$, and sets of size $3$ of the form $\textbf{u}, \textbf{u}+\textbf{v}, \textbf{u}+2\textbf{v}$, where $\textbf{u}, \textbf{v} \neq 0$ are elements of $U$, and the addition is modulo $3$. Note the following: for every pair of elements in the set system, there is a unique set of size three that contains them. 

We now claim that $\textsf{gpd}(\mathcal{F})$ is not finite. 

First, we are going to use the following observation regarding packing three vectors $v_1, v_2, v_3 \in [0,1]^d$ in a $d$-dimensional bin: suppose that $i_{12} \in [d]$ is such that $(v_1)_{i_12} + (v_2)_{i_12} \leq 1$, and similarly, define $i_{23}$ and $i_{13}$. (If they don't exist, we cannot pack the three vectors anyway. ) Now, if $\left| \{ i_{12}, i_{23}, i_{13} \} \right| = 2 $, then the three vectors can be packed in $1^d$. 

Now, suppose for contradiction that there is a $d$-dimensional embedding of $U$. Consider an arbitrary element $u \in U$, and arbitrary elements $v_1, v_2 \in U \setminus \{u\}$. Let $i_1 \in [d] $ be such that $u_{i_1} + (v_1)_{i_1} \leq 1 $, and similarly define $i_2$. Choose $u, v_1, v_2$ is such that there exist such $i_1$ and $i_2$ that are distinct. (Here, we are assuming that there is no $1$-dimensional embedding for $\mathcal{F}$ - I think this is true) Now, as $i_1 \neq i_2$, and as there is a coordinate $j \in [d]$ where $(v_1)_j + (v_2)_j \leq 1$, $(u, v_1, v_2)$ are a set in $\mathcal{F}$. However, consider an arbitrary element $v_3 \in U \setminus \{u, v_1, v_2 \}$. Note that there exists $i_3 \in [d]$ such that $u_{i_3} + (v_3)_{i_3} \leq 1$. However, there exists $\ell \in \{1,2\}$ such that $i_\ell \neq i_3$, implying that $u, v_3, v_\ell$ are a line, a contradiction. 
\end{proof}
\begin{lemma}
For the line set system $\mathcal F$ on $\mathbb F^n$ with large enough $n$, we have $\textsf{gpd}(\mathcal F)>1$
\end{lemma}
\begin{proof}
Suppose there is an embedding $f:\mathbb F^n\to (0,1]$ which acts as a certificate for $\textsf{gpd}(\mathcal F)=1$.
Pick 2 disjoint sets $S_1,S_2\in \mathcal F$ of size 3.
Observe that for any set $S\in \mathcal F$ of size 3 there exists $u\in S$ with $f(u)\leq 1/3$.
Let $u_1\in S_1$ and $u_2\in S_2$ be such that $f(u_1)\leq 1/3$ and $f(u_2)\leq 1/3$.
Pick $d\in \mathbb F^n$ such that $d\ne 0,u_2-u_1,u_1-u_2$.
Now, consider the set $S_3=\set{u_1+d,u_2+d,2u_2-u_1+d}$.
Again, let $u_3\in S_3$ be such that $f(u_3)\leq 1/3$.
By construction, $u_3\ne u_1,u_2,2u_2-u_1$ hence $\set{u_1,u_2,u_3}\not\in \mathcal F$.
But, $f(u_1)+f(u_2)+f(u_3)\leq 1$, a contradiction.
($n$ needs to be large enough for 2 disjoint sets to exist)
\end{proof}

\section{Reduction from Graph Coloring}
\label{sec:proof}

In this section, we prove the inapproximability result for Geometric Bin Packing.
Our reduction is reminiscent of the reduction from graph coloring to vector bin packing by Chekuri and Khanna \cite{CK04} which showed there is no $d^{1/2-\epsilon}$ approximation for Vector Bin Packing unless $\text{NP}=\text{ZPP}$.


\medskip \noindent \textbf{Reduction.}
Our reduction outputs a $d$-dimensional geometric bin packing instance from a given graph $G=([n],E)$ wherein each $d$-dimensional rectangle corresponds to a vertex. 
The key idea is that the $d$-dimensional rectangles corresponding to a subset of vertices fit in the unit $d$-dimensional cube if and only if the subset of vertices is a clique in the graph. 
Fix a constant $\alpha \in (0,0.1)$.
We have $d=n$, and the $d$-dimensional rectangles $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$ are defined as follows. 
\[
v_{i,j} := \begin{cases}
\alpha,\text{ if }i=j \\
0.5+\alpha,\text{ if }(i,j) \in E\\
1,\text{ if }i \neq j, (i,j) \notin E \end{cases}
\]


Before analyzing the reduction, we need the following lemma regarding packing two $d$-dimensional rectangles in the unit $d$-dimensional cube $\mathbf{1}^d$. 
\begin{lemma} 
\label{lem:gpd-pair}
The $d$-dimensional rectangles $\mathbf u, \mathbf v \in [0,1]^d$ fit in the unit cube $\mathbf{1}^d$ if and only if there exists $j \in [d]$ such that $u_j + v_j \leq 1$. 
\end{lemma}
\begin{proof}
First, suppose that there exists $j \in [d]$ such that $u_j + v_j \leq 1$. We consider the following positions of the rectangles: $\mathbf{p}, \mathbf{q} \in [0,1]^d$: $p_l = 0 \, \forall l \in [d]$, and 
\[
q_l = \begin{cases}
0, \text{ if }l \neq j.\\
u_j, \text { if }l=j.
\end{cases}
\]
Note that $[\mathbf{p}, \mathbf{p}+\mathbf{u}) \cap [\mathbf{q}, \mathbf{q}+\mathbf{v}) =\phi$. 

Now, suppose that the two $d$-dimensional rectangles fit in a $d$-dimensional cube, i.e., there exist $\mathbf{p}, \mathbf{q}$ such that $[\mathbf{p}, \mathbf{p}+\mathbf{u}) \cap [\mathbf{q}, \mathbf{q}+\mathbf{v}) =\phi$. Note that $u_l + v_l > 1$ implies that $[p_l, p_l + u_l) \cap [q_l, q_l + v_l) \neq \phi$. Thus, if $u_l + v_l > 1$ for every $l \in [d]$, we get that $[\mathbf{p}, \mathbf{p}+\mathbf{u}) \cap [\mathbf{q}, \mathbf{q}+\mathbf{v}) \neq \phi$, a contradiction. Hence, there exists $l \in [d]$ such that $u_l + v_l \leq 1$. 
\end{proof}

\begin{figure}
    \centering
    \begin{subfigure}[b]{0.3\textwidth}
        \includegraphics{images/graph.pdf}
        \caption{Input graph}
    \end{subfigure}
    \begin{subfigure}[b]{0.3\textwidth}
        \includegraphics{images/bin1.pdf}
        \caption{The clique $\set{1,2}$}
    \end{subfigure}
    \begin{subfigure}[b]{0.3\textwidth}
        \includegraphics{images/bin2.pdf}
        \caption{The clique $\set{3}$}
    \end{subfigure}
    
    \caption{Embedding a graph according to \Cref{lem:coloringtogdp} and packing the cliques $\set{1,2},\set{3}$.}
    \label{fig:embedding}
\end{figure}

We are now ready to analyze the reduction. 
\iffalse 
Each item in this instance corresponds to a vertex and each component is either 
The completeness is extremely simple.
For the soundness we use the observation\footnote{Notation: for $\mathbf a,\mathbf b\in \mathbb R^d$, $(\mathbf a,\mathbf b)=(a_1,b_1) \times (a_2,b_2) \dots \times (a_d,b_d)$.} that if $(\mathbf a,\mathbf b)\cap (\mathbf c,\mathbf d)=\phi$ then there exists $i$ such that $(a_i,b_i)\cap (c_i,d_i)=\phi$.
\fi 


\begin{lemma}
\label{lem:coloringtogdp}
Given a graph $G=([n],E)$, $\alpha\in (0,1)$, and the $d$-dimensional rectangles $\mathbf v_1, \mathbf v_2, \ldots, \mathbf v_n \in [0,1]^d$ defined as above with $d=n$, for every subset of vertices $S \subseteq [n]$, $S$  is a clique in $G$ if and only if $\{ \mathbf v_i: i \in S \}$ fit in $\mathbf{1}^d$. 
\end{lemma}

\begin{proof}
First, suppose that indices $i,j \in [n]$ are such that $(i,j)$ are not adjacent in $G$. By the definition of the vectors, for every $l \in [d]$, we have $v_{i,l}+v_{j,l}>1$. Thus, by~\Cref{lem:gpd-pair},  $\mathbf v_i, \mathbf v_j$ do not fit in $\mathbf{1}^d$. Thus, if a subset of vertices $S$ is not a clique, then the corresponding $d$-dimensional rectangles do not fit in the $d$-dimensional unit cube. 

Now, we define the positions $\mathbf p_1, \mathbf p_2, \ldots, \mathbf p_n \in [0,1]^d$ as follows: 
\[
p_{i,j} = \begin{cases}
0, \text { if } i \neq j \\
0.6,  \text { if } i = j.
\end{cases}
\]
Suppose that $(i,j) \in E$. Then, we have $[p_{i,i}, p_{i,i}+v_{i,i}) \cap [p_{j,i}, p_{j,i}+v_{j,i}) = \phi$. Thus, $[\mathbf p_i, \mathbf p_i + \mathbf v_i) \cap [\mathbf p_j, \mathbf p_j + \mathbf v_j) = \phi$. Hence, 
if a subset $S = \{ i_1, i_2, \ldots, i_s\}$ is a clique in $G$, then the cuboids $[\mathbf p_{i_1}, \mathbf p_{i_1}+\mathbf v_{i_1}), \ldots, [\mathbf p_{i_s}, \mathbf p_{i_s}+\mathbf v_{i_s})$ are all mutually disjoint. In other words, the set of rectangles $\mathbf v_{i_1}, \mathbf v_{i_2}, \ldots, \mathbf v_{i_s}$ fit in the $d$-dimensional unit cube. 
\end{proof}

Thus, the minimum number of cubes needed to cover all the rectangles is equal to the chromatic number of $\overline{G}$.
Now, using the $n^{1-\epsilon}$ hardness for graph coloring by Feige and Kilian \cite{FK98} we have the following result,
\main*
Finally, as a consequence of the reduction in \Cref{lem:coloringtogdp} we can also conclude there is no $d^\epsilon$-approximation, for some $\epsilon>0$, for GBP under the weaker assumption of $\text{NP} \ne \P$.
This is because Lund and Yannakakis \cite{LY94} showed there is no polynomial-time approximation algorithm with an approximation ratio better than $n^\epsilon$, for some $\epsilon>0$, for graph coloring, unless $\P = \text{NP}$. 
