Buchumschlag

A simpler QPTAS for scheduling jobs with precedence constraints

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Das, Syamantak, Wiese, Andreas
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

A QPTAS for Facility Location on Unit Disk graphs
von: Friggstad, Zachary, et al.
Veröffentlicht: (2024)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
von: Das, Syamantak, et al.
Veröffentlicht: (2024)

Online busy time scheduling with flexible jobs
von: Albers, Susanne, et al.
Veröffentlicht: (2024)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

Stochastic scheduling with Bernoulli-type jobs through policy stratification
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2025)

Faster and simpler online/sliding rightmost Lempel-Ziv factorizations
von: Sumiyoshi, Wataru, et al.
Veröffentlicht: (2024)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
von: Kolmogorov, Vladimir
Veröffentlicht: (2023)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
von: Buchem, Moritz, et al.
Veröffentlicht: (2024)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
von: Armbruster, Alexander, et al.
Veröffentlicht: (2026)

Speed-robust scheduling revisited
von: Minařík, Josef, et al.
Veröffentlicht: (2024)

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
von: Kar, Debajyoti, et al.
Veröffentlicht: (2026)

Scheduling on a Stochastic Number of Machines
von: Buchem, Moritz, et al.
Veröffentlicht: (2024)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
von: Fischer, David, et al.
Veröffentlicht: (2022)

Scheduling two types of jobs with minimum makespan
von: Cao, Song, et al.
Veröffentlicht: (2024)

Spike-and-Slab Posterior Sampling in High Dimensions
von: Kumar, Syamantak, et al.
Veröffentlicht: (2025)

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

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

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

Private Geometric Median in Nearly-Linear Time
von: Kumar, Syamantak, et al.
Veröffentlicht: (2025)

Combinatorial Sparse PCA Beyond the Spiked Identity Model
von: Kumar, Syamantak, et al.
Veröffentlicht: (2026)

A probabilistic analysis on general probabilistic scheduling problems
von: Suruga, Daiki
Veröffentlicht: (2024)

Dependent randomized rounding for clustering and partition systems with knapsack constraints
von: Harris, David G., et al.
Veröffentlicht: (2017)

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2023)

Sampling permutations satisfying constraints within the lopsided local lemma regime
von: He, Kun, et al.
Veröffentlicht: (2024)

On the Approximability of Unsplittable Flow on a Path with Time Windows
von: Armbruster, Alexander, et al.
Veröffentlicht: (2025)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
von: Das, Rathish, et al.
Veröffentlicht: (2025)

Sorting with constraints
von: Manas, A.
Veröffentlicht: (2025)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
von: Das, Debarati, et al.
Veröffentlicht: (2026)

Approximation algorithms for scheduling with rejection in green manufacturing
von: Gong, Mingyang, et al.
Veröffentlicht: (2025)

Adaptive determinantal scheduling with fairness in wireless networks
von: Keeler, H. P., et al.
Veröffentlicht: (2025)

Local Search-based Individually Fair Clustering with Outliers
von: Maity, Binita, et al.
Veröffentlicht: (2025)

Resource Leveling: Complexity of a UET two-processor scheduling variant and related problems
von: Bendotti, Pascale, et al.
Veröffentlicht: (2024)

Black-Box $k$-to-$1$-PCA Reductions: Theory and Applications
von: Jambulapati, Arun, et al.
Veröffentlicht: (2024)

Multiplicative assignment with upgrades
von: Armbruster, Alexander, et al.
Veröffentlicht: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
von: Kalavas, Andreas, et al.
Veröffentlicht: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
von: Kalavas, Andreas, et al.
Veröffentlicht: (2025)

Fitting Tree Metrics and Ultrametrics in Data Streams
von: Carmel, Amir, et al.
Veröffentlicht: (2025)

A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
von: Saller, Sophia, et al.
Veröffentlicht: (2023)

Counting Small Balanced (p,q)-bicliques in Signed Bipartite Graphs
von: Kiran, Mekala, et al.
Veröffentlicht: (2026)