Cover Image

A Little Clairvoyance Is All You Need

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gupta, Anupam, Kaplan, Haim, Lindermayr, Alexander, Schlöter, Jens, Yingchareonthawornchai, Sorrachai
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

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

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)

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

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

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)

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)

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

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)

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)

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)

Faster All-Pairs Optimal Electric Car Routing
by: Dorfman, Dani, et al.
Published: (2025)

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

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

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

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

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

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

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

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

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

Learning-Augmented Online Scheduling with Parsimonious Preemption
by: Blue, Mugen, 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)

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

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

On Differentially Private Linear Algebra
by: Kaplan, Haim, et al.
Published: (2024)

Random Order Set Cover is as Easy as Offline
by: Gupta, Anupam, et al.
Published: (2021)

Pairwise-Independent Contention Resolution
by: Gupta, Anupam, et al.
Published: (2024)

Learning-Augmented Algorithms with Explicit Predictors
by: Elias, Marek, et al.
Published: (2024)

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

Why is My Route Different Today? An Algorithm for Explaining Route Selection
by: Schild, Aaron, et al.
Published: (2025)

Zero-Freeness is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region
by: Shao, Shuai, et al.
Published: (2025)

Sublinear Spectral Clustering Oracle with Little Memory
by: Shen, Ranran, et al.
Published: (2026)