Cover Image

Optimal 4-Approximation for the Correlated Pandora's Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bansal, Nikhil, Huang, Zhiyi, Zhu, Zixuan
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

On Approximating Cutwidth and Pathwidth
by: Bansal, Nikhil, et al.
Published: (2023)

Expander Decomposition with Almost Optimal Overhead
by: Bansal, Nikhil, et al.
Published: (2026)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
by: Bansal, Nikhil, et al.
Published: (2026)

Pandora with Inaccurate Priors
by: Banihashem, Kiarash, et al.
Published: (2025)

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

Optimal Stopping with a Predicted Prior
by: Bai, Tian, et al.
Published: (2025)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
by: Mallek, Nadym, et al.
Published: (2025)

Laminar Matroid Secretary: Greedy Strikes Back
by: Huang, Zhiyi, et al.
Published: (2023)

Pandora's Problem with Combinatorial Cost
by: Berger, Ben, et al.
Published: (2023)

Warehouse Problem with Multiple Vendors and Generalized Complementarity Constraints
by: Bansal, Ishan, et al.
Published: (2024)

Robust Max Selection
by: Dang, Trung, et al.
Published: (2024)

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

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

An Approximate Generalization of the Okamura-Seymour Theorem
by: Kumar, Nikhil
Published: (2022)

Improved Combinatorial Approximations for Weighted Correlation Clustering
by: Ostovari, Mojtaba, et al.
Published: (2023)

An Improved Bound for the Beck-Fiala Conjecture
by: Bansal, Nikhil, et al.
Published: (2025)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
by: Zhou, Jianqi, et al.
Published: (2025)

A $\frac{4}{3}$-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs
by: Neuwohner, Meike
Published: (2024)

Pandora's Box Problem With Time Constraints
by: Amanatidis, Georgios, et al.
Published: (2024)

Optimal FPT-Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2026)

New Approximation Guarantees for The Inventory Staggering Problem
by: Alon, Noga, et al.
Published: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
by: Neuwohner, Meike, et al.
Published: (2025)

Improved Approximations for Dial-a-Ride Problems
by: Zhao, Jingyang, et al.
Published: (2026)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
by: Antoniadis, Antonios, et al.
Published: (2020)

3/2-Approximation for the Forest Augmentation Problem
by: Çivril, Ali
Published: (2024)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
by: Fan, Chenglin, et al.
Published: (2025)

Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering
by: Cao, Nairen, et al.
Published: (2024)

Online Matching: A Brief Survey
by: Huang, Zhiyi, et al.
Published: (2024)

Stochastic Online Correlated Selection
by: Chen, Ziyun, et al.
Published: (2024)

Optimal Approximate Matrix Multiplication over Sliding Window
by: Xian, Haoming, et al.
Published: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
by: Chen, Yong, et al.
Published: (2025)

Enhanced Approximation Algorithms for the Capacitated Location Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

A Global Analysis of the Primal-Dual Method for Pliable Families
by: Bansal, Ishan
Published: (2023)

Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
by: Chen, Tianqi, et al.
Published: (2025)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

Edge-weighted Matching in the Dark
by: Huang, Zhiyi, et al.
Published: (2025)