pipette
ENEnglish

A deterministic algorithm for signing bipartite graphs at the Ramanujan bound

Zhiqiang Xu

Preprint

En palabras de los autores

We give a deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs. For every finite simple bipartite graph of maximum degree at most an integer , the algorithm assigns signs to its edges so that the signed adjacency matrix has operator norm strictly less than . Our algorithm builds on the randomized recursive repair framework of Jadbabaie, Saberi, and Sra~\cite{JSS26}, with deterministic rules for sign selection and vertex deletion.

Resultado principalLimitación que admiten los autores

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

Comentario de los autores: 18 pages