Imagen de Portada

The Impact of Approximation on Algorithmic Progress

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Li, Jeffery, Lynch, Jayson, Olina, Liva, Chen, Cecilia, Lucas, Andrew, Thompson, Neil
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

How fast are algorithms reducing the demands on memory? A survey of progress in space complexity
por: Rome, Hayden, et al.
Publicado: (2025)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
por: Chen, Yong, et al.
Publicado: (2025)

Slant/Gokigen Naname is NP-complete, and Some Variations are in P
por: Lynch, Jayson, et al.
Publicado: (2025)

Approximation Algorithms for Scheduling Crowdsourcing Tasks in Mobile Social Networks
por: Chen, Chi-Yeh
Publicado: (2025)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
por: Chen, Lin, et al.
Publicado: (2026)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
por: Dai, Han, et al.
Publicado: (2025)

Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint
por: Rui, Xiaobin, et al.
Publicado: (2025)

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

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

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

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

Improved Approximation Algorithm for Maximum Balanced Biclique
por: Manurangsi, Pasin
Publicado: (2026)

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

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

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

Faster Approximation Algorithms for k-Center via Data Reduction
por: Filtser, Arnold, et al.
Publicado: (2025)

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
por: Chen, Yixin, et al.
Publicado: (2025)

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

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

Efficient and Practical Approximation Algorithms for Advertising in Content Feeds
por: Zhang, Guangyi, et al.
Publicado: (2025)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
por: Soma, Tasuku, et al.
Publicado: (2025)

Faster Algorithms for Schatten-p Low Rank Approximation
por: Kacham, Praneeth, et al.
Publicado: (2024)

Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
por: Mo, Guanlin, et al.
Publicado: (2024)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
por: Zhou, Jianqi, et al.
Publicado: (2025)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
por: Zhao, Jingyang, et al.
Publicado: (2025)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
por: Zhao, Jingyang, et al.
Publicado: (2023)

Automating the Search for Small Hard Examples to Approximation Algorithms
por: Sharma, Eklavya
Publicado: (2025)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
por: Dong, Yinhao, et al.
Publicado: (2024)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
por: Zhao, Jingyang, et al.
Publicado: (2025)

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
por: Cervenjak, Philip, et al.
Publicado: (2026)

Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
por: Andoni, Alexandr, et al.
Publicado: (2026)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
por: Das, Rathish, et al.
Publicado: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
por: Cohen-Addad, Vincent, et al.
Publicado: (2025)

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

Approximation Algorithms for Network Design in Non-Uniform Fault Models
por: Chekuri, Chandra, et al.
Publicado: (2024)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
por: Zheng, Da Wei, et al.
Publicado: (2023)

Simple Algorithms for Stochastic Score Classification with Small Approximation Ratios
por: Plank, Benedikt M., et al.
Publicado: (2022)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
por: Łącki, Jakub, et al.
Publicado: (2025)

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

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
por: Ashvinkumar, Vikrant, et al.
Publicado: (2024)