Cover Image

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fischer, David, Golak, Julian, Mnich, Matthias
Format:	Preprint
Published:	2022
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 Survey on Graph Problems Parameterized Above and Below Guaranteed Values
by: Gutin, Gregory, et al.
Published: (2022)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
by: Armbruster, Susanne, et al.
Published: (2024)

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

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

A faster algorithm for Vertex Cover parameterized by solution size
by: Harris, David G., et al.
Published: (2022)

A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth
by: Kratsch, Stefan
Published: (2026)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

Optimizing Periodic Operations for Efficient Inland Waterway Lock Management
by: Golak, Julian, et al.
Published: (2025)

Connectivity augmentation is fixed-parameter tractable
by: Korhonen, Tuukka, et al.
Published: (2026)

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

Improved algorithms for single machine serial-batch scheduling to minimize makespan and maximum cost
by: Li, Shuguang, et al.
Published: (2025)

An algebraic interpretation of Pauli flow, leading to faster flow-finding algorithms
by: Mitosek, Piotr, et al.
Published: (2024)

Counting perfect matchings and Hamiltonian cycles faster
by: Li, Baitian
Published: (2023)

A faster algorithm for the construction of optimal factoring automata
by: Erlebach, Thomas, et al.
Published: (2024)

Engineering faster double-array Aho-Corasick automata
by: Kanda, Shunsuke, et al.
Published: (2022)

A faster heuristic for the Traveling Salesman Problem with Drone
by: Hokama, Pedro H. D. B., et al.
Published: (2024)

Downstream: efficient cross-platform algorithms for fixed-capacity stream downsampling
by: Yang, Connor, et al.
Published: (2025)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Speed-robust scheduling revisited
by: Minařík, Josef, et al.
Published: (2024)

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time
by: Harris, David G.
Published: (2023)

Approximation algorithms for scheduling with rejection in green manufacturing
by: Gong, Mingyang, et al.
Published: (2025)

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters $k$-clustering and their fair variants
by: Banerjee, Sandip, et al.
Published: (2025)

A faster algorithm for efficient longest common substring calculation for non-parametric entropy estimation in sequential data
by: Smart, Bridget, et al.
Published: (2025)

Online busy time scheduling with flexible jobs
by: Albers, Susanne, et al.
Published: (2024)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

A simpler QPTAS for scheduling jobs with precedence constraints
by: Das, Syamantak, et al.
Published: (2025)

Stochastic scheduling with Bernoulli-type jobs through policy stratification
by: Antoniadis, Antonios, et al.
Published: (2025)

Algorithms for matrix multiplication via sampling and opportunistic matrix multiplication
by: Harris, David G.
Published: (2021)

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

Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling
by: Chen, Tyler, et al.
Published: (2025)

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
by: Umans, Chris, et al.
Published: (2025)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
by: Censor-Hillel, Keren, et al.
Published: (2025)

Double Exponential Lower Bound for Telephone Broadcast
by: Tale, Prafullkumar
Published: (2024)

Fast and Practical Single-Exponential Algorithms for Branchwidth
by: Kaneda, Taiki, et al.
Published: (2026)

Enumerating models of DNF faster: breaking the dependency on the formula size
by: Capelli, Florent, et al.
Published: (2018)

Weighted $k$-Server Admits an Exponentially Competitive Algorithm
by: Bijoy, Adithya, et al.
Published: (2025)

A Single Exponential-Time FPT Algorithm for Cactus Contraction
by: Krithika, R., et al.
Published: (2025)

Real Time Proportional Throughput Maximization: How much advance notice should you give your scheduler?
by: Mottu, Nadim A.
Published: (2025)