| paper | d4-conf-ijcai-2016-0464 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Achieving any fixed approximation ratio \(\rho\in(50/51,1]\) is NP-hard, even with dyadic rational masses. The requested polynomial-time algorithm cannot exist unless \(\mathrm{P}=\mathrm{NP}\); ratios \(\rho>1\) are impossible. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite item set \(X\) with \(|X|=2q\) and a rational distribution \(\mu\) over supported binary utility types \(t:X\to\{0,1\}\), compute a pair of disjoint \(q\)-item sets maximizing \(U_\mu(S)=\sum_t\mu_t\sum_{j=1}^{2}\max_{x\in S_j}u_t(x)\). In particular, is there a polynomial-time approximation with ratio strictly greater than \(50/51\)?
The audience is a finite support of complete utility types \(t:X\to\{0,1\}\), each carrying binary-rational mass \(\mu_t\) summing to one. The decision remains an integral schedule of disjoint \(q\)-item sets, and the objective is the expected audience utility \(U_\mu(S)\).
The opponent notes that the paper’s matching and LP approximation methods may extend by weighting types, so some algorithmic extensions could add little new structure; this does not undermine the anchored hardness question.
fatal: False
The mirror covers the hardness claims in Theorems 1 and 2. It leaves the algorithmic results in Theorems 3 through 6 and other CPD variants unexamined.
I would make the mirror the same conference-program problem with the audience represented by a distribution over utility types. A type \(t\) is a complete utility vector \(u_t:X\to\{0,1\}\): it says which talks that kind of participant values. The input gives the supported types and binary-rational masses \(\mu_t\), summing to one. The program is still an integral schedule \(S=(S_1,\ldots,S_k)\) of disjoint \(q\)-item sets; its value is
\[ U_\mu(S)=\sum_t \mu_t\sum_{j=1}^k\max_{x\in S_j}u_t(x). \]
The task is to find a schedule maximizing \(U_\mu\). Thus the population becomes continuous, while the talks and the scheduling decision remain exactly as in CPD. This seems like a mirror the authors would recognize: it replaces a sum over named participants with the expected utility of a participant drawn from the audience distribution, without changing what a feasible program means.
A plausible regime is a large conference or festival with many participants in recurring interest cohorts. Everyone in a cohort has the same utility for every talk, and \(\mu_t\) is that cohort’s share of the audience. The number of participants \(N\) can be much larger than the number of supported profiles \(\tau\). In the paper’s hardness constructions, however, the profiles encode graph edges or nonedges, so \(\tau\) itself grows with the item set. Duplicating each participant \(R\) times gives \(N=R\tau\) without changing the type distribution. That makes a high-multiplicity audience plausible, though it does not produce a fixed-size type space as the instance grows.
My lead anchor is Theorem 1, proved in this paper. It states that CPD restricted to \(k=2\), \(m=2q\), and uniformly dichotomous utilities is NP-hard to approximate within a factor of \(50/51\). The authors prove it with an approximation-preserving reduction from MAX BISECTION, using the cited inapproximability bound for MAX BISECTION that follows from Håstad’s result. Its continuous mirror is: given \(X\), \(q\), and a rational distribution over binary utility types, with \(k=2\) and \(|X|=2q\), return a two-slot program whose value is at least \(50/51\) of the optimum. I expect this question to be Class B: the hardness transfers. Given any discrete audience, group participants with identical utility vectors and set \(\mu_t=n_t/n\). Then \(U_\mu\) is the discrete social utility divided by \(n\), preserving both the optimum and approximation ratios. The source reduction’s graph partitioning still lives in the items and their grouping into sessions; replacing the roster with masses does not remove it.
A second, complementary anchor is Theorem 2, also proved here. It states that CPD restricted to \(q=3\), \(m=3k\), and dichotomous utilities is NP-hard; the proof reduces from PARTITION INTO TRIANGLES. The corresponding continuous decision problem takes the same kind of type distribution, with \(q=3\) and \(|X|=3k\), and a rational threshold \(B\), and asks whether some program has \(U_\mu(S)\ge B\). In the reduction, each type values the two endpoints of a nonedge. With uniform mass over those types, a program reaches value \(2\) exactly when every valued pair is split across sessions, which holds exactly when the items can be partitioned into triangles. I again expect hardness to transfer, by the same grouping argument. This anchor is useful on its own terms because it shows exact hardness when the number of sessions grows, with only three talks per session.
My case covers Theorems 1 and 2, not the paper’s approximation guarantees or its whole range of CPD variants. The mirrors also raise follow-up questions: which of the paper’s approximation guarantees extend directly to rational type masses, and can restrictions on the supported utility profiles make exact scheduling tractable?
The weak point is that the paper’s hardness results do not show that aggregation makes the computation easier: their reductions have a growing number of types, often one per graph edge or nonedge. Cloning creates many attendees per type, but leaves the underlying hard instance intact. That limits the case for a *tractability gain* from continuization. It does not, in my view, undermine the mirror itself: this is still a precise, natural high-multiplicity version of the authors’ stated optimization problem, and its hardness has a clean explanation in the item structure.
The strongest case against is that the continuous version seems to change only how the audience is encoded. A natural mirror gives each supported utility vector \(t\) a rational mass \(\mu_t\), keeps the schedule integral, and maximizes
\[
U_\mu(S)=\sum_t\mu_t\sum_{j=1}^k\max_{x\in S_j}u_t(x).
\]
There is no interaction between audience members: the schedule’s feasibility is unchanged, and the audience enters only through a weighted sum. A large event with recurring interest cohorts makes this a plausible model, especially for dichotomous utilities. So this is a concern about the likely research payoff, not a persuasive objection to the model itself.
It does not defeat Theorem 1. Give each graph edge a type that values its two endpoints, with mass \(1/|E|\). The continuous objective is the discrete one divided by \(|E|\); the bisection reduction and its approximation gap remain. Cloning each type \(R\) times gives \(R|E|\) participants but only \(|E|\) types, so the construction can lie squarely in a high-multiplicity regime. The fact that the combinatorics remain in the items is not a valid objection under this programme.
Nor does it defeat Theorem 2. Give each nonedge type uniform mass. A schedule reaches value \(2\) exactly when every valued pair is split between sessions, which is equivalent to partitioning the graph into triangles. The threshold \(2\) is exact with rational masses. Again, the types can be cloned without changing the instance.
The better version of the mirror allows arbitrary rational masses over complete utility vectors. That makes the audience representation natural and leaves both anchors intact. The skeptical point is that the paper’s matching and LP methods appear to extend by weighting agents, while its hardness reductions already use only polynomially many types. The new question may therefore produce little new structure or algorithmic insight. But the programme expressly treats hardness that survives aggregation as a worthwhile boundary result, and a low expected payoff does not show that the question is not worth asking. I cannot make a strong case against this mirror under the stated standard; both anchors survive.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.