Efficient algorithms for online decision problems
From MaRDI portal
Publication:2568459
DOI10.1016/j.jcss.2004.10.016zbMath1094.68112OpenAlexW2169401877MaRDI QIDQ2568459
Santosh Vempala, Adam Tauman Kalai
Publication date: 10 October 2005
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2004.10.016
Nonnumerical algorithms (68W05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (55)
Replicator dynamics: old and new ⋮ Lower bounds on individual sequence regret ⋮ Oracle-Based Robust Optimization via Online Learning ⋮ A simulated annealing algorithm for the restricted stochastic traveling salesman problem with exponentially distributed arc lengths ⋮ Learning in auctions: regret is hard, envy is easy ⋮ The Post-Disaster Debris Clearance Problem Under Incomplete Information ⋮ Online learning for min-max discrete problems ⋮ On minimaxity of follow the leader strategy in the stochastic setting ⋮ Structured Robust Submodular Maximization: Offline and Online Algorithms ⋮ Combining initial segments of lists ⋮ Feature-aware regularization for sparse online learning ⋮ Regrets of proximal method of multipliers for online non-convex optimization with long term constraints ⋮ Regret minimization in online Bayesian persuasion: handling adversarial receiver's types under full and partial feedback models ⋮ Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback ⋮ No-regret algorithms in on-line learning, games and convex optimization ⋮ Unnamed Item ⋮ No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization ⋮ No-regret learning for repeated non-cooperative games with lossy bandits ⋮ Online variance minimization ⋮ Online multiple kernel classification ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Scale-free online learning ⋮ Combinatorial bandits ⋮ The covering Canadian traveller problem ⋮ Extracting certainty from uncertainty: regret bounded by variation in costs ⋮ Regret bounds for sleeping experts and bandits ⋮ Online Learning Based on Online DCA and Application to Online Classification ⋮ An Online Policy Gradient Algorithm for Markov Decision Processes with Continuous States and Actions ⋮ Online First-Order Framework for Robust Convex Optimization ⋮ Online linear optimization and adaptive routing ⋮ Unnamed Item ⋮ Sampled fictitious play is Hannan consistent ⋮ Regret bounded by gradual variation for online convex optimization ⋮ Equilibria of Greedy Combinatorial Auctions ⋮ Near-Optimal Algorithms for Online Matrix Prediction ⋮ A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization ⋮ Unnamed Item ⋮ Unified Algorithms for Online Learning and Competitive Analysis ⋮ On modification of population-based search algorithms for convergence in stochastic combinatorial optimization ⋮ Logarithmic regret algorithms for online convex optimization ⋮ Regret to the best vs. regret to the average ⋮ Unnamed Item ⋮ Multi-Finger Binary Search Trees ⋮ Perspectives on multiagent learning ⋮ Online Discrete Optimization in Social Networks in the Presence of Knightian Uncertainty ⋮ A Combinatorial Metrical Task System Problem Under the Uniform Metric ⋮ How the Experts Algorithm Can Help Solve LPs Online ⋮ Online Linear Optimization for Job Scheduling Under Precedence Constraints ⋮ The Canadian Traveller Problem and its competitive analysis ⋮ Online Learning over a Finite Action Set with Limited Switching ⋮ Efficient Online Linear Optimization with Approximation Algorithms ⋮ AN ONLINE PORTFOLIO SELECTION ALGORITHM WITH REGRET LOGARITHMIC IN PRICE VARIATION ⋮ Machine learning advised algorithms for the ski rental problem with a discount ⋮ Unnamed Item ⋮ Small-Loss Bounds for Online Learning with Partial Information
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Static optimality and dynamic search-optimality in lists and trees
- Predicting nearly as well as the best pruning of a planar decision graph.
- The geometry of graphs and some of its algorithmic applications
- Adapting to a reliable network path
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Adaptive routing with end-to-end feedback
- Dynamic huffman coding
- Self-adjusting binary search trees
- Universal Portfolios
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Learning Theory
- 10.1162/1532443041424328
- Learning Theory and Kernel Machines
This page was built for publication: Efficient algorithms for online decision problems
