Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Balzereit, Kaja, Grüttemeier, Niels, Morawietz, Nils, Reinhardt, Dennis, Windmann, Stefan, Wolf, Petra
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

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
von: Grüttemeier, Niels, et al.
Veröffentlicht: (2025)

Complexity of Local Search for Euclidean Clustering Problems
von: Manthey, Bodo, et al.
Veröffentlicht: (2023)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
von: Herrmann, Anton, et al.
Veröffentlicht: (2025)

Parameterized Local Search for Max $c$-Cut
von: Garvardt, Jaroslav, et al.
Veröffentlicht: (2024)

Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
von: Komusiewicz, Christian, et al.
Veröffentlicht: (2026)

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

Neighborhood-Aware Graph Labeling Problem
von: Shahverdikondori, Mohammad, et al.
Veröffentlicht: (2026)

Knapsack on Graphs with Relaxed Neighborhood Constraints
von: Dey, Palash, et al.
Veröffentlicht: (2025)

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

Single Family Algebra Operation on BDDs and ZDDs Leads To Exponential Blow-Up
von: Nakamura, Kengo, et al.
Veröffentlicht: (2024)

The Query Complexity of Local Search in Rounds on General Graphs
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
von: Maalouly, Nicolas El, et al.
Veröffentlicht: (2025)

Scheduling Problems with Constrained Rejections
von: Davies, Sami, et al.
Veröffentlicht: (2025)

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

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

Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
von: Holtgrefe, Niels, et al.
Veröffentlicht: (2026)

Scheduling on Identical Machines with Setup Time and Unknown Execution Time
von: Kawase, Yasushi, et al.
Veröffentlicht: (2025)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2026)

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

Further Explanations on "SAT Requires Exhaustive Search"
von: Dong, Qingxiu, et al.
Veröffentlicht: (2024)

Clustering with Locally Bounded Ignorance
von: Garvardt, Jaroslav, et al.
Veröffentlicht: (2026)

Local Enumeration: The Not-All-Equal Case
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2026)

Near-Optimality for Single-Source Personalized PageRank
von: Jiang, Xinpeng, et al.
Veröffentlicht: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Emit As You Go: Enumerating Edges of a Spanning Tree
von: Casel, Katrin, et al.
Veröffentlicht: (2025)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
von: Dvořák, Pavel, et al.
Veröffentlicht: (2022)

Finding One Local Optimum Is Easy -- but What About Two?
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2025)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
von: Michel, Lukas, et al.
Veröffentlicht: (2023)

The Days On Days Off Scheduling Problem
von: Nießen, Fabien, et al.
Veröffentlicht: (2024)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
von: Moroie, Gregory
Veröffentlicht: (2025)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
von: Sajith, Thejas Radhika
Veröffentlicht: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
von: Chmel, Petr, et al.
Veröffentlicht: (2026)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
von: Kim, Eun Jung, et al.
Veröffentlicht: (2022)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
von: Asadi, Vahid R., et al.
Veröffentlicht: (2026)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
von: Buhrman, Harry, et al.
Veröffentlicht: (2025)

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

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

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
von: Arvind, V., et al.
Veröffentlicht: (2023)