Answer: Polynomial-time solvable exactly: \(\mathrm{OPT}_k=k\), with one interval and one bin range per type.
Theorem 2 — class: algorithmic
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), demands \(d_t\le s\), per-capita supply \(s>0\), and an integer \(k\ge1\), find the minimum integer \(q\) and a succinct schedule of \(q\) equal-duration bins. Each household must be fully served in exactly \(k\) distinct bins, and each bin’s total demand mass must be at most \(s\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Let \(\sum_t\mu_t=1\), with binary rational demands and supply satisfying \(0<d_t\le s\) and \(s>0\), and a binary encoded integer \(k\ge1\). Let \(m\) count distinct demands and \(L\) be the total input bit length.
Represent type \(t\) by an atomless interval \([0,\mu_t)\) with Lebesgue measure. Different households of the same type may receive different schedules; a connected household receives its full demand.
A feasible schedule has an integer \(q\ge k\) of bins, each lasting \(1/q\). For each bin \(j\), choose measurable sets \(A_{tj}\subseteq[0,\mu_t)\) such that every household belongs to exactly \(k\) distinct bins and \(\sum_t d_t\lvert A_{tj}\rvert\le s\). Let \(\mathrm{OPT}_k\) be the minimum feasible \(q\).
A succinct schedule partitions each type interval into finitely many intervals with rational endpoints and assigns each interval a set of exactly \(k\) bin indices, encoded as disjoint ranges with binary integer endpoints.
Does a polynomial-time algorithm, with running time measured in \(m,\tau,L\), always produce a succinct feasible schedule satisfying \(q\le\left(\frac32+\frac{1}{5k}\right)\mathrm{OPT}_k+3k\), or is achieving this guarantee NP-hard?
For discrete households, First-Fit applied to \(k\) consecutive copies of the household list, forbidding repeated copies of a household in one bin, achieves this same bound; exact optimization is NP-hard already for \(k=1\). [Verified discrete results](https://arxiv.org/html/2311.16742v3)
No result settling this precise atomless scheduling guarantee was located.
Yes. An exact polynomial-time algorithm produces a succinct schedule with \(\mathrm{OPT}_k=k\).
I interpret mass and capacity exactly as specified: type \(t\) contributes \(d_t|A_{tj}|\) to bin \(j\). Under this interpretation, the normalization and demand bound rule out scarce supply. Indeed, writing \(D=\sum_t\mu_t d_t\), we have
\[
D\le\sum_t\mu_t s=s.
\]
To also examine the nontrivial atomless case, Section 3 proves an exact feasibility criterion without assuming \(D\le s\).
Choose \(q=k\), and set \(A_{tj}=[0,\mu_t)\) for every type \(t\) and every bin \(j\in\{1,\ldots,k\}\).
Every household belongs to exactly \(k\) distinct bins. Each bin has load \(\sum_t d_t|A_{tj}|=D\le s\), so this schedule is feasible.
Conversely, every feasible schedule must have \(q\ge k\) by definition. Therefore \(\mathrm{OPT}_k=k\).
The succinct output consists of one interval \([0,\mu_t)\) for each type, assigned the single inclusive bin range \([1,k]\). Its rational endpoints already occur in the input, and its bin endpoints require \(O(\log(k+1))\) bits. The total output length is \(O(L+\tau\log(k+1))\), and constructing it takes polynomial time in \(m,\tau,L\), even when \(k\) is exponentially large in its bit length.
Since the algorithm is exact, it satisfies the requested inequality
\[
q\le\left(\frac32+\frac{1}{5k}\right)\mathrm{OPT}_k+3k.
\]
The discrete hardness result in the [referenced paper](https://arxiv.org/html/2311.16742v3) concerns indivisible households. It does not establish hardness for this atomless model.
The following result addresses the nontrivial case obtained by relaxing the assumptions that force \(D\le s\).
Proposition. Suppose there are finitely many types with positive rational masses and demands, and positive rational supply \(s\). For a given integer \(q\), an atomless schedule is feasible if and only if \(q\ge k\) and \(qs\ge kD\), where \(D=\sum_t\mu_t d_t\). Consequently,
\[
\mathrm{OPT}_k=\max\left\{k,\left\lceil\frac{kD}{s}\right\rceil\right\}.
\]
Necessity. Every household belongs to exactly \(k\) bins. Integrating this identity over each type gives \(\sum_{j=1}^q|A_{tj}|=k\mu_t\). Summing the bin loads therefore yields
\[
kD=\sum_{j=1}^q\sum_t d_t|A_{tj}|\le qs.
\]
The condition \(q\ge k\) is also necessary.
Sufficiency. Assume \(q\ge k\) and \(qs\ge kD\). Order the types and define \(W_0=0\) and \(W_t=\sum_{u=1}^t\mu_ud_u\). Map household \(x\in[0,\mu_t)\) to its demand coordinate \(y=W_{t-1}+d_tx\). These maps partition \([0,D)\), and demand-weighted measure \(d_t\,dx\) becomes ordinary length \(dy\).
Partition \([0,D)\) into the \(q\) half-open cells
\[
C_r=\left[\frac{rD}{q},\frac{(r+1)D}{q}\right),\qquad r\in\{0,\ldots,q-1\}.
\]
For every household whose coordinate lies in \(C_r\), assign the bin set
\[
B_r=\left\{1+((r+h)\bmod q):h\in\{0,\ldots,k-1\}\right\}.
\]
Because \(k\le q\), these are exactly \(k\) distinct bins. For each bin \(j\), precisely \(k\) cells have \(j\in B_r\): their indices are the distinct residues \(r\equiv j-1-h\pmod q\), with \(h\in\{0,\ldots,k-1\}\). Each cell has demand-weighted measure \(D/q\). Thus every bin has load \(kD/q\le s\), proving feasibility.
This construction also gives a finite rational schedule. Intersect the type-coordinate intervals \([W_{t-1},W_t)\) with the cells, then map those intersections back to household coordinates. All resulting endpoints are rational. Each \(B_r\) is a cyclic block of consecutive indices, so it is encoded by at most two disjoint ranges.
There are at most \(\tau+q-1\) nonempty pieces: the combined partition of \([0,D)\) has at most \(\tau-1\) internal type boundaries and \(q-1\) internal cell boundaries. This completes the proof.
The proposition does not automatically give a polynomial-size schedule when the original restrictions are removed.
For example, retain normalized mass but drop \(d_t\le s\). Take one type with \(\mu_1=1\), demand \(d_1=2^n\), supply \(s=1\), and \(k=1\). The input length is \(O(n)\).
Every interval in a succinct schedule is assigned to one bin. If its length is \(\ell\), that bin’s capacity implies \(2^n\ell\le1\), hence \(\ell\le2^{-n}\). Partitioning the unit type interval therefore requires at least \(2^n\) nonempty intervals, regardless of the number of bins used.
Thus this natural scarce-supply extension has an exponential output-size obstruction. Under the actual premises, Section 2 avoids that obstruction and completely resolves the requested guarantee.
⟨structured verdict parsed — rendered above⟩
The output correctly resolves the stated task: it gives an exact polynomial-time algorithm with \(\mathrm{OPT}_k=k\). No major or minor mathematical issues were found. The supplementary feasibility criterion and output-size obstruction are also correct.
Section 1 defines \(D=\sum_t\mu_td_t\). Since each \(\mu_t>0\), each \(d_t\le s\), and \(\sum_t\mu_t=1\), its calculation
\(D\le\sum_t\mu_ts=s\)
is valid.
This uses the task’s explicit capacity rule, in which demand is weighted by the measure of connected households. It is not an unintended interpretation or an extra assumption.
Section 2 chooses the integer \(q=k\), which satisfies \(q\ge k\). Each bin consequently lasts \(1/k\), as required.
For every type and bin, \(A_{tj}=[0,\mu_t)\) is measurable. Every household—including the left endpoint of each type interval—belongs to all \(k\) distinct bins. The omitted right endpoint is outside the household domain, so there is no endpoint exception.
Each bin has load \(D\le s\). Connected households receive their full demand according to the specified load model. Thus the schedule is feasible.
Every feasible schedule has \(q\ge k\) by definition, and the construction attains \(q=k\). Therefore \(\mathrm{OPT}_k=k\). No additional lower-bound argument is needed.
One interval per type partitions its entire household domain. Its endpoints are rational, and the inclusive integer range \([1,k]\) represents exactly \(k\) distinct bin indices.
The stated output bound \(O(L+\tau\log(k+1))\) accounts for the rational interval endpoints and the bin-range endpoints. Copying these data and emitting the records takes polynomial time in the specified input parameters. The algorithm never enumerates the bins, so binary encoding of a large \(k\) causes no difficulty.
The construction is exact. With \(k\ge1\), the requested right-hand side is greater than or equal to \(\mathrm{OPT}_k=q\). The additive term and approximation coefficient therefore present no restriction on this construction.
The referenced paper studies individual items whose sizes are summed within each bin and requires each item to appear in \(k\) distinct bins. This supports the output’s distinction between that discrete model and the task’s measure-weighted atomless model. The proof here does not rely on transferring any discrete algorithm or hardness theorem. [Referenced paper](https://arxiv.org/html/2311.16742v3)
Section 3 retains the task’s positive integer \(k\). Integrating the pointwise membership requirement gives \(\sum_{j=1}^q|A_{tj}|=k\mu_t\). All sums are finite, so summing across types and bins is justified. The resulting inequality \(kD\le qs\), together with \(q\ge k\), establishes the claimed necessary conditions.
Positive demands make each coordinate map \(x\mapsto W_{t-1}+d_tx\) invertible on its type interval. The resulting half-open intervals partition \([0,D)\), and the stated change from demand-weighted measure to coordinate length is valid.
The cells also partition \([0,D)\) without endpoint ambiguity. Because \(k\le q\), each assigned set \(B_r\) contains exactly \(k\) distinct indices. For a fixed bin, the displayed residues identify exactly \(k\) distinct cells. Each contributes demand-weighted measure \(D/q\), so the load is \(kD/q\le s\).
Hence both directions of the criterion are established, and the displayed formula for the optimum follows.
Intersections of type-coordinate intervals and cells have rational endpoints; mapping them back preserves rationality. A cyclic block of \(k\le q\) indices can be represented by at most two disjoint inclusive ranges, including the cases \(k=q\) and \(q=1\).
The count of at most \(\tau+q-1\) nonempty pieces follows from the stated bound on internal boundaries. Coincident boundaries only reduce that count. The output correctly refrains from claiming this construction has polynomial output size when \(q\) is large.
In Section 4, the integer demand \(2^n\) has binary encoding length \(O(n)\). With \(k=1\), each partition interval is assigned to exactly one bin. Capacity forces its length to be at most \(2^{-n}\), even if that bin contains other intervals. Covering the unit type interval therefore requires at least \(2^n\) nonempty pieces.
This example explicitly relaxes \(d_t\le s\), so it does not contradict the polynomial construction under the original assumptions.
No repair or additional clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.