Cover Image

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Rohwedder, Lars, Safari, Ashkan, Vredeveld, Tjark
Format:	Preprint
Published:	2024
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 k-swap Local Search for Makespan Scheduling
by: Rohwedder, Lars, et al.
Published: (2024)

ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
by: Rohwedder, Lars
Published: (2025)

Convergence and Running Time of Time-dependent Ant Colony Algorithms
by: Manthey, Bodo, et al.
Published: (2025)

3.415-Approximation for Coflow Scheduling via Iterated Rounding
by: Rohwedder, Lars, et al.
Published: (2025)

Online Makespan Scheduling under Scenarios
by: Ergen, Ekin
Published: (2025)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
by: Nielsen, Mads Anker, et al.
Published: (2025)

Space-Efficient Algorithm for Integer Programming with Few Constraints
by: Rohwedder, Lars, et al.
Published: (2024)

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
by: Eisenbrand, Friedrich, et al.
Published: (2024)

The Submodular Santa Claus Problem
by: Bamas, Etienne, et al.
Published: (2024)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)

Randomized Rounding over Dynamic Programs
by: Bamas, Etienne, et al.
Published: (2025)

Cost Preserving Dependent Rounding for Allocation Problems
by: Rohwedder, Lars, et al.
Published: (2025)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

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

Online Makespan Minimization: Beat LPT by Dynamic Locking
by: Wang, Zhaozi, et al.
Published: (2023)

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

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
by: Avila, Tatiana Rocha, et al.
Published: (2026)

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

Finite Pinwheel Scheduling: the k-Visits Problem
by: Kanellopoulos, Sotiris, et al.
Published: (2025)

Coloring Reconfiguration under Color Swapping
by: Fuchs, Janosch, et al.
Published: (2025)

Sequentially Swapping Tokens: Further on Graph Classes
by: Kiya, Hironori, et al.
Published: (2022)

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

A simple and efficient preprocessing step for convex hull problem
by: Heydari, Mohammad, et al.
Published: (2023)

Smoothed Analysis of Online Metric Problems
by: Coester, Christian, et al.
Published: (2025)

Optimal Smoothed Analysis of the Simplex Method
by: Bach, Eleon, et al.
Published: (2025)

Smoothed Analysis of Dynamic Graph Algorithms
by: Meir, Uri, et al.
Published: (2025)

Approximate Cartesian Tree Matching: an Approach Using Swaps
by: Auvray, Bastien, et al.
Published: (2023)

Settling Weighted Token Swapping up to Algorithmic Barriers
by: Wein, Nicole, et al.
Published: (2025)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
by: Balzereit, Kaja, et al.
Published: (2024)

Multiplicative assignment with upgrades
by: Armbruster, Alexander, et al.
Published: (2025)

Sparse Neighborhood Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization
by: Ma, Xinran, et al.
Published: (2025)

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

Optimal Neighborhood Exploration for Dynamic Independent Sets
by: Borowitz, Jannick, et al.
Published: (2024)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
by: Antoniadis, Antonios, et al.
Published: (2020)

Stochastic Traveling Salesperson Problem with Neighborhoods for Object Detection
by: Peng, Cheng, et al.
Published: (2024)

Assigning Agents to Increase Network-Based Neighborhood Diversity
by: Qiu, Zirou, et al.
Published: (2023)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
by: Gupta, Anupam, et al.
Published: (2026)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
by: Jiang, Yonggang, et al.
Published: (2025)

Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
by: Manthey, Bodo, et al.
Published: (2023)

Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules
by: Mendoza-Cadena, Mirabel, et al.
Published: (2026)