Buchumschlag

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Armbruster, Alexander, Grandoni, Fabrizio, Tinguely, Antoine, Wiese, Andreas
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On the Approximability of Unsplittable Flow on a Path with Time Windows
von: Armbruster, Alexander, et al.
Veröffentlicht: (2025)

Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions
von: Grandoni, Fabrizio, et al.
Veröffentlicht: (2024)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
von: Armbruster, Alexander, et al.
Veröffentlicht: (2025)

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

An Improved Greedy Approximation for (Metric) $k$-Means
von: Charikar, Moses, et al.
Veröffentlicht: (2026)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2022)

FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters Clustering
von: Grandoni, Fabrizio, et al.
Veröffentlicht: (2026)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
von: Armbruster, Susanne, et al.
Veröffentlicht: (2024)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
von: Geng, Yutong, et al.
Veröffentlicht: (2025)

Unsplittable Flow on a Short Path
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

A Competitive Algorithm for Throughput Maximization on Identical Machines
von: Moseley, Benjamin, et al.
Veröffentlicht: (2021)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
von: Buchem, Moritz, et al.
Veröffentlicht: (2024)

A PTAS for Weighted Triangle-free 2-Matching
von: Bosch-Calvo, Miguel, et al.
Veröffentlicht: (2026)

On the Bidirected Cut Relaxation for Steiner Forest
von: Byrka, Jarosław, et al.
Veröffentlicht: (2024)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
von: Byrka, Jarosław, et al.
Veröffentlicht: (2024)

A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times
von: Deppert, Max A., et al.
Veröffentlicht: (2025)

Multiplicative assignment with upgrades
von: Armbruster, Alexander, et al.
Veröffentlicht: (2025)

Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling
von: Jäger, Sven, et al.
Veröffentlicht: (2022)

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

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
von: Cervenjak, Philip, et al.
Veröffentlicht: (2026)

Improved Algorithms for Fair Matroid Submodular Maximization
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2026)

A simpler QPTAS for scheduling jobs with precedence constraints
von: Das, Syamantak, et al.
Veröffentlicht: (2025)

Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint
von: Rui, Xiaobin, et al.
Veröffentlicht: (2025)

Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints
von: Zhu, Yanhui, et al.
Veröffentlicht: (2024)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
von: Kar, Debajyoti, et al.
Veröffentlicht: (2026)

Improved Additive Approximation Algorithms for APSP
von: Jin, Ce, et al.
Veröffentlicht: (2025)

Improved Approximation Algorithm for Maximum Balanced Biclique
von: Manurangsi, Pasin
Veröffentlicht: (2026)

Improved Approximation Algorithms for Three-Dimensional Knapsack
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

An Improved Approximation Algorithm for Metric Triangle Packing
von: Zhao, Jingyang, et al.
Veröffentlicht: (2024)

Approximation Algorithms for Budget Splitting in Multi-Channel Influence Maximization
von: Ali, Dildar, et al.
Veröffentlicht: (2026)

Improved FPT Approximation for Non-metric TSP
von: Bampis, Evripidis, et al.
Veröffentlicht: (2024)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
von: Udwani, Rajan
Veröffentlicht: (2024)

Size Minimization For Multi-Output AND-Functions
von: Armbruster, Susanne
Veröffentlicht: (2024)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
von: Zhao, Jingyang, et al.
Veröffentlicht: (2022)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
von: Fan, Chenglin, et al.
Veröffentlicht: (2025)

Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
von: Hsieh, Wen-Han, et al.
Veröffentlicht: (2026)

Improved Approximation Algorithms for Relational Clustering
von: Esmailpour, Aryan, et al.
Veröffentlicht: (2024)