Image de couverture de livre

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Geng, Yutong, Sun, Enze, Yang, Zonghan, Zhang, Yuhao
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Competitive Non-Clairvoyant KV-Cache Scheduling for LLM Inference
par: Feng, Yiding, et autres
Publié: (2026)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
par: Armbruster, Alexander, et autres
Publié: (2026)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
par: Das, Rathish, et autres
Publié: (2025)

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
par: Kosolobov, Dmitry
Publié: (2024)

Nearly Tight Bounds for the Online Sorting Problem
par: Azar, Yossi, et autres
Publié: (2025)

Almost Tight Bounds for Online Hypergraph Matching
par: Tröbst, Thorben, et autres
Publié: (2024)

Online Makespan Minimization: Beat LPT by Dynamic Locking
par: Wang, Zhaozi, et autres
Publié: (2023)

Online Flow Time Minimization with Gradually Revealed Jobs
par: Lindermayr, Alexander, et autres
Publié: (2026)

Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
par: Räcke, Harald, et autres
Publié: (2024)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
par: Rohwedder, Lars
Publié: (2025)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
par: Das, Syamantak, et autres
Publié: (2024)

Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum
par: Sun, Enze, et autres
Publié: (2025)

Tight Static Lower Bounds for Non-Adaptive Data Structures
par: Persiano, Giuseppe, et autres
Publié: (2020)

Differentially Private Learning of Exponential Distributions: Simple Algorithms and Tight Bounds
par: Mahpud, Bar, et autres
Publié: (2025)

Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling
par: Jäger, Sven, et autres
Publié: (2022)

Online Scheduling via Gradient Descent for Weighted Flow Time Minimization
par: Chen, Qingyun, et autres
Publié: (2024)

Tight Bounds for Online Scheduling in the One-Fast-Many-Slow Machines Setting
par: Jeang, John, et autres
Publié: (2026)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
par: Dai, Han, et autres
Publié: (2025)

Tight Sampling Bounds for Eigenvalue Approximation
par: Swartworth, William, et autres
Publié: (2024)

Tight Bounds for Classical Open Addressing
par: Bender, Michael A., et autres
Publié: (2024)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
par: Bringmann, Karl, et autres
Publié: (2026)

A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times
par: Deppert, Max A., et autres
Publié: (2025)

Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
par: Chua, Lynn, et autres
Publié: (2026)

Tight Bounds for Sorting Under Partial Information
par: van der Hoog, Ivor, et autres
Publié: (2024)

Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms
par: Ezra, Tomer, et autres
Publié: (2024)

Almost Tight Bounds for Differentially Private Densest Subgraph
par: Dinitz, Michael, et autres
Publié: (2023)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
par: Kuszmaul, William, et autres
Publié: (2024)

A Tight Bound on Localization of Electrical Flows
par: Gurel-Gurevich, Ori, et autres
Publié: (2026)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
par: Cheng, Yu, et autres
Publié: (2024)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
par: Chen, Lin, et autres
Publié: (2026)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
par: Fomin, Fedor V., et autres
Publié: (2025)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
par: Jiang, Tianle, et autres
Publié: (2024)

Tight Lower Bounds for Central String Queries in Compressed Space
par: Kempa, Dominik, et autres
Publié: (2025)

A Tight Lower Bound for Cycle Detection in Grid Graphs
par: Au, Andrew
Publié: (2026)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
par: Khanna, Sanjeev, et autres
Publié: (2024)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
par: Wlodarczyk, Michal
Publié: (2023)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
par: Bentert, Matthias, et autres
Publié: (2024)

Lower Bounds for Non-adaptive Local Computation Algorithms
par: Azarmehr, Amir, et autres
Publié: (2025)

Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
par: Chen, Tianqi, et autres
Publié: (2025)

Tight Approximation Bounds on a Simple Algorithm for Minimum Average Search Time in Trees
par: Høgemo, Svein
Publié: (2024)