Cover Image

Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dürr, Christoph, Merino, Arturo, Soto, José A., Verschae, José
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Randomized Binary and Tree Search under Pressure
by: Caracci, Agustín, et al.
Published: (2024)

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
by: Dürr, Anita
Published: (2022)

Scenario-Based Robust Optimization of Tree Structures
by: Angelopoulos, Spyros, et al.
Published: (2024)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
by: Adar, Tomer, et al.
Published: (2026)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
by: Shah, Vihan
Published: (2026)

Online Computation with Untrusted Advice
by: Angelopoulos, Spyros, et al.
Published: (2019)

Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy
by: Pfisterer, Kevin, et al.
Published: (2026)

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
by: Angelopoulos, Spyros, et al.
Published: (2025)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
by: Bringmann, Karl, et al.
Published: (2024)

Faster algorithms for k-Orthogonal Vectors in low dimension
by: Dürr, Anita, et al.
Published: (2025)

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

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

Finding Maximum Weight 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2025)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Scalable Private Partition Selection via Adaptive Weighting
by: Chen, Justin Y., et al.
Published: (2025)

Two Complexity Results on Spanning-Tree Congestion Problems
by: Atalig, Sunny, et al.
Published: (2026)

Logarithmic Approximations for Fair k-Set Selection
by: Li, Shi, et al.
Published: (2025)

The Two-Center Problem of Uncertain Points on Trees
by: Xu, Haitao, et al.
Published: (2024)

Computing the Center of Uncertain Points on Cactus Graphs
by: Hu, Ran, et al.
Published: (2024)

Finding the Balance Rate of Uncertain Signed Graphs
by: Wang, Zeyu, et al.
Published: (2026)

The k-Center Problem of Uncertain Points on Graphs
by: Xu, Haitao, et al.
Published: (2025)

Combinatorial Perpetual Scheduling: Existence and Computation of Low-Height Schedules
by: Mendoza-Cadena, Mirabel, et al.
Published: (2026)

Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms
by: Angelopoulos, Spyros, et al.
Published: (2024)

Chasing Small Sets Optimally Against Adaptive Adversaries
by: Coester, Christian, et al.
Published: (2026)

Computing Data Distribution from Query Selectivities
by: Agarwal, Pankaj K., et al.
Published: (2024)

The Two-Center Problem of Uncertain Points on Cactus Graphs
by: Xu, Haitao, et al.
Published: (2024)

Computing All Restricted Skyline Probabilities on Uncertain Datasets
by: Gao, Xiangyu, et al.
Published: (2023)

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
by: Großmann, Ernestine, et al.
Published: (2024)

Non-Signaling Locality Lower Bounds for Dominating Set
by: Fleming, Noah, et al.
Published: (2026)

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
by: Cohen, Edith, et al.
Published: (2024)

Noisy Computing of the Threshold Function
by: Wang, Ziao, et al.
Published: (2024)

Exact Learning of Weighted Graphs Using Composite Queries
by: Goodrich, Michael T., et al.
Published: (2025)

Free-order secretary for two-sided independence systems
by: Bérczi, Kristóf, et al.
Published: (2025)

Traversing combinatorial 0/1-polytopes via optimization
by: Merino, Arturo, et al.
Published: (2023)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Online Edge Coloring: Sharp Thresholds
by: Blikstad, Joakim, et al.
Published: (2025)

Space-Efficient Indexes for Uncertain Strings
by: Gabory, Esteban, et al.
Published: (2024)

Efficient Stochastic Routing in Path-Centric Uncertain Road Networks -- Extended Version
by: Guo, Chenjuan, et al.
Published: (2024)

Weighted Set Multi-Cover on Bounded Universe and Applications in Package Recommendation
by: Shahbazi, Nima, et al.
Published: (2026)