pipette
ENEnglish

An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint

Zizong Wang, Yibo Wang

Preprint

En palabras de los autores

We give a randomized polynomial-time -approximation for maximizing a nonnegative non-monotone -submodular function under a matroid constraint, for every . The algorithm combines a top-two label rule with a nested-chain potential and maximum-weight matroid bases. Its analysis reduces the approximation guarantee to a one-dimensional time allocation: a uniform local lower bound leads to a linear differential equation, concavity closes the remaining interval, and two elementary budgets complete the proof. A strict saving in the time budget absorbs sampling and discretization errors, yielding the exact guarantee in the value-oracle model.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 22 pages, 1 figure, 1 table