d4-conf-sagt-2024-0025

My lead is Theorem 2 in §5.1, proved in this paper. It says that for every item multiset \(D\) and every \(k\geq1\), the authors’ First-Fit extension uses at most \(\left(1.5+\frac{1}{5k}\right)\operatorname{OPT}(D_k)+3k\) bins on the \(k\)-times bin-packing instance \(D_k\). This is an approximation result for the underlying packing problem. The paper says \(k\)BP is NP-hard even for \(k=1\), but that appears as background prose, not as a numbered hardness theorem, so I do not use it as an anchor.

A plausible high-multiplicity regime is a large community served by a power feeder, with many households falling into a small number \(\tau\) of exact demand classes. Let \(N\gg\tau\) be the number of households, \(\mu_t\) the fraction in type \(t\), and \(d_t\) that type’s demand during the period being scheduled. Let total supply be \(Ns\), so \(s\) is supply per household at the population scale. A type is complete for the baseline objective: its members have the same demand, and each household’s utility is its connection time. For example, a community might have thousands of households but only a handful of standardized appliance-demand classes. The paper’s 367-household, time-varying dataset is not itself this regime; this is a different, plausible use of the same mathematical problem.

The continuous problem I would hand to a prover is Mass-\(k\)BP. Its input is the finite type set \(T\), rational masses \((\mu_t)_{t\in T}\) summing to \(1\), demands \(d_t>0\), per-capita supply \(s>0\), and an integer \(k\geq1\). Find the minimum integer \(q\) and a schedule of \(q\) equal-duration bins. In bin \(b\), let \(x_{bt}\in[0,\mu_t]\) be the mass of type \(t\) connected. Require \(\sum_t d_t x_{bt}\leq s\) in every bin and \(\sum_{b=1}^q x_{bt}=k\mu_t\) for each type. Each individual household must be connected in exactly \(k\) distinct bins. A solution is \(q\) together with a mass assignment realizing those constraints; its connection time per household is \(k/q\).

The individual-level condition is compatible with fractional type masses. For \(q\geq k\), split each type into \(q\) equal-mass cohorts, indexed by a starting bin. Assign each cohort to \(k\) consecutive bins cyclically. Every bin then receives \(k\mu_t/q\) mass of each type, while every household in every cohort appears in exactly \(k\) distinct bins. Writing \(\bar d=\sum_t\mu_t d_t\), the exact optimum is
\[ q^\star=\max\!\left\{k,\left\lceil\frac{k\bar d}{s}\right\rceil\right\}. \]
The two terms are necessary because households need \(k\) distinct bins and the bins must carry total mass-demand \(k\bar d\). The cyclic construction attains both bounds. Thus this mirror is Class A: its optimum and a compressed schedule description are computable in time polynomial in the rational input length and \(\log k\). It does not claim that the paper’s First-Fit approximation ratio carries over; the continuous population changes the underlying optimization landscape.

This is recognizably the authors’ problem: the objective is still to minimize bins for \(k\)-times packing, the bin capacity is still a supply constraint, and connection still delivers a household’s full demand or nothing. Only the population has become atomless. A fractional \(x_{bt}\) means that a fraction of the type’s households are fully connected, not that any household receives fractional electricity. The co-modification to per-capita supply is needed to keep a large-population regime meaningful. This is population continuization, not continuity of the electricity outcome.

The mirror covers the paper’s \(k\)BP packing problem and its baseline max-min connection-time application. It does not cover the experiment’s comfort objectives or maximum utility differences, which would require types to include the relevant comfort or utility information. Further questions include how closely the finite \(k\)BP optimum approaches \(q^\star\) as household counts per type grow, and how the best fixed-\(k\) connection rate \(k/q^\star\) compares with schedules that allow unequal-duration bins.

The weak point is that the paper’s motivating data are individualized and time-varying, while this mirror needs large cohorts with identical demand profiles and supply that scales with population. A referee might also say the continuous optimum is too simple to illuminate the authors’ First-Fit analysis: its finite-item ordering and packing conflicts disappear, leaving total demand as the decisive constraint. That objection limits how much of their algorithmic analysis the mirror explains. It does not erase the mirror of their underlying problem: Mass-\(k\)BP retains the \(k\)-distinct-bins requirement, bin capacity, and full-demand service, while making the society itself continuous.