We suggest a new model and algorithms for global routing in chip design. Traditional global routing covers the chip with a 3D grid graph. However, terminals are implicitly mapped to tile centers, any tile-internal wiring is largely ignored, hindering accurate congestion estimates, and the structure of the nets is altered. To overcome these deficiencies, we propose a new model that always considers exact pin and wire positions. We work with rhomboidal tiles and pack Steiner trees rather into the tiles than into a grid graph. We present a new algorithm for computing shortest paths with respect to tile prices, exploiting the rhomboidal shape of the tiles. We then solve the Steiner tree packing problem using the min-max resource sharing algorithm to approximately minimize the total wire length subject to wire density constraints. Our results are routes connecting to pin shapes which correlate well with detailed routing in terms of wire length and via count. Moreover, our rhomboidal model allows us to scale up the tile size and still produce reliable input for the detailed router. We demonstrate the benefits of this approach with experimental results on industrial chips.

We present a new approach for the cell selection problem based on a resource sharing formulation, which is a specialization of Lagrangian relaxation with multiplicative weight updates. For the convex continuous gate sizing problem, we can prove fast polynomial running times. This theoretical result also gives some justification to previous heuristic multiplicative weight update methods. For the discrete cell selection problem, where voltage thresholds can also be chosen, we employ the new algorithm heuristically and achieve superior results on industrial benchmarks compared with one of the previously best known algorithms, and competitive results on the ISPD 2013 benchmarks. Finally, we demonstrate how the approach can be parallelized effectively achieving speed-ups of up to 16.

We study the simplex method over polyhedra satisfying certain "discrete curvature" lower bounds, which enforce that the boundary always meets vertices at sharp angles. Motivated by linear programs with totally unimodular constraint matrices, recent results of Bonifas et al. (SOCG 2012), Brunsch and Röglin (ICALP 2013), and Eisenbrand and Vempala (2014) have improved our understanding of such polyhedra. We develop a new type of dual analysis of the shadow simplex method which provides a clean and powerful tool for improving all previously mentioned results. Our methods are inspired by the recent work of Bonifas and the first named author, who analyzed a remarkably similar process as part of an algorithm for the Closest Vector Problem with Preprocessing. For our first result, we obtain a constructive diameter bound of O((n^2 / delta) ln (n / delta)) for n-dimensional polyhedra with curvature parameter delta in (0, 1]. For the class of polyhedra arising from totally unimodular constraint matrices, this implies a bound of O(n^3 ln n). For linear optimization, given an initial feasible vertex, we show that an optimal vertex can be found using an expected O((n^3 / delta) ln (n / delta)) simplex pivots, each requiring O(mn) time to compute. An initial feasible solution can be found using O((mn^3 / delta) ln (n / delta)) pivot steps.

The parametric lattice-point counting problem is as follows: Given an integer matrix A ∊ ℤm×n, compute an explicit formula parameterized by b ∊ ℝm that determines the number of integer points in the polyhedron {x ∊ ℝn: Ax ≤ b}. In the last decade, this counting problem has received considerable attention in the literature. Several variants of Barvinok's algorithm have been shown to solve this problem in polynomial time if the number n of columns of A is fixed. Central to our investigation is the following question: Can one also efficiently determine a parameter b such that the number of integer points in {x ∊ ℝn: Ax ≤ b} is minimized? Here, the parameter b can be chosen from a given polyhedron Q ⊆ ℝm. Our main result is a proof that finding such a minimizing parameter is NP-hard, even in dimension 2 and even if the parametrization reflects a translation of a 2-dimensional convex polygon. This result is established via a relationship of this problem to arithmetic progressions and simultaneous Diophantine approximation. On the positive side we show that in dimension 2 there exists a polynomial time algorithm for each fixed k that either determines a minimizing translation or asserts that any translation contains at most 1 + 1/k times the minimal number of lattice points.

Some of the routing protocols used in telecommunication networks route traffic on a shortest path tree according to configurable integral link weights. One crucial issue for network operators is finding a weight function that ensures a stable routing: when some link fails, traffic whose path does not use that link should not be rerouted. In this paper we improve on several previously best results for finding small stable weights. As a conceptual contribution, we draw a connection between the stable weights problem and the seemingly unrelated unique-max coloring problem. In unique-max coloring, one is given a set of points and a family of subsets of those points called regions. The task is to assign to each region a color represented as an integer such that, for every point, one region containing it has a color strictly larger than the color of any other region containing this point. In our setting, points and regions become edges and paths of the shortest path tree, respectively, and based on this connection, we provide stable weight functions with a maximum weight of $O(n \log n)$ in the case of single link failure, where $n$ is the number of vertices in the network. Furthermore, if the root of the shortest path tree is known, we present an algorithm for determining stable weights bounded by $4n$, which is optimal up to constant factors. For the case of an arbitrary number of failures, we show how stable weights bounded by $3^n n$ can be obtained. All the results improve on the previously best known bounds.

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 the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomial time if the number of constraints is fixed. It turns out that this generalization is NP-hard even if the number of constraints is fixed. However, if, in addition, the objective is the all-one vector, then one can test in polynomial time whether the additive gap is bounded by a constant.

We investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Although this abstraction is simpler than other abstractions that were previously studied in the literature, the best upper bounds on the diameter of polyhedra continue to hold here. On the other hand, we show that this abstraction has its limits by providing a superlinear lower bound.