Buchumschlag

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Brinkop, Hauke, 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

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

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

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

New Approximation Guarantees for The Economic Warehouse Lot Scheduling Problem
von: Segev, Danny
Veröffentlicht: (2024)

New Approximation Guarantees for The Inventory Staggering Problem
von: Alon, Noga, et al.
Veröffentlicht: (2025)

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

Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
von: Heeger, Klaus, et al.
Veröffentlicht: (2024)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
von: Jansen, Klaus, 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)

Improved Approximation Guarantees and Hardness Results for MNL-Driven Product Ranking
von: Segev, Danny, et al.
Veröffentlicht: (2025)

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

Non-Splitting Coflow Scheduling with Provable Guarantees in Heterogeneous Parallel Networks
von: Chen, Chi-Yeh
Veröffentlicht: (2025)

Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
von: Zhao, Jingyang, et al.
Veröffentlicht: (2023)

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

Scheduling on a Stochastic Number of Machines
von: Buchem, Moritz, et al.
Veröffentlicht: (2024)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
von: Łącki, Jakub, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Network Design in Non-Uniform Fault Models
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Approximating Single-Source Personalized PageRank with Absolute Error Guarantees
von: Wei, Zhewei, et al.
Veröffentlicht: (2024)

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)

Polylogarithmic Approximation for Robust s-t Path
von: Li, Shi, et al.
Veröffentlicht: (2023)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
von: Rohwedder, Lars
Veröffentlicht: (2025)

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

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

Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-Uniform k-Center
von: Blauth, Jannis, et al.
Veröffentlicht: (2025)

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

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
von: Li, Shi
Veröffentlicht: (2024)

Approximate Cartesian Tree Matching: an Approach Using Swaps
von: Auvray, Bastien, et al.
Veröffentlicht: (2023)

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

Dynamic Spectral Clustering with Provable Approximation Guarantee
von: Laenen, Steinar, 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)

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
von: Yamano, Ryosuke, et al.
Veröffentlicht: (2026)

New Convex Programming Technique for Nash Social Welfare and Scheduling
von: Feng, Yuda, et al.
Veröffentlicht: (2026)

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

Improved Approximation Guarantees for Joint Replenishment in Continuous Time
von: Segev, Danny
Veröffentlicht: (2024)

Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
von: Chen, Tianqi, et al.
Veröffentlicht: (2025)

Tight Bounds for Online Scheduling in the One-Fast-Many-Slow Machines Setting
von: Jeang, John, et al.
Veröffentlicht: (2026)

New Algorithms and Hardness Results for Connected Clustering
von: Eube, Jan, et al.
Veröffentlicht: (2025)