Loading...
| Friend's email | |
| Your name | |
| Your email | |
| enter code | |
This page was sent successfuly
Bookmark
Review List
40 viewed
A better LP rounding for feedback arc set on tournaments
Ostovari, M
A better LP rounding for feedback arc set on tournaments
Ostovari, M ; Sharif University of Technology | 2024
40
Viewed
- Type of Document: Article
- DOI: 10.1016/j.tcs.2024.114768
- Publisher: 2024
- Abstract:
- We present a randomized algorithm to approximate the feedback arc set problem on weighted tournaments, a classic well-studied NP-hard problem. Our algorithm is based on rounding its standard linear programming relaxation. It improves the previously best-known LP rounding algorithm by achieving an approximation factor of 2.127 (best known was 2.5). As a result, we have found a better upper bound for the integrality gap of the corresponding LP. © 2024 Elsevier B.V
- Keywords:
- LP rounding ; Computational complexity ; Linear programming ; Approximation factor ; Feedback arc set ; Its standards ; Linear programming relaxation ; Randomized algorithms ; Rounding algorithm ; Set problems ; Tournament ; Upper bound ; Approximation algorithm
- Source: Theoretical Computer Science ; Volume 1015 , 2024 ; 03043975 (ISSN)
- URL: https://www.sciencedirect.com/science/article/abs/pii/S0304397524003852