Open Research Index

Solving Convex Quadratic Optimization with Indicators Over Structured Graphs

Aaresh Bhathena, Salar Fattahi, Andrés Gómez, Simge Küçükyavuz

arXivarxiv/2603.02103Mar 2, 2026math.OCscore 0

This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth of the Hessian's support graph, its volume growth, and an appropriate margin parameter. Under suitable structural conditions, the overall complexity scales linearly with the problem dimension. To demonstrate…

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