Primal beats dual on online packing LPs in the random-order model
From MaRDI portal
Publication:5259564
DOI10.1145/2591796.2591810zbMath1315.68291arXiv1311.2578OpenAlexW2086189137MaRDI QIDQ5259564
Andreas Tönnis, Thomas Kesselheim, Berthold Vöcking, Klaus Radke
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.2578
Linear programming (90C05) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (20)
Approximation algorithms for stochastic combinatorial optimization problems ⋮ Secretary Markets with Local Information ⋮ The Temp Secretary Problem ⋮ Online Appointment Scheduling in the Random Order Model ⋮ Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds ⋮ A stochastic algorithm for online bipartite resource allocation problems ⋮ New results for the \(k\)-secretary problem ⋮ Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order ⋮ Asymptotic analysis for multi-objective sequential stochastic assignment problems ⋮ Simple and fast algorithm for binary integer and online linear programming ⋮ Unnamed Item ⋮ An Approximation Algorithm for Network Revenue Management Under Nonstationary Arrivals ⋮ Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints ⋮ Scheduling In the random-order model ⋮ Secretary markets with local information ⋮ Unnamed Item ⋮ Online Submodular Maximization Problem with Vector Packing Constraint. ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem ⋮ Improved online algorithm for fractional knapsack in the random order model ⋮ Online Resource Allocation Under Partially Predictable Demand
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Efficient algorithms for privately releasing marginals via convex relaxations
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Faster Algorithms for Privately Releasing Marginals
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately Releasing Conjunctions and the Statistical Query Barrier
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Collusion-secure fingerprinting for digital data
- On the complexity of differentially private data release
- Advances in Cryptology – CRYPTO 2004
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Theory of Cryptography
This page was built for publication: Primal beats dual on online packing LPs in the random-order model
