# Efficient Vertex-Oriented Polytopic Projection for Web-scale Applications

arXiv: https://arxiv.org/abs/2103.05277 · HTML: https://mlsanity.com/paper/2103.05277/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 52 references that are in the map.
- First posted on arXiv 9 Mar 2021.

## Builds on (most cited first, 7 of 7)

- [Fairness in Machine Learning](https://mlsanity.com/paper/2012.15816/) (2020)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Policy Learning for Fairness in Ranking](https://mlsanity.com/paper/1902.04056/) (2019)
- [Provable Submodular Minimization using Wolfe's Algorithm](https://mlsanity.com/paper/1411.0095/) (2014)
- [A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing](https://mlsanity.com/paper/1405.5208/) (2014)
- [Diverse M-Best Solutions by Dynamic Programming](https://mlsanity.com/paper/1803.05748/) (2018)

## Built on by (most cited first, 2 of 2)

- [BanditLP: Large-Scale Stochastic Optimization for Personalized Recommendations](https://mlsanity.com/paper/2601.15552/) (2026)
- [Neural Optimization with Adaptive Heuristics for Intelligent Marketing System](https://mlsanity.com/paper/2405.10490/) (2024)

## Abstract (arXiv)

We consider applications involving a large set of instances of projecting points to polytopes. We develop an intuition guided by theoretical and empirical analysis to show that when these instances follow certain structures, a large majority of the projections lie on vertices of the polytopes. To do these projections efficiently we derive a vertex-oriented incremental algorithm to project a point onto any arbitrary polytope, as well as give specific algorithms to cater to simplex projection and polytopes where the unit box is cut by planes. Such settings are especially useful in web-scale applications such as optimal matching or allocation problems. Several such problems in internet marketplaces (e-commerce, ride-sharing, food delivery, professional services, advertising, etc.), can be formulated as Linear Programs (LP) with such polytope constraints that require a projection step in the overall optimization process. We show that in the very recent work, the polytopic projection is the most expensive step and our efficient projection algorithms help in gaining massive improvements in performance.