Parameterized Complexity of Fair Coloring Problem

Hossein Shokouhi; Ramin Javadi

REVIEW 2 major objections 5 minor 25 references

Parameterized Complexity of Fair Coloring Problem

T0 review · 2 major / 5 minor · reviewed 2026-07-30 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Fair coloring is already W[1]-hard by the number of groups on forests and modular-width-two graphs, even for two colors, yet becomes FPT once neighborhood diversity is a parameter.

desk verdict Solid hardness map and a clean k=2 FPT, but the general (nd,p) FPT has a real gap in the matrix-decomposition step. read the letter →

arxiv 2607.27004 v1 pith:FBEPOSXX submitted 2026-07-29 cs.CC

Ramin Javadi , Hossein Shokouhi This is my paper · ORCID

classification cs.CC MSC 68Q2705C1568Q25

keywords faircoloringparameterizedcomplexityneighborhooddiversitymodular-widthvectorbinpackingW[1]-hardnessFPTalgorithmsequitable

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks when a proper graph coloring can also keep given demographic groups nearly balanced inside every color class (the difference between any two groups at most a fixed threshold). It proves that measuring complexity only by the number of groups leaves the problem hard: already for two colors the question is W[1]-hard on forests whose components have depth two and on graphs of modular-width two. Hardness is obtained by first showing that unary multi-dimensional bin packing is W[1]-hard by dimension, then reducing that problem to fair two-coloring. On the positive side, when the input has small neighborhood diversity the two-color case is fixed-parameter tractable, and for any number of colors the combination of neighborhood diversity and number of groups is enough for an FPT algorithm via integer programming. A reader who cares about fair districting, load balancing or demographic balance on networks now knows exactly which structural parameters rescue the problem and which do not.

What carries the argument

A parameterized reduction from Grid Tiling through Unary Multi-dimensional Bin Packing that builds a simple forest (or modular-width-two graph) whose fair two-colorings encode exact capacity solutions; on the algorithmic side an integer linear program whose variables count color classes by valid type-sets of neighborhood-diversity modules, solved by Lenstra’s theorem after a balanced matrix decomposition.

What would settle it

Produce a concrete matrix that satisfies the aggregate fairness constraint of the ILP yet every balanced decomposition into the prescribed number of summands has at least one summand whose group counts differ by more than the allowed threshold; or prove no such matrix exists.

Watch

Extended reading notes

Core claim

Fair Coloring is W[1]-hard parameterized by the number of groups p alone, already when only two colors are allowed, on forests of depth-two components and on modular-width-two graphs. The same problem is FPT parameterized by neighborhood diversity when the number of colors is two, and FPT parameterized by the pair (neighborhood diversity, p) for arbitrary numbers of colors. As a by-product, unary vector bin packing is W[1]-hard with respect to dimension.

Load-bearing premise

The FPT proof for general numbers of colors assumes that a balanced splitting of an already-fair aggregate assignment automatically produces individually fair color classes, which the cited balancing lemma does not guarantee.

Editorial extensions

If this is right

Unary multi-dimensional bin packing admits no FPT algorithm parameterized solely by dimension (unless FPT equals W[1]).
Fair two-coloring on forests is already intractable when only the number of demographic groups is treated as the parameter.
Neighborhood diversity alone restores fixed-parameter tractability for the two-color case without needing the number of groups.
For arbitrary numbers of colors the pair (neighborhood diversity, number of groups) yields an FPT algorithm via bounded-variable integer programming.
An XP algorithm exists for two colors parameterized only by the number of groups.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Whether Fair Coloring is FPT by neighborhood diversity alone for more than two colors is the immediate open boundary left by the paper’s dichotomy.
The same type-set ILP encoding may apply directly to other Max-Min fairness problems already studied for matchings and shortest paths.
If the balancing step fails, an FPT algorithm can still be recovered by enumerating finer integer distributions inside each type rather than invoking the matrix lemma.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main takeaway is a clean W[1]-hardness for Fair Coloring by number of groups p, already at k=2, on forests of depth two and on modular-width-two graphs, plus a reusable byproduct that unary vector bin packing is W[1]-hard by dimension. Both reductions (Grid Tiling to packing, packing to coloring) look carefully written and correct. The XP algorithm for k=2 and the FPT algorithm by neighborhood diversity alone when k=2 (difference-constraint LP whose vertices are integral) are also convincing and use standard tools well.

