Cover Image

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gupta, Anupam, Kaplan, Haim, Lindermayr, Alexander, Schlöter, Jens, Yingchareonthawornchai, Sorrachai
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Little Clairvoyance Is All You Need
by: Gupta, Anupam, et al.
Published: (2025)

Delayed-Clairvoyant Flow Time Scheduling via a Borrow Graph Analysis
by: Lindermayr, Alexander, et al.
Published: (2026)

Non-Clairvoyant Scheduling with Progress Bars
by: Benomar, Ziyad, et al.
Published: (2025)

Online Flow Time Minimization with Gradually Revealed Jobs
by: Lindermayr, Alexander, et al.
Published: (2026)

The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints
by: Jäger, Sven, et al.
Published: (2024)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
by: Fischer, Olivier, et al.
Published: (2025)

Hardness Amplification for Dynamic Binary Search Trees
by: Jiang, Shunhua, et al.
Published: (2024)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
by: Jiang, Yonggang, et al.
Published: (2025)

On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms
by: Schlöter, Jens
Published: (2025)

Accelerating Matroid Optimization through Fast Imprecise Oracles
by: Eberle, Franziska, et al.
Published: (2024)

Competitive Non-Clairvoyant KV-Cache Scheduling for LLM Inference
by: Feng, Yiding, et al.
Published: (2026)

Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling
by: Jäger, Sven, et al.
Published: (2022)

Learning-Augmented Online Scheduling with Parsimonious Preemption
by: Blue, Mugen, et al.
Published: (2026)

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

Polytope Scheduling with Groups: Unified Models and Optimal Guarantees
by: Lindermayr, Alexander, et al.
Published: (2025)

Improved Tree Sparsifiers in Near-Linear Time
by: Agassy, Daniel, et al.
Published: (2025)

A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
by: Hommelsheim, Felix, et al.
Published: (2025)

Two-Edge Connectivity via Pac-Man Gluing
by: Garg, Mohit, et al.
Published: (2024)

Indirect Coflow Scheduling
by: Lindermayr, Alexander, et al.
Published: (2025)

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
by: Sadeh, Yaniv, et al.
Published: (2026)

Caching Connections in Matchings
by: Sadeh, Yaniv, et al.
Published: (2023)

Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment
by: Ezra, Tomer, et al.
Published: (2024)

Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid
by: Diwan, Haya, et al.
Published: (2025)

Dynamic Edge Coloring of Forests
by: Kaplan, Haim, et al.
Published: (2026)

Search Trees on Trees via LP
by: Sadeh, Yaniv, et al.
Published: (2025)

Expander Decomposition for Non-Uniform Vertex Measures
by: Agassy, Daniel, et al.
Published: (2025)

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
by: Agassy, Daniel, et al.
Published: (2022)

Simpler Universally Optimal Dijkstra
by: van der Hoog, Ivor, et al.
Published: (2025)

Steiner Forest: A Simplified Better-Than-2 Approximation
by: Gupta, Anupam, et al.
Published: (2025)

Weighted Chairman Assignment and Flow-Time Scheduling
by: Liu, Siyue, et al.
Published: (2025)

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

Simpler and Improved Replacement Path Coverings
by: Bilò, Davide, et al.
Published: (2026)

The Online Submodular Cover Problem
by: Gupta, Anupam, et al.
Published: (2025)

Fully-Dynamic Submodular Cover with Bounded Recourse
by: Gupta, Anupam, et al.
Published: (2020)

Simpler and Faster Directed Low-Diameter Decompositions
by: Li, Jason
Published: (2025)

3SUM in Preprocessed Universes: Faster and Simpler
by: Kasliwal, Shashwat, et al.
Published: (2024)

A Learning Perspective on Random-Order Covering Problems
by: Gupta, Anupam, et al.
Published: (2025)

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)