ABSTRACT
This chapter focuses on the global routing problem. It discusses routing techniques that are based on the linear relaxation of an integer programming formulation of the global routing problem. The chapter also discusses the linear relaxation and the dual linear program. It presents early work on linear programming for global routing, in particular the simplex method with column generation. The chapter describes the multicommodity flow problem and the fractional packing problem and shows the relationship to the fractional global routing problem. It also presents a fully polynomial approximation scheme for the fractional global routing problem based on the multicommodity flow approximation schemes and proves the approximation ratio. The chapter examines randomized rounding as introduced by P. Raghavan and C. D. Thompson, which is used to achieve the final integer solution. The expected value for the relative congestion of an edge or of the maximum relative congestion after randomized rounding is equal to the relative congestion of the fractional solution.