What is new is the problem itself under Max-Min group balance, the packing hardness, and the precise location of the FPT/W[1] border on these parameters. The citation pattern is appropriate; the self-citation is minor and the classical balanced-edge-coloring lemmas are properly invoked.

The soft spot is real and load-bearing for one positive claim. In Theorem 4.2 the authors solve an ILP that only enforces aggregate fairness per type, then invoke the balanced matrix decomposition (Lemma 2.2) and assert that each summand is automatically ℓ-fair. Column-sum balance alone does not force every individual difference vector inside [-ℓ,ℓ]; a summand can overshoot while another compensates. The 1×2 counter-example (A=(3 1), y_I=2, ℓ=1) already shows the step fails. So the claimed FPT by (nd,p) is incompletely justified. The rest of the paper does not depend on it.

This is for people who work on parameterized algorithms for coloring or fairness constraints on graphs. A referee who knows Lenstra and structural parameters will get value from the hardness side and the k=2 results immediately; the gap in 4.2 is fixable in revision (stronger ILP, different rounding, or an extra matching step) and does not sink the contribution. I would send it to peer review.

Referee Report

2 major / 5 minor

Summary. The paper studies the parameterized complexity of Fair Coloring: given a graph whose vertices are partitioned into p groups, decide whether there is a proper k-coloring in which every color class is ℓ-fair under the Max-Min criterion. The main negative results are that the problem is W[1]-hard parameterized by p alone, already for k=2, on forests of component depth 2 and on modular-width-2 graphs (Theorem 3.1); the hardness is obtained via a new intermediate result that Unary Vector Bin Packing is W[1]-hard in the dimension (Theorem 3.2). On the positive side the authors give an XP algorithm in p for k=2 (Theorem 3.3), an FPT algorithm in neighborhood diversity for k=2 via an integral difference-constraint LP (Theorem 4.1), and claim FPT in the combined parameter (nd,p) for arbitrary k by reducing to an ILP with 2^O(nd)nd p variables and invoking Lenstra (Theorem 4.2).

Significance. If correct, the results cleanly locate the tractability boundary of a natural fairness-constrained coloring problem: hardness already on forests and mw=2 when parameterized only by the number of groups, contrasted with FPT once neighborhood diversity (and, for general k, also p) is added. The by-product that unary multi-dimensional bin packing is W[1]-hard in the dimension is of independent interest and is obtained by a clean parameterized reduction from Grid Tiling. The k=2 FPT algorithm via integrality of a difference-constraint polytope is technically neat. These contributions would be a solid addition to the parameterized-complexity literature on fair graph problems, provided the general FPT claim is repaired.

major comments (2)

