Buchumschlag

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Heeger, Klaus, Hermelin, Danny
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
von: Heeger, Klaus, et al.
Veröffentlicht: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
von: Stoian, Mihail
Veröffentlicht: (2024)

Halfspaces are hard to test with relative error
von: Chen, Xi, et al.
Veröffentlicht: (2025)

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
von: Kaul, Matthias, et al.
Veröffentlicht: (2024)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Faster Minimization of Total Weighted Completion Time on Parallel Machines
von: Hermelin, Danny, et al.
Veröffentlicht: (2025)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
von: Cheng, Kuan, et al.
Veröffentlicht: (2025)

Size Minimization For Multi-Output AND-Functions
von: Armbruster, Susanne
Veröffentlicht: (2024)

Bandwidth Parameterized by Cluster Vertex Deletion Number
von: Gima, Tatsuya, et al.
Veröffentlicht: (2023)

Sumplete is Hard, Even with Two Different Numbers
von: Ruangwises, Suthee
Veröffentlicht: (2023)

Asymmetric Number Partitioning with Splitting and Interval Targets
von: Bismuth, Samuel, et al.
Veröffentlicht: (2022)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
von: Liu, Wei, et al.
Veröffentlicht: (2024)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
von: Dhar, Anubhav, et al.
Veröffentlicht: (2025)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
von: Kurita, Kazuhiro, et al.
Veröffentlicht: (2025)

The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2026)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
von: Fei, Yumou
Veröffentlicht: (2025)

Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
von: Grandjean, Étienne, et al.
Veröffentlicht: (2025)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
von: Tale, Prafullkumar
Veröffentlicht: (2025)

Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches
von: Pintér, József, et al.
Veröffentlicht: (2026)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
von: Scheder, Dominik, et al.
Veröffentlicht: (2025)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

Equivalent Instances for Scheduling and Packing Problems
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

Fair Repetitive Interval Scheduling
von: Heeger, Klaus, et al.
Veröffentlicht: (2024)

Computational-Statistical Tradeoffs from NP-hardness
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

Fast decision tree learning solves hard coding-theoretic problems
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
von: Kutner, David C., et al.
Veröffentlicht: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2026)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
von: Yang, Yang
Veröffentlicht: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

Fast Makespan Minimization via Short ILPs
von: Hermelin, Danny, et al.
Veröffentlicht: (2026)

Quantum Algorithm for Lexicographically Minimal String Rotation
von: Wang, Qisheng, et al.
Veröffentlicht: (2020)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
von: Aute, Shubhada, et al.
Veröffentlicht: (2026)

Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
von: Levet, Michael, et al.
Veröffentlicht: (2025)

Can You Link Up With Treewidth?
von: Curticapean, Radu, et al.
Veröffentlicht: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

Simple approximation algorithms for Polyamorous Scheduling
von: Biktairov, Yuriy, et al.
Veröffentlicht: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
von: Stoian, Mihail
Veröffentlicht: (2024)

Cluster Editing on Cographs and Related Classes
von: Lafond, Manuel, et al.
Veröffentlicht: (2024)