|
A bad fact about ``cheap'' algorithms is that all known methods of this type possess sublinear rate of convergence and thus cannot guarantee high-accuracy solutions. A good piece of news is that with ``favourable geometry'' of a problem, properly chosen cheap algorithms demonstrate {\sl dimension-independent} and {\sl optimal in the large-scale case}, in a certain precise sense, rate of convergence, which makes these methods well-suited for finding moderate-accuracy solutions of really large-scale problems.
In this talk, we present a new simple method of this type aimed at solving problems of the form $\min\limits_{x\in X} \max\limits_{y\in Y} F(x,y)$, where $X$, $Y$ are convex compact and $F$ is a convex-concave function with Lipschitz continuous gradient. When $X$ and $Y$ possess favourable geometry (e.g., are balls, or simplexes, or spectahedrons), the method exhibits (nearly) dimension-independent and optimal in the large-scale case $O(1/t)$ rate of convergence.
Our numerical examples include large-scale
matrix games and computing, within absolute accuracy 1, the Lovacz
capacity of a graph (the largest graph we have processed has 1024
vertices and over 197,000 arcs).
James Orlin
MIT
The Complexity of Inverse and Partial Inverse Optimization Problems
Given a combinatorial optimization problem and a feasible
solution to it, the corresponding inverse optimization problem is to find
a minimal adjustment of the cost function such that the given solution
becomes optimum. A partial inverse optimization problem differs from an
inverse optimization problem in that only part of an optimal solution is
known.
Researchers have applied inverse optimization to the study of geophysics
(e.g., what are seismological parameters that are consistent with the
observed behavior of an earthquake), and transportation analysis (e.g.,
how can one adjust road tolls so as to lead to optimal traffic flows),
and to marketing (e.g., what is the best estimate for a person's
utilities for product features based on observations of their preferences
for products?)
After formalizing the notion of an inverse problem and its variants, we
present various methods for solving inverse problems efficiently, and
review the complexity of partial inverse problems. In general, if the
original problem is solvable in polynomial time, the inverse problem is
also solvable in polynomial time. On the other hand, for very simple
network problems, such as the assignment problem, the shortest path
problem, and the minimum cut problem, the partial inverse problem is
NP-hard.
Baruch Schieber
IBM Research
Approximating the Throughput in Resource Allocation and Real Time Scheduling.
We consider the problem of maximizing the throughput or minimizing the
loss in resource allocation and real time scheduling. In this problem we
have a set of activities competing for a reusable resource. Each activity
utilizes a certain amount of the resource for the duration of its
execution and frees it upon completion. The problem
is to select a feasible subset of activities for execution, that is, a
subset of activities such that the total amount of resource consumed by
them simultaneously does not exceed the amount of resource available. The
objective is to find a feasible subset so as to maximize the profit
accrued or, in some cases, to minimize the profit lost due to unscheduled
activities. Several problems can be cast in these terms, among them: (i)
real-time scheduling of jobs on parallel machines; (ii) bandwidth
allocation for sessions between two endpoints; (iii) general caching; (iv)
dynamic storage allocation; (v) bandwidth allocation on optical line and
ring topologies.
We consider several variants of this problem, all of which are NP-Hard, and present efficient constant factor approximation algorithms for computing the maximum throughput and minimum loss in these variants. Some of our algorithms are based on the local-ratio technique.
Based on joint work with Amotz Bar-Noy, Reuven Bar-Yehuda, Don
Coppersmith, Ari Freund, Sudipto Guha, Yoav Katz, Joseph (Seffi) Naor,
Hadas Shachnai, and Maxim Sviridenko.