[Theorem 4.2, sufficiency (pp. 10-11)] Theorem 4.2, sufficiency direction (pp. 10–11): after solving ILP2 the authors form, for each type I, the matrix A=(x_{i,j,I}) and invoke Lemma 2.2 to write A=A_1+⋯+A_{y_I} so that row sums and column sums of the summands differ by at most 1. They then assert that “because of Conditions (10) and (14) the coloring is ℓ-fair.” Condition (10) only bounds the aggregate column-difference vector by y_I·ℓ. Column-sum balance alone permits the individual differences d_s=(A_s)_j-(A_s)_{j'} to vary; a summand can realise difference ℓ+1 while another realises ℓ-1. A minimal counter-example is the 1 imes2 matrix A=(3 1), y_I=2, ℓ=1 (aggregate difference 2≤2ℓ): every balanced decomposition produces a summand with column difference 2>ℓ. The same phenomenon occurs whenever a stable-set module is the sole member of I. Consequently the cited lemma does not justify the step from aggregate to per-class fai
[Theorem 4.2, ILP2 conditions (11)-(12)] Theorem 4.2, ILP2 formulation: Condition (11) is written as a logical implication (“if y_I=0 then all x_{i,j,I}=0”). This is not a linear (or even polynomial) constraint. Without it, a feasible solution may place positive mass on a type with y_I=0; the subsequent matrix decomposition with b=y_I=0 is then undefined and the construction fails. For stable-set modules, constraint (8) only forces ∑_j x_{i,j,I}≥y_I, which is vacuous when y_I=0, so the implication is not implied by the remaining inequalities. The ILP must be rewritten with standard linear inequalities (e.g., big-M bounds x_{i,j,I}≤n_{i,j} y_I) before Lenstra’s algorithm can be applied.

minor comments (5)

[Figure 1] Figure 1 caption and the yellow node “nd”: the text states that nd is FPT for k=2 and open in general, which matches Theorem 4.1, but the figure legend could explicitly mark the open status of nd for arbitrary k to avoid confusion with the green (nd+p) node.
[Theorem 3.3] Theorem 3.3: the DP table size is written (2|V|)^{p choose 2} while the running-time claim uses (2|V|)^{p^2}; the two expressions differ by a lower-order factor but should be aligned for precision.
[Theorem 3.1] Proof of Theorem 3.1, sufficiency: the displayed equalities |C_1 ∩ V_j|=B+n-m and |C_2 ∩ V_j|=A+m are correct under the given definitions of |X_j| and |Y_j|, but a one-line reminder that A_j=∑_i w_{i,j} cancels would help the reader.
Several minor typos: “dimen-sions” (p. 6), “depthtwo” (p. 8), “ify I=0” missing spaces (p. 10), and “O^*(2^{O(2^{nd} nd^2 p log p)})” whose exponent is slightly looser than the Lenstra bound with k=Θ(2^{nd} nd p).
[Section 1, Related Work] Related-work paragraph on Fair Matching cites the authors’ own concurrent work [18]; a brief forward pointer clarifying the relationship (same fairness measure, different problem) would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: hardness and FPT claims rest on external Grid Tiling, classical Lenstra/De Werra lemmas, and self-contained reductions.

full rationale

This is a pure parameterized-complexity paper. The W[1]-hardness chain (Theorem 3.2 from Grid Tiling, then Theorem 3.1 from Unary Multi-dimensional Bin Packing) is a standard many-one parameterized reduction whose source problem is external and independently established. The FPT algorithms (Theorems 4.1–4.2) reduce Fair Coloring to an ILP with O(2^nd · nd · p) variables solved by Lenstra’s classical theorem, plus a 1970s balanced edge-coloring lemma of De Werra; neither result is defined in terms of the target claim. The sole self-citation ([18], the authors’ fair-matching paper) appears only in Related Work and is never invoked inside a proof. There are no fitted parameters, no uniqueness theorems imported from the authors, and no renaming of known empirical patterns. A separate correctness gap in the sufficiency direction of Theorem 4.2 (aggregate vs. per-class fairness under balanced matrix decomposition) is a proof-soundness issue, not circularity, and does not raise this score. The derivation chain is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The paper is a pure complexity-theoretic contribution. It inherits standard W[1]-hardness of Grid Tiling, Lenstra’s integer-programming theorem, and classical existence of balanced edge colorings of bipartite multigraphs. No numeric parameters are fitted; the only modeling choices are the definitions of ℓ-fairness and of the intermediate unary vector-bin-packing problem.

assumptions (5)

standard math Grid Tiling is W[1]-hard parameterized by t (even with unary numbers)
Invoked as the source problem for Theorem 3.2; cited from Cygan et al. and Marx.
standard math Lenstra’s theorem: ILP in f variables is solvable in O*(f^{O(f)}) time
Theorem 2.3, used to conclude FPT from the variable count of ILP2 in Theorem 4.2.
standard math Every bipartite multigraph admits a balanced k-edge-coloring (De Werra)
Lemma 2.1 / 2.2, used to decompose assignment matrices into nearly equal color classes in Theorem 4.2.
domain assumption Neighborhood diversity, modular-width, tree-depth and related structural parameters are defined as in the standard structural-parameter literature
Used throughout the parameter landscape (Figure 1) and in the statements of all main theorems.
ad hoc to paper A set is ℓ-fair when the Max-Min difference of group sizes inside it is at most ℓ; a coloring is ℓ-fair when every color class is
Definition of the Fair Coloring problem in Section 2; the entire complexity landscape is relative to this fairness notion.

invented entities (1)

Fair Coloring (ℓ-fair proper k-coloring under a given vertex-group partition)
purpose: The decision problem whose parameterized complexity is classified
Introduced in Section 2 as the central object of study; not identical to classical equitable coloring (which balances color-class sizes, not group counts inside classes).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Parameterized Complexity of Fair Coloring Problem." pith.science (2026). https://pith.science/paper/FBEPOSXX

@misc{pith2026260727004,
  author       = {Pith},
  title        = {Pith review of: Parameterized Complexity of Fair Coloring Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FBEPOSXX}},
  note         = {Machine review of arXiv:2607.27004}
}

