d4-conf-atal-2013-0085

My lead is Continuous Complex-Demand Knapsack (CC-KP), mirroring Theorem 5.2, proved in this paper. The theorem says that C-KP has no FPTAS unless \(\mathrm{P}=\mathrm{NP}\): given items with values \(v_k>0\) and complex demands \(d_k=d_k^{\rm R}+\mathrm{i}d_k^{\rm I}\), where both components are nonnegative, choose a subset maximizing \(\sum_{k\in S}v_k\) subject to \(\left|\sum_{k\in S}d_k\right|\le C\). The paper proves this by reducing equipartition to a cardinality version of C-KP: it sets \(M=n/2\), \(d_k^{\rm R}=w_k\), \(d_k^{\rm I}=\beta(w_{\max}-w_k)\), and chooses \(C\) and \(\beta\) so the capacity disk is tangent to the halfplane imposed by \(|S|\ge n/2\). Feasibility then forces an equal-size, equal-weight partition. An FPTAS would solve that integer-valued objective exactly by taking \(\epsilon=1/(n+1)\), implying \(\mathrm{P}=\mathrm{NP}\).

In CC-KP, the society has a finite support \(T\) of device types \(t=(d_t,v_t)\), with rational masses \(\mu_t\ge 0\) summing to \(1\). A type specifies both the device’s full complex demand and its value when that demand is met. Let \(c\) be the supply capacity per capita, and choose served mass \(y_t\in[0,\mu_t]\) for each type. Every served device receives its entire demand \(d_t\); every unserved device receives nothing. The question is to maximize \(\sum_{t\in T}y_tv_t\), subject to
\[ \left|\sum_{t\in T}y_td_t\right|\le c. \]
A solution is a feasible vector \(y\), with the aim of returning one whose welfare is within a requested \(\epsilon\) of the optimum. The aggregate demand and the welfare are per-capita quantities; in a population of \(N\) devices the total capacity scales as \(Nc\).

A plausible regime is a large fleet of standardized EV chargers or appliances: many devices share the same demand and value, while the number \(\tau=|T|\) of distinct device and service-contract types is much smaller than \(N\). The type-level value can represent the benefit of completing that device’s charging requirement. The aggregate AC capacity constraint and the paper’s value-maximizing allocation objective remain intact. This is not fractional power to an individual device: \(y_t\) is the mass of devices of type \(t\) that receive their whole requested service.

I expect CC-KP to be Class A, as a second-order cone optimization problem: the variables have box constraints and the aggregate-demand constraint is a Euclidean norm bound on a linear function of \(y\). Convex optimization therefore gives a natural route to \(\epsilon\)-optimal allocations. The paper’s particular hardness reduction also shows why the discrete result need not transfer. In its equipartition instance, the continuous analogue can select half of every item: that fractional selection has cardinality \(n/2\) and weight \(W/2\), without finding an equipartition. For a finite population with \(N\) devices and \(\tau\) types, rounding each selected type mass down to whole devices preserves feasibility, since demands lie in the first quadrant, and loses at most \(\tau v_{\max}/N\) welfare per capita. That gives a concrete connection back to large finite populations.

This case covers the underlying C-KP welfare-allocation problem in Theorem 5.2. It does not claim to mirror the paper’s incentive-compatibility results or its GC-KP extension. Its weakest point is that the original problem explicitly gives each item an indivisible \(0\)-or-\(1\) selection, while CC-KP permits selection of any mass of a type. Authors might regard that as a fractional relaxation rather than their problem. I think they should recognize it as their population analogue in the stated regime: individual service remains all-or-nothing, while a continuum lets the operator serve a proportion of a large, interchangeable type class. Further questions include bounding the finite-population rounding loss under broader parameter regimes, and whether the paper’s monotonicity and payment construction extends to mass allocations with private demand and value reports.