Buchumschlag

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Fischer, Nick, Wennmann, Leo
Format:	Preprint
Veröffentlicht:	2024
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

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

Minimizing the Number of Tardy Jobs and Maximal Tardiness on a Single Machine is NP-hard
von: Heeger, Klaus, et al.
Veröffentlicht: (2024)

A Simple Algorithm for Trimmed Multipoint Evaluation
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
von: Kaul, Matthias, et al.
Veröffentlicht: (2024)

Cost Preserving Dependent Rounding for Allocation Problems
von: Rohwedder, Lars, et al.
Veröffentlicht: (2025)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
von: Stoian, Mihail
Veröffentlicht: (2024)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
von: Heeger, Klaus, et al.
Veröffentlicht: (2024)

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

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

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
von: Harada, Kaito, et al.
Veröffentlicht: (2024)

Improved Tree Sparsifiers in Near-Linear Time
von: Agassy, Daniel, et al.
Veröffentlicht: (2025)

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
von: Avila, Tatiana Rocha, et al.
Veröffentlicht: (2026)

Solving Polynomial Equations Over Finite Fields
von: Dell, Holger, et al.
Veröffentlicht: (2024)

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

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
von: Henzinger, Monika, et al.
Veröffentlicht: (2025)

Faster Minimization of Total Weighted Completion Time on Parallel Machines
von: Hermelin, Danny, et al.
Veröffentlicht: (2025)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
von: Elkin, Michael, et al.
Veröffentlicht: (2024)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
von: Driemel, Anne, et al.
Veröffentlicht: (2026)

Near-Optimal Directed Low-Diameter Decompositions
von: Bringmann, Karl, et al.
Veröffentlicht: (2025)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2022)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
von: Dhawan, Abhishek
Veröffentlicht: (2024)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
von: Hua, Kevin, et al.
Veröffentlicht: (2024)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Ortho-Radial Drawing in Near-Linear Time
von: Chang, Yi-Jun
Veröffentlicht: (2023)

Sumsets, 3SUM, Subset Sum: Now for Real!
von: Fischer, Nick
Veröffentlicht: (2024)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
von: Fischer, Nick
Veröffentlicht: (2026)

Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
von: Choromanski, Krzysztof, et al.
Veröffentlicht: (2026)

Discrepancy Minimization in Input-Sparsity Time
von: Deng, Yichuan, et al.
Veröffentlicht: (2022)

Testing Calibration in Nearly-Linear Time
von: Hu, Lunjia, et al.
Veröffentlicht: (2024)

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
von: Gu, Yuzhou, et al.
Veröffentlicht: (2023)

0-1 Knapsack in Nearly Quadratic Time
von: Jin, Ce
Veröffentlicht: (2023)

A Nearly Quadratic-Time FPTAS for Knapsack
von: Chen, Lin, et al.
Veröffentlicht: (2023)

Knapsack with Small Items in Near-Quadratic Time
von: Bringmann, Karl
Veröffentlicht: (2023)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
von: Sajith, Thejas Radhika
Veröffentlicht: (2025)

Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
von: Cabello, Sergio, et al.
Veröffentlicht: (2021)

Parameterized Linear Time Transitive Closure
von: Kritikakis, Giorgos, et al.
Veröffentlicht: (2024)

Verifying Shortest Paths in Linear Time
von: Shokry, Ahmed, et al.
Veröffentlicht: (2024)

Unbreakable Decomposition in Close-to-Linear Time
von: Anand, Aditya, et al.
Veröffentlicht: (2024)