Image de couverture de livre

Minimizing Makespan in Sublinear Time via Weighted Random Sampling

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Fu, Bin, Huo, Yumei, Zhao, Hairong
Format:	Preprint
Publié:	2026
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

Minimizing the Weighted Makespan with Restarts on a Single Machine
par: Amouzandeh, Aflatoun, et autres
Publié: (2025)

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

Fast Makespan Minimization via Short ILPs
par: Hermelin, Danny, et autres
Publié: (2026)

Improved Sublinear-time Moment Estimation using Weighted Sampling
par: Bhattacharya, Anup, et autres
Publié: (2025)

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

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
par: Eden, Talya, et autres
Publié: (2025)

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

Sublinear Time Algorithm for Online Weighted Bipartite Matching
par: Hu, Hang, et autres
Publié: (2022)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
par: Kapralov, Michael, et autres
Publié: (2022)

Online Makespan Scheduling under Scenarios
par: Ergen, Ekin
Publié: (2025)

Sublinear Time Quantum Sensitivity Sampling
par: Song, Zhao, et autres
Publié: (2025)

Sublinear Random Access Generators for Preferential Attachment Graphs
par: Even, Guy, et autres
Publié: (2016)

Computing String Covers in Sublinear Time
par: Radoszewski, Jakub, et autres
Publié: (2024)

On Solving Linear Systems in Sublinear Time
par: Andoni, Alexandr, et autres
Publié: (2018)

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
par: Rohwedder, Lars, et autres
Publié: (2024)

A k-swap Local Search for Makespan Scheduling
par: Rohwedder, Lars, et autres
Publié: (2024)

Solving the Correlation Cluster LP in Sublinear Time
par: Cao, Nairen, et autres
Publié: (2025)

Counting Distinct Square Substrings in Sublinear Time
par: Charalampopoulos, Panagiotis, et autres
Publié: (2025)

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

Fully Dynamic Exact Edge Connectivity in Sublinear Time
par: Goranci, Gramoz, et autres
Publié: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
par: Bernstein, Aaron, et autres
Publié: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
par: Dai, Jiangqi, et autres
Publié: (2025)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
par: Kempa, Dominik, et autres
Publié: (2024)

Sublinear Algorithms for TSP via Path Covers
par: Behnezhad, Soheil, et autres
Publié: (2023)

Approximate Butterfly Counting in Sublinear Time
par: Luo, Chi, et autres
Publié: (2026)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
par: Bishnu, Arijit, et autres
Publié: (2025)

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
par: Kwok, Tsz Chiu, et autres
Publié: (2025)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
par: Bille, Philip, et autres
Publié: (2022)

Training Overparametrized Neural Networks in Sublinear Time
par: Deng, Yichuan, et autres
Publié: (2022)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
par: Goranci, Gramoz, et autres
Publié: (2025)

Faster Minimization of Total Weighted Completion Time on Parallel Machines
par: Hermelin, Danny, et autres
Publié: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
par: Mahabadi, Sepideh, et autres
Publié: (2025)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
par: Bhattacharya, Sayan, et autres
Publié: (2023)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
par: Mahabadi, Sepideh, et autres
Publié: (2024)

Almost-Optimal Sublinear Additive Spanners
par: Tan, Zihan, et autres
Publié: (2023)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
par: Shah, Vihan
Publié: (2026)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
par: Mahabadi, Sepideh, et autres
Publié: (2025)

Sublinear Spectral Clustering Oracle with Little Memory
par: Shen, Ranran, et autres
Publié: (2026)

Simple and Optimal Sublinear Algorithms for Mean Estimation
par: Bertolotti, Beatrice, et autres
Publié: (2024)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
par: He, Jialin, et autres
Publié: (2025)