abstract

Given a graph $G=(V,E)$, a (proper) $k$-coloring for $G$ is a vertex coloring with $k$ colors such that every two adjacent vertices receive different colors. Suppose that the vertex set $V$ is partitioned into some groups, a proper coloring is called fair if for every color class, the difference between the number of vertices in any two groups does not exceed a given threshold. In this paper, we investigate the parameterized complexity of the fair coloring problem with respect to the structural parameters of the input graph. In particular, we prove that the problem is W[1]-hard with respect to the number of groups for forests and also graphs of modular-width two, even when the number of colors is equal to two. On the positive side, we prove that when the number of colors is equal to two, then the problem is FPT with respect to neighborhood diversity of the input graph. Moreover, in general, the problem is FPT with respect to neighborhood diversity and the number of groups. As a by-product, we prove that unary vector bin packing problem is W[1]-hard with respect to the dimension.

Figures

Figures reproduced from arXiv: 2607.27004 by the authors.

**Figure 1.** Summary of our main results regarding Fair Coloring problem. An arrow from f to g means that g is bounded by a function of f and so W[1]-hardness result with respect to f implies W[1]-hardness with respect to g. Parameters marked by green are proved to be FPT. Parameters marked by red are proved to be W[1]- hard. Parameters marked by yellow is known to be FPT in the case of k = 2 and its complexity is unknown in gen… view at source ↗

**Figure 2.** The constructed graph G in the proof of Theorem 3.1. We construct an instance of Fair Coloring as follows. Let p = d + 1 and ℓ = 0. Let S and T be sets with |S| = n − m + B and |T| = A + m + 1. Also, for each (i, j) ∈ [n] × [d], let Wi,j be a set with |Wi,j | = wi,j , Xj , Yj be sets with |Xj | = B − Bj , |Yj | = Bj + A − Aj . Also, let Z = {zi,j | i ∈ [n], j ∈ [d]}. All these sets are disjoint. The graph G = (V, E)… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 1 linked inside Pith

[1]

MIT press, 2023

Solon Barocas, Moritz Hardt, and Arvind Narayanan.Fairness and machine learning: Limitations and opportu- nities. MIT press, 2023

2023
[2]

Parameterized (approximate) defective coloring.SIAM Journal on Discrete Mathematics, 34(2):1084–1106, 2020

R´ emy Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (approximate) defective coloring.SIAM Journal on Discrete Mathematics, 34(2):1084–1106, 2020

2020
[3]

The structural complexity landscape of finding balance- fair shortest paths.Theoretical Computer Science, 933:149–162, 2022

