An Optimal Algorithm for Stochastic Vertex Cover

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Brand, Jan van den, Gørtz, Inge Li, Pabbaraju, Chirag, Panigrahi, Debmalya, Stein, Clifford, Stouras, Miltiadis, Svensson, Ola, Vakilian, Ali
Format:	Preprint
Publié:	2026
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

New and Improved Bounds for Markov Paging
par: Pabbaraju, Chirag, et autres
Publié: (2025)

Retriever Portfolios: A Principled Approach to Adaptive RAG
par: Stouras, Miltiadis, et autres
Publié: (2026)

Data-Driven Solution Portfolios
par: Drygala, Marina, et autres
Publié: (2024)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
par: Bhattacharya, Sayan, et autres
Publié: (2025)

A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses
par: Pabbaraju, Chirag, et autres
Publié: (2025)

Online Two-Stage Submodular Maximization
par: Nikolaou, Iasonas, et autres
Publié: (2025)

A Characterization of List Regression
par: Pabbaraju, Chirag, et autres
Publié: (2024)

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics
par: Charikar, Moses, et autres
Publié: (2023)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
par: Dong, Yinhao, et autres
Publié: (2024)

Nearly Tight Bounds for the Online Sorting Problem
par: Azar, Yossi, et autres
Publié: (2025)

Streaming Algorithms for Network Design
par: Chekuri, Chandra, et autres
Publié: (2025)

Streaming Algorithms for Connectivity Augmentation
par: Jin, Ce, et autres
Publié: (2024)

Hypergraph Unreliability in Quasi-Polynomial Time
par: Cen, Ruoxu, et autres
Publié: (2024)

Network Unreliability in Almost-Linear Time
par: Cen, Ruoxu, et autres
Publié: (2025)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
par: Mahabadi, Sepideh, et autres
Publié: (2024)

Exploring Facets of Language Generation in the Limit
par: Charikar, Moses, et autres
Publié: (2024)

Pareto-optimal Non-uniform Language Generation
par: Charikar, Moses, et autres
Publié: (2025)

Fast Algorithms for Graph Arboricity and Related Problems
par: Cen, Ruoxu, et autres
Publié: (2025)

Lower Bounds for Greedy Teaching Set Constructions
par: Compton, Spencer, et autres
Publié: (2025)

Learning with Monotone Adversarial Corruptions
par: Larsen, Kasper Green, et autres
Publié: (2026)

Learning-Augmented Algorithms for $k$-median via Online Learning
par: Hebbar, Anish, et autres
Publié: (2026)

Succinct Data Structures for Segments
par: Bille, Philip, et autres
Publié: (2024)

Improved Extended Regular Expression Matching
par: Bille, Philip, et autres
Publié: (2025)

Fast Practical Compression of Deterministic Finite Automata
par: Bille, Philip, et autres
Publié: (2023)

String Indexing with Compressed Patterns
par: Bille, Philip, et autres
Publié: (2019)

Differentially Private Substring and Document Counting with Near-Optimal Error
par: Bernardini, Giulia, et autres
Publié: (2024)

Parameterized Algorithms for Minimum Sum Vertex Cover
par: Aute, Shubhada, et autres
Publié: (2024)

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
par: Akhtar, Sheikh Shakil, et autres
Publié: (2025)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
par: Garg, Sumegha, et autres
Publié: (2026)

Computing Flows in Subquadratic Space
par: Brand, Jan van den, et autres
Publié: (2026)

Language Generation in the Limit: Noise, Loss, and Feedback
par: Bai, Yannan, et autres
Publié: (2025)

Scalable Algorithms for Individual Preference Stable Clustering
par: Mosenzon, Ron, et autres
Publié: (2024)

Dynamic Range Minimum Queries on the Ultra-Wide Word RAM
par: Bille, Philip, et autres
Publié: (2024)

Dynamic Rank, Basis, and Matching
par: Brand, Jan van den, et autres
Publié: (2026)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
par: Lee, Euiwoong, et autres
Publié: (2024)

A Characterization of List Language Identification in the Limit
par: Charikar, Moses, et autres
Publié: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Enumeration kernels for Vertex Cover and Feedback Vertex Set
par: Bougeret, Marin, et autres
Publié: (2025)

Compressed Dictionary Matching on Run-Length Encoded Strings
par: Bille, Philip, et autres
Publié: (2025)

Max-Cut with Multiple Cardinality Constraints
par: Makarychev, Yury, et autres
Publié: (2025)