{"ID":2843639,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.08801","arxiv_id":"2511.08801","title":"A Simple Analysis of Ranking in General Graphs","abstract":"We provide a simple combinatorial analysis of the Ranking algorithm, originally introduced in the seminal work by Karp, Vazirani, and Vazirani [KVV90], demonstrating that it achieves a $(1/2 + c)$-approximate matching for general graphs for $c \\geq 0.005$.","short_abstract":"We provide a simple combinatorial analysis of the Ranking algorithm, originally introduced in the seminal work by Karp, Vazirani, and Vazirani [KVV90], demonstrating that it achieves a $(1/2 + c)$-approximate matching for general graphs for $c \\geq 0.005$.","url_abs":"https://arxiv.org/abs/2511.08801","url_pdf":"https://arxiv.org/pdf/2511.08801v1","authors":"[\"Mahsa Derakhshan\",\"Mohammad Roghani\",\"Mohammad Saneian\",\"Tao Yu\"]","published":"2025-11-11T21:55:39Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}