  We consider the optimization problem of a multi-resource, multi-unit VCG
auction that produces an optimal, i.e., non-approximated, social welfare. We
present an algorithm that solves this optimization problem with
pseudo-polynomial complexity and demonstrate its efficiency via our
implementation. Our implementation is efficient enough to be deployed in real
systems to allocate computing resources in fine time-granularity. Our algorithm
has a pseudo-near-linear time complexity on average (over all possible
realistic inputs) with respect to the number of clients and the number of
possible unit allocations. In the worst case, it is quadratic with respect to
the number of possible allocations. Our experiments validate our analysis and
show near-linear complexity. This is in contrast to the unbounded,
nonpolynomial complexity of known solutions, which do not scale well for a
large number of agents.
  For a single resource and concave valuations, our algorithm reproduces the
results of a well-known algorithm. It does so, however, without subjecting the
valuations to any restrictions and supports a multiple resource auction, which
improves the social welfare over a combination of single-resource auctions by a
factor of 2.5-50. This makes our algorithm applicable to real clients in a real
system.
