Cover Image

Online Makespan Minimization: Beat LPT by Dynamic Locking

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Wang, Zhaozi, Ying, Zhiwei, Zhang, Yuhao
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Makespan Scheduling under Scenarios
by: Ergen, Ekin
Published: (2025)

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

Minimizing Makespan in Sublinear Time via Weighted Random Sampling
by: Fu, Bin, et al.
Published: (2026)

Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
by: Chen, Tianqi, et al.
Published: (2025)

Fast Makespan Minimization via Short ILPs
by: Hermelin, Danny, et al.
Published: (2026)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
by: Geng, Yutong, et al.
Published: (2025)

Minimizing the Weighted Makespan with Restarts on a Single Machine
by: Amouzandeh, Aflatoun, et al.
Published: (2025)

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

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

Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum
by: Sun, Enze, et al.
Published: (2025)

The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization
by: Huang, Zhiyi, et al.
Published: (2025)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
by: Jiang, Tianle, et al.
Published: (2024)

Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
by: Nikolov, Aleksandar, et al.
Published: (2026)

Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery using Drones
by: Chandran, L. Sunil, et al.
Published: (2024)

Beating Bellman's Algorithm for Subset Sum
by: Bringmann, Karl, et al.
Published: (2024)

On Beating $2^n$ for the Closest Vector Problem
by: Abboud, Amir, et al.
Published: (2025)

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

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions
by: Berg, Magnus
Published: (2024)

Beating Competitive Ratio 4 for Graphic Matroid Secretary
by: Banihashem, Kiarash, et al.
Published: (2025)

Minimizers in Semi-Dynamic Strings
by: Zuba, Wiktor, et al.
Published: (2025)

Online Scheduling via Gradient Descent for Weighted Flow Time Minimization
by: Chen, Qingyun, et al.
Published: (2024)

You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
by: Doron-Arad, Ilan, et al.
Published: (2024)

A Lock-free Binary Trie
by: Ko, Jeremy
Published: (2024)

Equitable Connected Partition and Structural Parameters Revisited: N-fold Beats Lenstra
by: Blažej, Václav, et al.
Published: (2024)

Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation
by: Bessa, Aline, et al.
Published: (2023)

Dynamic Pricing Algorithms for Online Set Cover
by: Bender, Max, et al.
Published: (2024)

Optimizing Periodic Operations for Efficient Inland Waterway Lock Management
by: Golak, Julian, et al.
Published: (2025)

Minimizing the Minimizers via Alphabet Reordering
by: Verbeek, Hilde, et al.
Published: (2024)

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

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
by: Liu, Yang P.
Published: (2024)

How to Balance the Load Online When Jobs and Machines Are Both Selfish?
by: Wang, Wenqian, et al.
Published: (2024)

Minimizing Total Travel Time for Collaborative Package Delivery with Heterogeneous Drones
by: Erlebach, Thomas, et al.
Published: (2026)

Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$
by: Yan, Shuyi
Published: (2022)

Discrepancy Minimization in Input-Sparsity Time
by: Deng, Yichuan, et al.
Published: (2022)

On Minimizing Wiggle in Stacked Area Charts
by: Dobler, Alexander, et al.
Published: (2025)

One-Sided Local Crossing Minimization
by: Giannopoulos, Panos, et al.
Published: (2025)

Engineering Minimal k-Perfect Hash Functions
by: Hermann, Stefan, et al.
Published: (2025)

Identifying Approximate Minimizers under Stochastic Uncertainty
by: Al-Thani, Hessa, et al.
Published: (2025)

A Note on Interdiction of Linear Minimization Problems
by: Cong, Yu, et al.
Published: (2026)

Modern Minimal Perfect Hashing: A Survey
by: Lehmann, Hans-Peter, et al.
Published: (2025)