Matthias Bentert, Leon Kellerhals, and Rolf Niedermeier. The structural complexity landscape of finding balance- fair shortest paths.Theoretical Computer Science, 933:149–162, 2022

2022
[4]

Fair algorithms for clustering

Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. Advances in Neural Information Processing Systems, 32, 2019

2019
[5]

Dynamic programming on graphs with bounded treewidth

Hans L Bodlaender. Dynamic programming on graphs with bounded treewidth. InInternational Colloquium on Automata, Languages, and Programming, pages 105–118. Springer, 1988

1988
[6]

The complexity of finding fair many-to-one matchings.ACM Transactions on Algorithms, 20(2):1–37, 2024

Niclas Boehmer and Tomohiro Koana. The complexity of finding fair many-to-one matchings.ACM Transactions on Algorithms, 20(2):1–37, 2024

2024
[7]

A refined complexity analysis of fair districting over graphs.Autonomous Agents and Multi-Agent Systems, 37(1):13, 2023

Niclas Boehmer, Tomohiro Koana, and Rolf Niedermeier. A refined complexity analysis of fair districting over graphs.Autonomous Agents and Multi-Agent Systems, 37(1):13, 2023

2023
[8]

On multidimensional packing problems.SIAM journal on computing, 33(4):837–851, 2004

Chandra Chekuri and Sanjeev Khanna. On multidimensional packing problems.SIAM journal on computing, 33(4):837–851, 2004

2004

Show all 25 references

[9]

Multidimensional bin packing and other related problems: A survey.Computer Science Review, 24:34, 2016

Henrik I Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Multidimensional bin packing and other related problems: A survey.Computer Science Review, 24:34, 2016

2016
[10]

Springer, 2015

Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Micha l Pilipczuk, and Saket Saurabh.Parameterized algorithms, volume 5. Springer, 2015

2015
[11]

Balanced schedules.INFOR: Information Systems and Operational Research, 9(3):230–237, 1971

D De Werra. Balanced schedules.INFOR: Information Systems and Operational Research, 9(3):230–237, 1971

1971
[12]

On a particular conference scheduling problem.INFOR: Information Systems and Operational Research, 13(3):308–315, 1975

D De Werra. On a particular conference scheduling problem.INFOR: Information Systems and Operational Research, 13(3):308–315, 1975

1975
[13]

On the complexity of some colorful problems parameterized by treewidth.Information and Computation, 209(2):143–153, 2011

Michael R Fellows, Fedor V Fomin, Daniel Lokshtanov, Frances Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth.Information and Computation, 209(2):143–153, 2011. 12

2011
[14]

Parameterized complexity of coloring problems: Treewidth versus vertex cover.Theoretical Computer Science, 412(23):2513–2523, 2011

Jiˇ r ´ ı Fiala, Petr A Golovach, and Jan Kratochv ´ ıl. Parameterized complexity of coloring problems: Treewidth versus vertex cover.Theoretical Computer Science, 412(23):2513–2523, 2011

2011
[15]

Clique-width: on the price of generality

Fedor V Fomin, Petr A Golovach, Daniel Lokshtanov, and Saket Saurabh. Clique-width: on the price of generality. InProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 825–834. SIAM, 2009

2009
[16]

Using neighborhood diversity to solve hard problems.arXiv preprint arXiv:1201.3091, 2012

Robert Ganian. Using neighborhood diversity to solve hard problems.arXiv preprint arXiv:1201.3091, 2012

2012 arXiv
[17]

Garey, David S

Michael R. Garey, David S. Johnson, and Larry Stockmeyer. Some simplified np-complete graph problems. Theoretical Computer Science, 1(3):237–267, 1976

1976
[18]

Parameterized complexity of fair many-to-one matchings.Theoretical Com- puter Science, page 115727, 2025

Ramin Javadi and Hossein Shokouhi. Parameterized complexity of fair many-to-one matchings.Theoretical Com- puter Science, page 115727, 2025

2025
[19]

PhD thesis, Uni- versit´ e Paris Dauphine, 2022

