Cover Image

Fast Makespan Minimization via Short ILPs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hermelin, Danny, Shabtay, Dvir
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

Faster Minimization of Total Weighted Completion Time on Parallel Machines
by: Hermelin, Danny, et al.
Published: (2025)

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

Discrepancy Minimization via Regularization
by: Pesenti, Lucas, et al.
Published: (2022)

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

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

Parameterized Complexity of Submodular Minimization under Uncertainty
by: Kakimura, Naonori, et al.
Published: (2024)

A Unified Approach to Minimizing Symmetric Submodular Functions
by: Iwata, Satoru, et al.
Published: (2026)

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

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
by: Veldt, Nate
Published: (2025)

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
by: Jordon, Addie, et al.
Published: (2025)

Fast approximation algorithms for the 1-median problem on real-world large graphs
by: Ueta, Keisuke, et al.
Published: (2025)

Online Coloring of Short Intervals
by: Chybowska-Sokół, Joanna, et al.
Published: (2018)

Constructive l2-Discrepancy Minimization with Additive Deviations
by: Dutta, Kunal
Published: (2025)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

Cutwidth Bounds via Vertex Partitions
by: Amarilli, Antoine, et al.
Published: (2025)

Bounding $\varepsilon$-scatter dimension via metric sparsity
by: Bourneuf, Romain, et al.
Published: (2024)

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

Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
by: Efthymiou, Charilaos, et al.
Published: (2023)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
by: German, Samuel
Published: (2026)

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
by: Brubach, Brian, et al.
Published: (2021)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
by: Dutta, Kunal, et al.
Published: (2026)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
by: Shakeri, Heman, et al.
Published: (2025)

Online Graph Balancing and the Power of Two Choices
by: Bansal, Nikhil, et al.
Published: (2026)

Optimal Enumeration of Eulerian Trails in Directed Graphs
by: Bals, Ben, et al.
Published: (2026)

Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
by: Komusiewicz, Christian, et al.
Published: (2026)

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
by: Abbasi, Ali, et al.
Published: (2026)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
by: Foucaud, Florent, et al.
Published: (2026)

Fanciful Figurines flip Free Flood-It -- Polynomial-Time Miniature Painting on Co-gem-free Graphs
by: Rosenke, Christian, et al.
Published: (2026)

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

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
by: Dahan, Anatole, et al.
Published: (2026)

All ascents exponential from valued constraint graphs of pathwidth three
by: Kaznatcheev, Artem, et al.
Published: (2026)

Layer-Based Width for PAFP
by: German, Samuel
Published: (2026)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
by: Arndt, Stephen, et al.
Published: (2026)

Polynomial Kernels for Spanning Tree with Diversity Requirements
by: Golovach, Petr A., et al.
Published: (2026)

Placing Green Bridges Optimally for Robust Habitat Reconnection
by: Ellmies, Gero, et al.
Published: (2026)