Buchumschlag

A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Deppert, Max A., Fischer, David, Jansen, Klaus
Format:	Preprint
Veröffentlicht:	2025
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

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee
von: Brinkop, Hauke, et al.
Veröffentlicht: (2025)

Structural Results for High-Multiplicity Scheduling on Uniform Machines
von: Brinkop, Hauke, et al.
Veröffentlicht: (2022)

A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling
von: Jansen, Klaus, et al.
Veröffentlicht: (2026)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
von: Gupta, Anupam, et al.
Veröffentlicht: (2026)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
von: Fischer, Manuela, et al.
Veröffentlicht: (2021)

Scheduling on Identical Machines with Setup Time and Unknown Execution Time
von: Kawase, Yasushi, 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)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
von: Armbruster, Alexander, et al.
Veröffentlicht: (2026)

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
von: Eberle, Franziska, et al.
Veröffentlicht: (2024)

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

Hardness and Tight Approximations of Demand Strip Packing
von: Jansen, Klaus, et al.
Veröffentlicht: (2024)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
von: Ahmadi, Ali, et al.
Veröffentlicht: (2025)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
von: Terao, Tatsuya
Veröffentlicht: (2024)

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

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
von: Balzereit, Kaja, et al.
Veröffentlicht: (2024)

Equivalent Instances for Scheduling and Packing Problems
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

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

Online Algorithms to Schedule a Proportionate Flexible Flow Shop of Batching Machines
von: Hertrich, Christoph, et al.
Veröffentlicht: (2020)

Approximation Algorithms for Fair Repetitive Scheduling
von: Hermelin, Danny, et al.
Veröffentlicht: (2025)

A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
von: Cambus, Mélanie, et al.
Veröffentlicht: (2022)

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

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
von: Das, Rathish, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Scheduling Crowdsourcing Tasks in Mobile Social Networks
von: Chen, Chi-Yeh
Veröffentlicht: (2025)

4/3-Approximation of Graphic TSP
von: Çivril, Ali
Veröffentlicht: (2023)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
von: Jansen, Klaus, et al.
Veröffentlicht: (2024)

Convolution and Knapsack in Higher Dimensions
von: Grage, Kilian, et al.
Veröffentlicht: (2024)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
von: Veldt, Nate
Veröffentlicht: (2025)

Weighted Chairman Assignment and Flow-Time Scheduling
von: Liu, Siyue, et al.
Veröffentlicht: (2025)

Total Completion Time Scheduling Under Scenarios
von: Bosman, Thomas, et al.
Veröffentlicht: (2024)

Online Flexible Busy Time Scheduling on Heterogeneous Machines
von: Calinescu, Gruia, et al.
Veröffentlicht: (2024)

3.415-Approximation for Coflow Scheduling via Iterated Rounding
von: Rohwedder, Lars, et al.
Veröffentlicht: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
von: Makarychev, Yury, et al.
Veröffentlicht: (2024)

Efficient $\varepsilon$-approximate minimum-entropy couplings
von: Compton, Spencer
Veröffentlicht: (2025)

Weakly Approximating Knapsack in Subquadratic Time
von: Chen, Lin, et al.
Veröffentlicht: (2025)

Approximating Partition in Near-Linear Time
von: Chen, Lin, et al.
Veröffentlicht: (2024)

The Support of Bin Packing is Exponential
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

New Algorithm for Combinatorial $n$-folds and Applications
von: Jansen, Klaus, et al.
Veröffentlicht: (2024)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
von: Jansen, Klaus, et al.
Veröffentlicht: (2024)

Batched Ranged Random Integer Generation
von: Brackett-Rozinsky, Nevin, et al.
Veröffentlicht: (2024)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
von: Fischer, Nick, et al.
Veröffentlicht: (2024)