Michael Lampis.Structural Graph Parameters, Fine-Grained Complexity, and Approximation. PhD thesis, Uni- versit´ e Paris Dauphine, 2022

2022
[20]

Integer programming with a fixed number of variables.Mathematics of operations research, 8(4):538–548, 1983

Hendrik W Lenstra Jr. Integer programming with a fixed number of variables.Mathematics of operations research, 8(4):538–548, 1983

1983
[21]

On the optimality of planar and geometric approximation schemes

D´ aniel Marx. On the optimality of planar and geometric approximation schemes. In48th Annual IEEE Sympo- sium on Foundations of Computer Science (FOCS’07), pages 338–348. IEEE, 2007

2007
[22]

Equitable coloring.The American mathematical monthly, 80(8):920–922, 1973

Walter Meyer. Equitable coloring.The American mathematical monthly, 80(8):920–922, 1973

1973
[23]

Msol partitioning problems on graphs of bounded treewidth and clique-width.Theoretical Computer Science, 377(1-3):260–267, 2007

Micha¨ el Rao. Msol partitioning problems on graphs of bounded treewidth and clique-width.Theoretical Computer Science, 377(1-3):260–267, 2007

2007
[24]

Minimizing margin of victory for fair political and educational districting

Ana-Andreea Stoica, Abhijnan Chakraborty, Palash Dey, and Krishna P Gummadi. Minimizing margin of victory for fair political and educational districting. InProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 1305–1313, 2020

2020
[25]

There is no asymptotic ptas for two-dimensional vector packing.Information Processing Letters, 64(6):293–297, 1997

Gerhard J Woeginger. There is no asymptotic ptas for two-dimensional vector packing.Information Processing Letters, 64(6):293–297, 1997. Department of Mathematical Sciences, Isfahan University of Technology, P.O. Box 84156-83111, Isfahan, Iran. Email address:rjavadi@iut.ac.ir 13

1997

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.

[1] [1]

MIT press, 2023

Solon Barocas, Moritz Hardt, and Arvind Narayanan.Fairness and machine learning: Limitations and opportu- nities. MIT press, 2023

2023

[2] [2]

Parameterized (approximate) defective coloring.SIAM Journal on Discrete Mathematics, 34(2):1084–1106, 2020

R´ emy Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (approximate) defective coloring.SIAM Journal on Discrete Mathematics, 34(2):1084–1106, 2020

2020

[3] [3]

The structural complexity landscape of finding balance- fair shortest paths.Theoretical Computer Science, 933:149–162, 2022

Matthias Bentert, Leon Kellerhals, and Rolf Niedermeier. The structural complexity landscape of finding balance- fair shortest paths.Theoretical Computer Science, 933:149–162, 2022

2022

[4] [4]

Fair algorithms for clustering

Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. Advances in Neural Information Processing Systems, 32, 2019

2019

[5] [5]

Dynamic programming on graphs with bounded treewidth

Hans L Bodlaender. Dynamic programming on graphs with bounded treewidth. InInternational Colloquium on Automata, Languages, and Programming, pages 105–118. Springer, 1988

1988

[6] [6]

The complexity of finding fair many-to-one matchings.ACM Transactions on Algorithms, 20(2):1–37, 2024

Niclas Boehmer and Tomohiro Koana. The complexity of finding fair many-to-one matchings.ACM Transactions on Algorithms, 20(2):1–37, 2024

2024

[7] [7]

A refined complexity analysis of fair districting over graphs.Autonomous Agents and Multi-Agent Systems, 37(1):13, 2023

Niclas Boehmer, Tomohiro Koana, and Rolf Niedermeier. A refined complexity analysis of fair districting over graphs.Autonomous Agents and Multi-Agent Systems, 37(1):13, 2023

2023

[8] [8]

On multidimensional packing problems.SIAM journal on computing, 33(4):837–851, 2004

Chandra Chekuri and Sanjeev Khanna. On multidimensional packing problems.SIAM journal on computing, 33(4):837–851, 2004

2004