Open Research Index

The Price of Feasibility: Greedy Approximation Bounds for String Supermodular Optimization over Oracle-Conditioned Greedoids

Joan Vendrell Gallart, Russell Bent, Solmaz Kia

arXivarxiv/2609.07787Sep 7, 2026math.OCscore 0

Greedy algorithms efficiently approximate combinatorial optimization problems, but their guarantees weaken when feasibility couples combinatorial structure with global physical constraints. We study monotone nondecreasing supermodular minimization over the bases of a graphic greedoid under physics-induced constraints. We model physics-informed selection using a look-ahead oracle that identifies candidates extendable to a feasible basis, yielding the Conditioned Sequential Greedy Algorithm. We derive a closed-form approximation bound, which we call the price of feasibility, based on the…

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