Cover Image

A Simple Approximation Algorithm for Optimal Decision Tree

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zhuo, Zhengjia, Nagarajan, Viswanath
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Semi-Bandit Learning for Monotone Stochastic Optimization
by: Agarwal, Arpit, et al.
Published: (2023)

Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
by: Harris, Blake, et al.
Published: (2024)

Minimum Cost Adaptive Submodular Cover
by: Al-Thani, Hessa, et al.
Published: (2022)

Identifying Approximate Minimizers under Stochastic Uncertainty
by: Al-Thani, Hessa, et al.
Published: (2025)

Distributionally Robust $k$-of-$n$ Sequential Testing
by: Tan, Rayen, et al.
Published: (2026)

Approximation Algorithms for D-optimal Design
by: Singh, Mohit, et al.
Published: (2018)

Approximation Algorithms for Combinatorial Optimization with Predictions
by: Antoniadis, Antonios, et al.
Published: (2024)

An Approximation Algorithm for Graph Label Selection
by: John, Josia, et al.
Published: (2026)

Near-Optimal Algorithms for Omniprediction
by: Okoroafor, Princewill, et al.
Published: (2025)

Optimal Approximate Matrix Multiplication over Sliding Windows
by: Yao, Ziqi, et al.
Published: (2025)

Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions
by: Epasto, Alessandro, et al.
Published: (2020)

A Faster $k$-means++ Algorithm
by: Liang, Jiehao, et al.
Published: (2022)

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

Constant-Factor Approximation for the Uniform Decision Tree
by: Szyfelbein, Michał
Published: (2026)

Sequential Testing with Subadditive Costs
by: Harris, Blake, et al.
Published: (2025)

Optimal Algorithms for Augmented Testing of Discrete Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2024)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
by: Hayderi, Alexandre, et al.
Published: (2024)

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2026)

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

Sublinear Time Algorithm for Online Weighted Bipartite Matching
by: Hu, Hang, et al.
Published: (2022)

Approximately Optimal Core Shapes for Tensor Decompositions
by: Ghadiri, Mehrdad, et al.
Published: (2023)

Precedence-Constrained Decision Trees and Coverings
by: Szyfelbein, Michał, et al.
Published: (2026)

Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret
by: Harada, Tsubasa, et al.
Published: (2025)

On Computing Optimal Tree Ensembles
by: Komusiewicz, Christian, et al.
Published: (2023)

Learning Small Decision Trees with Few Outliers: A Parameterized Perspective
by: Gahlawat, Harmender, et al.
Published: (2025)

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
by: Veldt, Nate, et al.
Published: (2025)

Active Learning with Simple Questions
by: Kontonis, Vasilis, et al.
Published: (2024)

Are Graph Neural Networks Optimal Approximation Algorithms?
by: Yau, Morris, et al.
Published: (2023)

Fast and Simple Densest Subgraph with Predictions
by: Bui, Thai, et al.
Published: (2025)

A Simple Sparse Matrix Vector Multiplication Approach to Padded Convolution
by: Chaudhry, Zan
Published: (2024)

Exact and Approximate Algorithms for Polytree Learning
by: Harviainen, Juha, et al.
Published: (2026)

A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
by: Grigorescu, Elena, et al.
Published: (2024)

Simple KNN-Based Outlier Detection Achieves Robust Clustering
by: Jiang, Tianle, et al.
Published: (2026)

Sublinear Time Quantum Algorithm for Attention Approximation
by: Song, Zhao, et al.
Published: (2026)

Efficient Calibration for Decision Making
by: Gopalan, Parikshit, et al.
Published: (2025)

Smooth Calibration and Decision Making
by: Hartline, Jason, et al.
Published: (2025)

Calibration Error for Decision Making
by: Hu, Lunjia, et al.
Published: (2024)

A Faster Generalized Two-Stage Approximate Top-K
by: Samaga, Yashas, et al.
Published: (2025)

Guessing Efficiently for Constrained Subspace Approximation
by: Bhaskara, Aditya, et al.
Published: (2025)

The Space Complexity of Approximating Logistic Loss
by: Dexter, Gregory, et al.
Published: (2024)