ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let n≫k>2n \gg k > 2, and let λ1,…,λk∈Q\lambda_1,\ldots,\lambda_k \in \mathbb{Q} satisfy λi>0\lambda_i>0 for each ii and

λ1+⋯+λk=1.\lambda_1+\cdots+\lambda_k=1.

Set ni=λinn_i=\lambda_i n for each ii, so that the λi\lambda_i determine a partition of nn. Partition-runtime conjecture. There exists a choice of λ1,…,λk\lambda_1,\ldots,\lambda_k such that the resulting runtime satisfies

Tn=Θ(knlog⁡2n).T_n=\Theta(k n\log^2 n).

The preceding analysis establishes this bound for the uniform partition, while the paper notes that numerical experiments suggest nonuniform partitions may perform better; whether an optimal partition can attain this asymptotic bound remains unresolved.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.