Open Research Index

A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints

Shengminjie Chen, Kaifeng Lin, Xiaoming Sun, Jialin Zhang

arXivarxiv/2610.16785Oct 12, 2026cs.DSscore 0

Submodular maximization arises in a wide range of combinatorial optimization problems and has been extensively studied from the perspective of approximation algorithms. For maximizing nonnegative, non-monotone submodular functions subject to a matroid constraint, randomized algorithms achieve a $0.401$-approximation, whereas obtaining comparable deterministic guarantees remains challenging. In this paper, we present a deterministic $0.401$-approximation algorithm in the exact value and independence oracle model, improving upon the previous deterministic guarantee of $(0.385-\varepsilon)$…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2610.16785
curl -X POST /api/v1/records/arxiv/2610.16785/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.16785/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'