Cover Image

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Armbruster, Alexander, Rohwedder, Lars, Wiese, Andreas
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Multiplicative assignment with upgrades
by: Armbruster, Alexander, et al.
Published: (2025)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
by: Rohwedder, Lars
Published: (2025)

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

A simpler QPTAS for scheduling jobs with precedence constraints
by: Das, Syamantak, et al.
Published: (2025)

Space-Efficient Algorithm for Integer Programming with Few Constraints
by: Rohwedder, Lars, et al.
Published: (2024)

A k-swap Local Search for Makespan Scheduling
by: Rohwedder, Lars, et al.
Published: (2024)

Randomized Rounding over Dynamic Programs
by: Bamas, Etienne, et al.
Published: (2025)

Cost Preserving Dependent Rounding for Allocation Problems
by: Rohwedder, Lars, et al.
Published: (2025)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
by: Eisenbrand, Friedrich, et al.
Published: (2024)

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
by: Rohwedder, Lars, et al.
Published: (2024)

The Submodular Santa Claus Problem
by: Bamas, Etienne, et al.
Published: (2024)

3.415-Approximation for Coflow Scheduling via Iterated Rounding
by: Rohwedder, Lars, et al.
Published: (2025)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations
by: Zlokapa, Alexander
Published: (2026)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
by: Nielsen, Mads Anker, et al.
Published: (2025)

On the Approximability of Unsplittable Flow on a Path with Time Windows
by: Armbruster, Alexander, et al.
Published: (2025)

Efficient $\varepsilon$-approximate minimum-entropy couplings
by: Compton, Spencer
Published: (2025)

A probabilistic analysis on general probabilistic scheduling problems
by: Suruga, Daiki
Published: (2024)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
by: Gupta, Anupam, et al.
Published: (2026)

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
by: Avila, Tatiana Rocha, et al.
Published: (2026)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
by: Fischer, David, et al.
Published: (2022)

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

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
by: Veldt, Nate
Published: (2025)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
by: Buchem, Moritz, et al.
Published: (2024)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
by: Eden, Talya, et al.
Published: (2025)

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

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

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

A 0.8395-approximation algorithm for the EPR problem
by: Apte, Anuj, et al.
Published: (2025)

Size Minimization For Multi-Output AND-Functions
by: Armbruster, Susanne
Published: (2024)

Online busy time scheduling with flexible jobs
by: Albers, Susanne, et al.
Published: (2024)

Improved algorithms for single machine serial-batch scheduling to minimize makespan and maximum cost
by: Li, Shuguang, et al.
Published: (2025)

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

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

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

Speed-robust scheduling revisited
by: Minařík, Josef, et al.
Published: (2024)

An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
by: Nutov, Zeev
Published: (2022)

Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time
by: Harris, David G.
Published: (2023)

An overview of some single machine scheduling problems: polynomial algorithms, complexity and approximability
by: Vakhania, Nodari, et al.
Published: (2024)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)