A PAC Approach to Application-Specific Algorithm Selection

DOI10.1137/15M1050276zbMath1371.68316OpenAlexW2625599877MaRDI QIDQ5269823

Rishi Gupta, Tim Roughgarden

Publication date: 28 June 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1050276

zbMATH Keywords

online learningPAC learningalgorithm selectionparameter tuningmeta-algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) General topics in the theory of algorithms (68W01) Online algorithms; streaming algorithms (68W27)

Related Items (2)

Learning-augmented algorithms for online subset sum ⋮ Data-driven algorithm selection and tuning in optimization and signal processing

Uses Software

• SATzilla

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithm runtime prediction: methods \& evaluation
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• The weighted majority algorithm
• (Incremental) priority algorithms
• A note on greedy algorithms for the maximum weighted independent set problem
• Self-improving algorithms for coordinate-wise maxima
• Empirical hardness models
• Truth revelation in approximately efficient combinatorial auctions
• Self-improving algorithms
• Self-improving algorithms for delaunay triangulations
• Estimating the Efficiency of Backtrack Programs
• Local Search Heuristics for k-Median and Facility Location Problems
• Neural Network Learning
• Learning Bounds for Support Vector Machines with Learned Kernels
• Prediction, Learning, and Games

This page was built for publication: A PAC Approach to Application-Specific Algorithm Selection