Cover Image

A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jansen, Klaus, Ohnesorge, Felix
Format:	Preprint
Published:	2026
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 Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
by: Jansen, Klaus, et al.
Published: (2025)

The Support of Bin Packing is Exponential
by: Jansen, Klaus, et al.
Published: (2025)

A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times
by: Deppert, Max A., et al.
Published: (2025)

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee
by: Brinkop, Hauke, et al.
Published: (2025)

Structural Results for High-Multiplicity Scheduling on Uniform Machines
by: Brinkop, Hauke, et al.
Published: (2022)

Hardness and Tight Approximations of Demand Strip Packing
by: Jansen, Klaus, et al.
Published: (2024)

Approximation algorithms for Job Scheduling with reconfigurable resources
by: Bergé, Pierre, et al.
Published: (2023)

Scheduling Jobs with Work-Inefficient Parallel Solutions
by: Kuszmaul, William, et al.
Published: (2024)

Job Scheduling under Base and Additional Fees, with Applications to Mixed-Criticality Scheduling
by: Hsieh, Yi-Ting, et al.
Published: (2025)

Equivalent Instances for Scheduling and Packing Problems
by: Jansen, Klaus, et al.
Published: (2025)

The Buffer Minimization Problem for Scheduling Flow Jobs with Conflicts
by: Haas, Niklas, et al.
Published: (2025)

Improved Approximation Algorithms for Three-Dimensional Knapsack
by: Jansen, Klaus, et al.
Published: (2025)

Contiguous Graph Partitioning For Optimal Total Or Bottleneck Communication
by: Ahrens, Willow
Published: (2020)

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

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
by: Kaul, Matthias, et al.
Published: (2025)

Global Predecessor Indexing: Avoiding Binary Search in Weighted Job Scheduling
by: Joshi, Amit
Published: (2025)

Scalable Fair Influence Blocking Maximization via Approximately Monotonic Submodular Optimization
by: Fang, Qiangpeng, et al.
Published: (2026)

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

Scheduling Multi-Server Jobs is Not Easy
by: Vaze, Rahul
Published: (2024)

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

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

Approximation Algorithms for Scheduling Crowdsourcing Tasks in Mobile Social Networks
by: Chen, Chi-Yeh
Published: (2025)

An Approximation Algorithm for Monotone Submodular Cost Allocation
by: Mizutani, Ryuhei
Published: (2025)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
by: Jansen, Klaus, et al.
Published: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
by: Esmer, Barış Can, et al.
Published: (2022)

Convolution and Knapsack in Higher Dimensions
by: Grage, Kilian, et al.
Published: (2024)

Submodular Ground-Set Pruning: Monotone Tightness and a Non-Monotone Separation
by: Kuhnle, Alan
Published: (2026)

Online Monotone Metric Embeddings
by: Coester, Christian, et al.
Published: (2026)

Monotone Submodular Multiway Partition
by: Bi, Richard, et al.
Published: (2024)

Efficient and Practical Approximation Algorithms for Advertising in Content Feeds
by: Zhang, Guangyi, 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)

A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
by: Hommelsheim, Felix, et al.
Published: (2025)

Practical Parallel Algorithms for Non-Monotone Submodular Maximization
by: Cui, Shuang, et al.
Published: (2023)

Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
by: Pinto Jr, Renato Ferreira
Published: (2024)

From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation
by: Großmann, Ernestine, et al.
Published: (2025)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

New Algorithm for Combinatorial $n$-folds and Applications
by: Jansen, Klaus, et al.
Published: (2024)

FPT Algorithms using Minimal Parameters for a Generalized Version of Maximin Shares
by: Jansen, Klaus, et al.
Published: (2024)

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

Testing Monotonicity of Real-Valued Functions on DAGs
by: Yoshida, Yuichi
Published: (2026)