We derive a new upper bound on the diameter of the graph of a polyhedron P = {x ∈ Rn : Ax ≤ b}, where A ∈ Zm×n. The bound is polynomial in n and the largest absolute value of a sub-determinant of A, denoted by Δ. More precisely, we show that the diameter of P is bounded by O(Δ2 n4 log nΔ). If P is bounded, then we show that the diameter of P is at most O(Δ2 n3.5 log nΔ).

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest lattice vector problem in the infinity-norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2(O(n)) (log(1/epsilon))(O(n)) which improves upon the (2+1/epsilon)(O(n)) running time of the previously best algorithm by Blömer and Naewe. Our algorithm is based on a solution of the following geometric covering problem that is of interest of its own: Given epsilon>0, how many ellipsoids are necessary to cover the scaled unit cube [-1+epsilon, 1-epsilon]n such all ellipsoids are contained in the standard unit cube [-1,1]n. We provide an almost optimal bound for the case where the ellipsoids are restricted to be axis-parallel.

We consider several real-time scheduling problems on heterogeneous multiprocessor platforms, in which the different processors share a common memory pool. These include (i)~scheduling a collection of implicit-deadline sporadic tasks with the objective of meeting all deadlines, and (ii)~scheduling a collection of independent jobs with the objective of minimizing the make span of the schedule. Both these problems are intractable (NP-hard). For each, we derive polynomial-time algorithms for solving them approximately, and show that these algorithms have bounded deviation from optimal behavior. We also consider the problem of determining how much common memory a platform needs in order to be able to accommodate a specified real-time workload.