The generalized knapsack function is defined as $f_{\a}(\x) = \sum_i
a_i \cdot x_i$, where $\a = (a_1, \ldots, a_m)$ consists of $m$
elements from some ring $R$, and $\x = (x_1, \ldots, x_m)$ consists
of $m$ coefficients from a specified subset $S \subseteq R$.
Micciancio ... more >>>

The ``analyst's traveling salesman theorem'' of geometric
measure theory characterizes those subsets of Euclidean
space that are contained in curves of finite length.
This result, proven for the plane by Jones (1990) and
extended to higher-dimensional Euclidean spaces by
Okikiolu (1991), says that a bounded set $K$ is contained
more >>>

We present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input.

We begin by reducing the input linear program to a special form in which we ... more >>>