Copertina

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Berg, Magnus
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Complexity Classes for Online Problems with and without Predictions
di: Berg, Magnus, et al.
Pubblicazione: (2024)

Online Bin Covering with Frequency Predictions
di: Berg, Magnus, et al.
Pubblicazione: (2024)

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

Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
di: Nikolov, Aleksandar, et al.
Pubblicazione: (2026)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
di: Madani, Amirali, et al.
Pubblicazione: (2025)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
di: Das, Rathish, et al.
Pubblicazione: (2025)

Improved Approximations for Hard Graph Problems using Predictions
di: Aamand, Anders, et al.
Pubblicazione: (2025)

Minimizing Cost Rather Than Maximizing Reward in Restless Multi-Armed Bandits
di: Witter, R. Teal, et al.
Pubblicazione: (2024)

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

Minimizing the Number of Tardy Jobs and Maximal Tardiness on a Single Machine is NP-hard
di: Heeger, Klaus, et al.
Pubblicazione: (2024)

A Note on Interdiction of Linear Minimization Problems
di: Cong, Yu, et al.
Pubblicazione: (2026)

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

Online Flow Time Minimization with Gradually Revealed Jobs
di: Lindermayr, Alexander, et al.
Pubblicazione: (2026)

The Online Submodular Assignment Problem
di: Hathcock, Daniel, et al.
Pubblicazione: (2024)

The Online Submodular Assignment Problem
di: Hathcock, Daniel, et al.
Pubblicazione: (2024)

The Online Submodular Cover Problem
di: Gupta, Anupam, et al.
Pubblicazione: (2025)

Online Knapsack Problems with Estimates
di: Balabán, Jakub, et al.
Pubblicazione: (2025)

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

Maximizing the Margin between Desirable and Undesirable Elements in a Covering Problem
di: Boileau, Sophie, et al.
Pubblicazione: (2025)

Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
di: Udwani, Rajan
Pubblicazione: (2024)

The Buffer Minimization Problem for Scheduling Flow Jobs with Conflicts
di: Haas, Niklas, et al.
Pubblicazione: (2025)

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

Learning-Augmented Online Covering Problems
di: Ameli, Afrouz Jabal, et al.
Pubblicazione: (2025)

Online Scheduling via Gradient Descent for Weighted Flow Time Minimization
di: Chen, Qingyun, et al.
Pubblicazione: (2024)

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

Online Rounding Schemes for $ k $-Rental Problems
di: Nekouyan, Hossein, et al.
Pubblicazione: (2025)

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

Maximal Covering Location Problem: A Set Coverage Approach Using Dynamic Programming
di: Samanta, Sukanya, et al.
Pubblicazione: (2025)

Near-real-time Solutions for Online String Problems
di: Köppl, Dominik, et al.
Pubblicazione: (2026)

Online Two-Stage Submodular Maximization
di: Nikolaou, Iasonas, et al.
Pubblicazione: (2025)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
di: Dhar, Anubhav, et al.
Pubblicazione: (2025)

Online Nash Welfare Maximization Without Predictions
di: Huang, Zhiyi, et al.
Pubblicazione: (2022)

Forbidden Subgraph Problems with Predictions
di: Böckenhauer, Hans-Joachim, et al.
Pubblicazione: (2025)

Time Efficient Implementation for Online $k$-server Problem on Trees
di: Khadiev, Kamil, et al.
Pubblicazione: (2024)

Optimizing Inventory Placement for a Downstream Online Matching Problem
di: Epstein, Boris, et al.
Pubblicazione: (2024)

Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs
di: Azar, Yossi, et al.
Pubblicazione: (2025)

A New Impossibility Result for Online Bipartite Matching Problems
di: Chierichetti, Flavio, et al.
Pubblicazione: (2025)

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

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
di: Ma, Will, et al.
Pubblicazione: (2019)

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
di: Dinitz, Michael, et al.
Pubblicazione: (2025)