Buchumschlag

Bounding the Optimal Performance of Online Randomized Primal-Dual Methods

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Xu, Pan
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 Global Analysis of the Primal-Dual Method for Pliable Families
von: Bansal, Ishan
Veröffentlicht: (2023)

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions
von: Bansal, Ishan, et al.
Veröffentlicht: (2022)

Nearly Optimal Bounds for Stochastic Online Sorting
von: Hu, Yang
Veröffentlicht: (2025)

Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis
von: Peng, Bo, et al.
Veröffentlicht: (2025)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
von: De, Rajat, et al.
Veröffentlicht: (2025)

Extracting Dual Solutions via Primal Optimizers
von: Carmon, Yair, et al.
Veröffentlicht: (2024)

Online Matching under KIID: Enhanced Competitive Analysis through Ordinary Differential Equation Systems
von: Xu, Pan
Veröffentlicht: (2025)

A Subquadratic Bound for Online Bisection
von: Bienkowski, Marcin, et al.
Veröffentlicht: (2023)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
von: Kothari, Pravesh, et al.
Veröffentlicht: (2024)

Competitive Analysis of Online Facility Assignment Algorithms on Discrete Grid Graphs: Performance Bounds and Remediation Strategies
von: Alif, Lamya, et al.
Veröffentlicht: (2026)

Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems
von: Kevi, Eniko, et al.
Veröffentlicht: (2024)

Nearly Tight Bounds for the Online Sorting Problem
von: Azar, Yossi, et al.
Veröffentlicht: (2025)

Almost Tight Bounds for Online Hypergraph Matching
von: Tröbst, Thorben, et al.
Veröffentlicht: (2024)

Online Algorithms with Randomly Infused Advice
von: Emek, Yuval, et al.
Veröffentlicht: (2023)

Online Matching in Geometric Random Graphs
von: Sentenac, Flore, et al.
Veröffentlicht: (2023)

An Optimal Density Bound for Discretized Point Patrolling
von: Mishra, Ahan
Veröffentlicht: (2025)

Online Disjoint Set Covers: Randomization is not Necessary
von: Bienkowski, Marcin, et al.
Veröffentlicht: (2024)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
von: Gribelyuk, Elena, et al.
Veröffentlicht: (2025)

Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
von: Räcke, Harald, et al.
Veröffentlicht: (2024)

Optimal Learning-Augmented Algorithm for Online Bidding
von: Lee, Changyeol, et al.
Veröffentlicht: (2026)

Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching
von: Ma, Will
Veröffentlicht: (2024)

An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle
von: Caporrella, Matteo, et al.
Veröffentlicht: (2026)

Optimal Bounds for Distinct Quartics
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2024)

The Primal Pathwidth SETH
von: Lampis, Michael
Veröffentlicht: (2024)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
von: Geng, Yutong, et al.
Veröffentlicht: (2025)

Near-Optimal Bayesian Online Assortment of Reusable Resources
von: Feng, Yiding, et al.
Veröffentlicht: (2025)

Optimal Testing of Reed-Muller Codes with an Online Adversary
von: Kelman, Esty, et al.
Veröffentlicht: (2026)

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
von: Kumar, Akash, et al.
Veröffentlicht: (2026)

An Optimal Sorting Algorithm for Persistent Random Comparison Faults
von: Geissmann, Barbara, et al.
Veröffentlicht: (2025)

Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams
von: Ta, Hoang, et al.
Veröffentlicht: (2026)

Near Optimal Dual Fault Tolerant Distance Oracle
von: Dey, Dipan, et al.
Veröffentlicht: (2024)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
von: Huiberts, Sophie, et al.
Veröffentlicht: (2022)

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

Online Probabilistic Metric Embedding: A General Framework for Bypassing Inherent Bounds
von: Bartal, Yair, et al.
Veröffentlicht: (2024)

Optimal Smoothed Analysis of the Simplex Method
von: Bach, Eleon, et al.
Veröffentlicht: (2025)

Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources
von: Goyal, Vineet, et al.
Veröffentlicht: (2020)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
von: Gorbachev, Egor, et al.
Veröffentlicht: (2024)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
von: Bansal, Nikhil, et al.
Veröffentlicht: (2024)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
von: Black, Hadley
Veröffentlicht: (2023)