Cover Image

Faster Minimization of Total Weighted Completion Time on Parallel Machines

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hermelin, Danny, Koana, Tomohiro, Shabtay, Dvir
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

Lawler-Moore Speedups via Additive Combinatorics
by: Bringmann, Karl, et al.
Published: (2026)

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

Approximation Algorithms for Fair Repetitive Scheduling
by: Hermelin, Danny, et al.
Published: (2025)

Minimizing the Number of Tardy Jobs and Maximal Tardiness on a Single Machine is NP-hard
by: Heeger, Klaus, et al.
Published: (2024)

Robust Permutation Flowshops Under Budgeted Uncertainty
by: Goldberg, Noam, et al.
Published: (2026)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

Fairness in Repetitive Scheduling
by: Hermelin, Danny, et al.
Published: (2021)

Fair Repetitive Interval Scheduling
by: Heeger, Klaus, et al.
Published: (2024)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
by: Heeger, Klaus, et al.
Published: (2024)

Faster algorithms on linear delta-matroids
by: Koana, Tomohiro, et al.
Published: (2024)

A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor
by: Groenland, Carla, et al.
Published: (2024)

FPT algorithms over linear delta-matroids with applications
by: Eiben, Eduard, et al.
Published: (2025)

Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
by: Goldmann, Lito, et al.
Published: (2023)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

Determinantal Sieving
by: Eiben, Eduard, et al.
Published: (2023)

Graph Coloring Below Guarantees via Co-Triangle Packing
by: Akmal, Shyan, et al.
Published: (2025)

New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph
by: Ameli, Afrouz Jabal, et al.
Published: (2026)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
by: Koana, Tomohiro, et al.
Published: (2024)

Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
by: Heeger, Klaus, et al.
Published: (2024)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
by: Björklund, Andreas, et al.
Published: (2025)

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
by: Li, Shi
Published: (2024)

Total Completion Time Scheduling Under Scenarios
by: Bosman, Thomas, et al.
Published: (2024)

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

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

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

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
by: Nogler, Jakob, et al.
Published: (2024)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
by: Kwok, Shawxing
Published: (2025)

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
by: Li, Jason, et al.
Published: (2025)

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

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
by: Fischer, Nick, et al.
Published: (2024)

Greedy Completion for Weighted $(α,β)$-Spanners
by: Tzalik, Elad
Published: (2026)

Node-Weighted Triangles: Faster and Simpler
by: Akmal, Shyan, et al.
Published: (2026)

Min-Sum Set Cover on Parallel Machines
by: Szyfelbein, Michał
Published: (2026)

List Update with Delays or Time Windows
by: Azar, Yossi, et al.
Published: (2023)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
by: Boneh, Itai, et al.
Published: (2025)

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

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

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2024)

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

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
by: Kobayashi, Yasuaki, et al.
Published: (2020)