Copertina

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bansal, Ishan, Cheriyan, Joseph, Grout, Logan, Ibrahimpur, Sharat
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

A Global Analysis of the Primal-Dual Method for Pliable Families
di: Bansal, Ishan
Pubblicazione: (2023)

Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity
di: Bansal, Ishan, et al.
Pubblicazione: (2024)

An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding
di: Ibrahimpur, Sharat, et al.
Pubblicazione: (2025)

A $5$-Approximation Analysis for the Cover Small Cuts Problem
di: Simmons, Miles, et al.
Pubblicazione: (2026)

A Bad Example for Jain's Iterative Rounding Theorem for the Cover Small Cuts Problem
di: Simmons, Miles, et al.
Pubblicazione: (2025)

Warehouse Problem with Multiple Vendors and Generalized Complementarity Constraints
di: Bansal, Ishan, et al.
Pubblicazione: (2024)

Bounding the Optimal Performance of Online Randomized Primal-Dual Methods
di: Xu, Pan
Pubblicazione: (2025)

Network Design on Undirected Series-Parallel Graphs
di: Bansal, Ishan, et al.
Pubblicazione: (2024)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
di: Bansal, Nikhil, et al.
Pubblicazione: (2026)

Generalized Cuts and Grothendieck Covers: a Primal-Dual Approximation Framework Extending the Goemans--Williamson Algorithm
di: Proença, Nathan Benedetto, et al.
Pubblicazione: (2024)

Improved Additive Approximation Algorithms for APSP
di: Jin, Ce, et al.
Pubblicazione: (2025)

Improved Approximation Algorithms for Three-Dimensional Knapsack
di: Jansen, Klaus, et al.
Pubblicazione: (2025)

Improved Approximation Algorithm for Maximum Balanced Biclique
di: Manurangsi, Pasin
Pubblicazione: (2026)

An Improved Approximation Algorithm for Metric Triangle Packing
di: Zhao, Jingyang, et al.
Pubblicazione: (2024)

On Approximating Cutwidth and Pathwidth
di: Bansal, Nikhil, et al.
Pubblicazione: (2023)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
di: Zhao, Jingyang, et al.
Pubblicazione: (2025)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
di: Armbruster, Alexander, et al.
Pubblicazione: (2026)

Formal Primal-Dual Algorithm Analysis
di: Abdulaziz, Mohammad, et al.
Pubblicazione: (2026)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
di: Zhao, Jingyang, et al.
Pubblicazione: (2022)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
di: Zhao, Jingyang, et al.
Pubblicazione: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
di: Fan, Chenglin, et al.
Pubblicazione: (2025)

Optimal 4-Approximation for the Correlated Pandora's Problem
di: Bansal, Nikhil, et al.
Pubblicazione: (2025)

Improved Approximation Algorithms for Relational Clustering
di: Esmailpour, Aryan, et al.
Pubblicazione: (2024)

Improved Approximation for Ranking on General Graphs
di: Derakhshan, Mahsa, et al.
Pubblicazione: (2025)

Extracting Dual Solutions via Primal Optimizers
di: Carmon, Yair, et al.
Pubblicazione: (2024)

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
di: Zhao, Jingyang, et al.
Pubblicazione: (2026)

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
di: Yamano, Ryosuke, et al.
Pubblicazione: (2026)

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion
di: McCauley, Samuel
Pubblicazione: (2024)

Improved Approximation Algorithms for Index Coding
di: Chawin, Dror, et al.
Pubblicazione: (2024)

The Impact of Approximation on Algorithmic Progress
di: Li, Jeffery, et al.
Pubblicazione: (2026)

Going Beyond Surfaces in Diameter Approximation
di: Włodarczyk, Michał
Pubblicazione: (2025)

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
di: Bhangale, Amey, et al.
Pubblicazione: (2026)

Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
di: Gupta, Sushmita, et al.
Pubblicazione: (2024)

Approximation Algorithms for Steiner Connectivity Augmentation
di: Hathcock, Daniel, et al.
Pubblicazione: (2023)

Approximation Algorithms for Fair Repetitive Scheduling
di: Hermelin, Danny, et al.
Pubblicazione: (2025)

Approximation Algorithms for Digraph Width Parameters
di: Kintali, Shiva, et al.
Pubblicazione: (2011)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
di: Alipour, Sharareh, et al.
Pubblicazione: (2025)

Improved Approximations for Flexible Network Design
di: Hyatt-Denesik, Dylan, et al.
Pubblicazione: (2024)

Hardness and Approximation Algorithms for Balanced Districting Problems
di: Dharangutte, Prathamesh, et al.
Pubblicazione: (2025)