Metraipolis › archive › dc_fac134bb2987

Structural Complexity of One-Factor Sparse Portfolio Selection: Exact Algorithms, Parameterized Hardness, and Restricted Circuit Lower Bounds — arXiv:2609.17626

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.17626
License (as archived): CC0-1.0
Archived: 2026-10-15T18:08:20.767Z
SHA-256 of the archived text: a0ce84453bfa6799d1b54484dbc08f3c44a76d0d78aa0dacc766a7f04d541846
Stable URL of this page: https://metraipolis.com/documento/dc_fac134bb2987

How to cite

Structural Complexity of One-Factor Sparse Portfolio Selection: Exact Algorithms, Parameterized Hardness, and Restricted Circuit Lower Bounds — arXiv:2609.17626 — arXiv (en), https://arxiv.org/abs/2609.17626 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fac134bb2987 (Metraipolis archive dc_fac134bb2987, sha256 a0ce84453bfa6799d1b54484dbc08f3c44a76d0d78aa0dacc766a7f04d541846)

BibTeX

@misc{dcfac134bb2987,
  title = {Structural Complexity of One-Factor Sparse Portfolio Selection: Exact Algorithms, Parameterized Hardness, and Restricted Circuit Lower Bounds — arXiv:2609.17626},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.17626},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fac134bb2987; sha256 a0ce84453bfa6799d1b54484dbc08f3c44a76d0d78aa0dacc766a7f04d541846},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.17626. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study exact-cardinality, equally weighted minimum-variance portfolio selection under a one-factor covariance model supplied in factor form. In the nonnegative homoskedastic regime, selecting the K smallest loadings is optimal. Allowing strictly positive asset-specific idiosyncratic variances makes the decision problem NP-complete even with positive integer loadings and a strictly positive-definite covariance matrix; with identity residual covariance, exactly one negative loading also suffices. We give exact pseudo-polynomial dynamic programs for one factor and fixed factor dimension and prove W[1]-hardness parameterized by K, including the positive-data family. Consequently, a general exact polynomial-time algorithm for Monge's (2017) equally weighted single-factor variance-input formulation would imply P=NP. For a normalized binary factor encoding, we construct a depth-zero projection from modular k-SUM that preserves exact cardinality and positive definiteness. The projection transfers Lin's (2026) fixed-k circuit lower bound under its stated width and quantifier conditions and, independently, yields a parity-based proof that the portfolio language is not in nonuniform AC^0 even with identity residual covariance and polynomially bounded integer coefficients. These are restricted-circuit results: no unrestricted P/poly lower bound and no separation of P from NP is claimed.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-17 in econ.EM).
Categorie arXiv: Econometrics (econ.EM).
Pagina del lavoro: https://arxiv.org/abs/2609.17626 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T17:26:28.545Z dalla pagina https://arxiv.org/catchup/econ.EM/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).