---
abstract: 'We develop a rounding method based on random walks in polytopes, which leads to improved approximation algorithms and integrality gaps for several assignment problems that arise in resource allocation and scheduling. In particular, it generalizes the work of Shmoys & Tardos on the generalized assignment problem in two different directions, where the machines have hard capacities, and where some jobs can be dropped. We also outline possible applications and connections of this methodology to discrepancy theory and iterated rounding.'
address: ' $^{1}$University of Maryland, College Park, MD 20742, USA '
author:
- 'Barna Saha$^{1}$ [^1]'
- 'Aravind Srinivasan$^{1}$ [^2]'
bibliography:
- 'af2009.bib'
- 'af2.bib'
title: 'A New Approximation Technique for Resource-Allocation Problems'
---

Introduction {#sec:intro}
============

Random Matchings with Linear Constraints, and GAP with Capacity Constraints {#sec:sched-cap}
===========================================================================

Scheduling with Outliers {#sec:sched-outlier}
========================

Max-Min Fair Allocation {#sec:max-min}
=======================

Future Directions {#sec:future}
=================

[^1]: Dept. of Computer Science, University of Maryland, College Park, MD 20742. Research supported by NSF Award NSF CCF-0728839.

[^2]: Dept. of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742. Supported in part by NSF ITR Award CNS-0426683 and NSF Award CNS-0626636.
