Cover Image

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Das, Rathish, Sun, Hao
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Almost Tight Bounds for Online Hypergraph Matching
by: Tröbst, Thorben, et al.
Published: (2024)

Hardness and Tight Approximations of Demand Strip Packing
by: Jansen, Klaus, et al.
Published: (2024)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
by: Geng, Yutong, et al.
Published: (2025)

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

Tight Bounds for Online Scheduling in the One-Fast-Many-Slow Machines Setting
by: Jeang, John, et al.
Published: (2026)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)

Almost Tight Bounds for Differentially Private Densest Subgraph
by: Dinitz, Michael, et al.
Published: (2023)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
by: Khanna, Sanjeev, et al.
Published: (2024)

Automating the Search for Small Hard Examples to Approximation Algorithms
by: Sharma, Eklavya
Published: (2025)

An Empirical Study of Online Packet Scheduling Algorithms
by: Sakr, Nourhan, et al.
Published: (2016)

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
by: Eberle, Franziska, et al.
Published: (2024)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
by: Bringmann, Karl, et al.
Published: (2026)

Approximation Algorithms for Scheduling Crowdsourcing Tasks in Mobile Social Networks
by: Chen, Chi-Yeh
Published: (2025)

Approximating Optimum Online for Capacitated Resource Allocation
by: Braun, Alexander, et al.
Published: (2024)

On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
by: Albers, Susanne, et al.
Published: (2025)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Approximating Directed Connectivity in Almost-Linear Time
by: Quanrud, Kent
Published: (2025)

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
by: Yamano, Ryosuke, et al.
Published: (2026)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)

Nearly Tight Bounds for the Online Sorting Problem
by: Azar, Yossi, et al.
Published: (2025)

Online Algorithms to Schedule a Proportionate Flexible Flow Shop of Batching Machines
by: Hertrich, Christoph, et al.
Published: (2020)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
by: Gadekar, Ameet, et al.
Published: (2025)

An Improved Kernel and Parameterized Algorithm for Almost Induced Matching
by: Liu, Yuxi, et al.
Published: (2023)

Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
by: Kanellopoulos, Sotiris, et al.
Published: (2026)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

Approximations and Hardness of Packing Partially Ordered Items
by: Doron-Arad, Ilan, et al.
Published: (2024)

A Tight Competitive Ratio for Online Submodular Welfare Maximization
by: Ganz, Amit, et al.
Published: (2023)

Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
by: Räcke, Harald, et al.
Published: (2024)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
by: Das, Syamantak, et al.
Published: (2024)

Risk-Sensitive Online Algorithms
by: Christianson, Nicolas, et al.
Published: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Mömke, Tobias, et al.
Published: (2024)

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

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

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
by: Kyng, Rasmus, et al.
Published: (2025)

Differentially Private Learning of Exponential Distributions: Simple Algorithms and Tight Bounds
by: Mahpud, Bar, et al.
Published: (2025)