23

*Restriction* is one of the most basic techniques to design approximation algorithms. The idea is to generate a solution to a given problem
P
by providing an optimal or suboptimal solution to a subproblem of
P
. A subproblem of a problem
P
means restricting the solution space for
P
by disallowing a subset of the feasible solutions. Restriction may be structural or algorithmic. In the case of structural restriction, the idea is to impose some structure on the set of feasible solutions (the solution space), which can be exploited by an efficient algorithm that solves the problem optimally or suboptimally. In the case of algorithmic restriction, an algorithm restricts the set of feasible solutions that may be found. The problem in the restricted solution spaces is referred as the *subproblem*. For this approach to be effective the subproblem must have the property that for every problem instance, its optimal or suboptimal solution should have an objective function value that is “close” to the optimal one for the original problem. The most common approach is to solve the subproblem once but there are algorithms where more than one subproblem is solved, and then the best of the solutions computed is the solution generated. In this chapter we discuss this methodology and show how to apply it to several problems. Approximation algorithms based on this approach are discussed in Volume 1, Chapters 31, 32, 36, and Volume 2, Chapters 6 and 15.

*Restriction* is one of the most basic techniques to design approximation algorithms. The idea is to generate a solution to a given problem

This approach is in a sense the opposite of “relaxation,” that is, augmenting the feasible solution space by including previously infeasible solutions. In this case, one needs to solve a superproblem of

. An approximation algorithm for solves the superproblem (optimally or suboptimally) and then transforms such solution to one that is feasible for . Approximation algorithms based on the linear programming methodology fall under this category. There are many different conversion techniques including rounding, randomized rounding, and so on. Chapters 4, 7, and 11 discuss this approach in detail. Approximation algorithms based on both restriction and relaxation exist (Vol. 2, Chap. 8). These algorithms first restrict the solution space and then relaxes it. The resulting solution space is different from the original one, as there are some infeasible solutions in the original problem that are now a part of the solution space, and some feasible solution in the original problem is no longer part of the solution space.In this chapter we discuss several approximation algorithms based on restriction. When designing algorithms of this type the first question is: how to select one of the many subproblem(s) to provide a good approximation for a given problem? One would like to select a subproblem that “works best.” But what do we mean by a subproblem that works best? The one that works best could be a subproblem that results in an approximation algorithm with smallest possible approximation ratio, or it could be a subproblem whose solution can be computed the fastest, or one may use some other criteria, for example, any of the ones discussed in Chapter 1. Perhaps “works best” should be with respect to a combination of different criteria. But even when using the approximation ratio as the only evaluation criteria for an algorithm, it is not at all clear how to select a subproblem that can be solved quickly and from which a best possible solution could be generated. These are the two most important properties when choosing a subproblem to solve. By studying several algorithms based on restriction, one learns why it works for these cases and then it becomes easier to find ways to approximate other problems.

The problems that we discuss in this chapter to illustrate “restriction” are Steiner tree, the traveling salesperson, covering points by squares, rectangular partitions, and routing multiterminal nets. The Traveling Salesperson Problem (TSP), and Steiner tree problem are classical problems in combinatorial optimization. The algorithms that we discuss for the TSP are among the best known approximation algorithms for combinatorial problems.

A closely related approach to restriction is *transformation-restriction*. The idea is to transform the problem instance to a restricted instance of the same problem. The difference is that the restricted problem instance is not a subproblem of original problem instance as in the case of restriction, but it is a “simpler” problem of the same type. In Section 3.5 we present algorithms based on this approach for routing multiterminal nets and embedding hyperedges in a cycle. The fully polynomial time approximation scheme for the knapsack problem based on rounding discussed in Chapter 9 is based on transformation-restriction. In Section 3.8 we summarize the chapter and briefly discuss other algorithms based on restriction for path problems arising in computational geometry.

The Steiner tree problem is a classical problem in combinatorial optimization. Let’s define the Steiner tree problem over an edge weighted complete metric graph

, where is the set of vertices, is the set of edges, and is the weight function for the edges. Since the graph is metric the set of weights satisfies the triangle inequality, that is, for every pair of vertices , the weight is less than or equal to the sum of the weight of the edges in any path from vertex to vertex . The Steiner tree problem consists of a metric graph and a subset of vertices . The problem is to find a tree that includes all the vertices in plus some other vertices in the graph such that the sum of the weight of the edges in the tree is least possible. The Steiner tree problem is an NP-hard problem.When

the problem is called the minimum weight (cost) spanning tree problem. By the 1960s there were several well-known polynomial time algorithms to construct a minimum weight spanning tree for edge weighted graphs [1]. These simple greedy algorithms have low-order polynomial time complexity bounds.Given an instance of the metric graph Steiner tree problem

one may construct a minimum weight spanning tree for the subgraph , where and includes only the edges joining vertices in . Clearly this minimum weight spanning tree is a restricted version of the Steiner tree problem and it seems a natural way to approximate the Steiner tree problem. This approach was analyzed in 1968 by E. F. Moore (see Reference 2) for the Steiner tree problem defined in metric space (e.g., 2D). The metric graph problem we just defined, includes only a subset of all the possible points in metric space. E. F. Moore presented an elegant proof of the fact that in metric space (and also for metric graphs) , where , , and are the weight of a minimum weight spanning tree, a minimum weight tour (solution) for the TSP, and minimum weight Steiner tree for any set of points , respectively. We defined the TSP in Chapter 2. Since every spanning tree for is a Steiner tree for , the above bounds show that when using a minimum weight spanning tree to approximate the Steiner tree results in a solution whose weight is at most twice the weight of an optimal Steiner tree. In other words, any algorithm that generates a minimum weight spanning tree is a 2-approximation algorithm for the Steiner tree problem. Furthermore, this approximation algorithm takes the same time as an algorithm that constructs a minimum weight spanning trees for edge-weighted graphs [1], since such an algorithm can be used to construct an optimal spanning tree for a set of points in metric space. The above bound is established by defining a transformation from any minimum weight Steiner tree into a TSP tour in such a way that [2]. Then by observing that deleting an edge from an optimum tour to the TSP problem results in a spanning tree, shows that . The proof is identical to the one given in the next section where we show this result, but starting from a minimum weight spanning tree. So where is restriction in this case? The algorithm finds the best possible solution that does not include Steiner points, that is, points in . In other words the restriction is to find the best tree without allowing Steiner points.Chapter 36 also discusses several constant-ratio approximation algorithms for Steiner trees, including ones where the graph is not metric.

The TSP has been studied for many decades [3]. There are many variations of this problem. One of the simplest versions of the problem consists of an edge-weighted complete graph and the problem is to find a minimum weight tour that starts and ends at vertex one and visits every vertex *exactly* once. The weight of a tour is the sum of the weight of the edges in the tour. Sahni and Gonzalez [4] (Chapter 1) show that the constant-ratio approximation problem is NP-hard, that is, if for any constant

In the literature you will find that the TSP is also defined with tours visiting each vertex *at least* once. We now show that the “at most once” version over metric graphs and the “exactly once” version over metric graphs are equivalent problems. Consider any optimal tour

Now suppose that you have an optimal tour

for an instance of the “at least once” version of the TSP. Applying the above-mentioned transformation we obtain an optimal tour in which every vertex is visited exactly once. Deleting an edge from the tour results in a spanning tree. Therefore, the weight of a minimum weight spanning tree is a lower bound for the weight of an optimal tour. The questions are: How good of a lower bound is it? How can one construct a tour from a spanning tree?How can we find a tour from a spanning tree

? Just draw the spanning tree in the plane with a vertex as its root and construct a tour by visiting each edge in the tree twice as illustrated in Figure 3.1. A more formal approach is to construct anFigure 3.1 Spanning tree (solid lines) and tour constructed (dashed lines).

The approximation algorithm, which we refer to as *DMCST*, constructs a minimum cost spanning tree, makes a copy of all the edges in the tree, and then generates a tour from this tree with weight at most equal to twice the cost of a minimum cost spanning tree. We established before that an optimal tour has weight greater than the weight of a minimum cost spanning tree, it then follows that the weight of the tour that the DMCST algorithm generates is at most twice the weight of an optimal tour for

**Theorem 3.1**
*For the metric TSP problem algorithm DMCST generates a tour with weight at most*

*Proof*. The proof for the approximation ratio follows from the above-mentioned discussion. As Fredman and Tarjan [8] point out, implementing Prim’s minimum cost spanning tree algorithm by using Fibonacci heaps results in a minimum cost spanning tree algorithm that takes

This constructive proof is based on Moore’s proof for the approximation algorithm for the Steiner tree problem. The difference is that he starts from an optimal Steiner tree.

So where is the restriction in the above-mentioned algorithms? We are actually *restricting* tours for the TSP to traverse the least possible number of *different* edges, though a tour may traverse some of these edges more than once. The minimum number of different edges needed from

That justifies the use of a minimum weight spanning tree. This is another way to think about the design of the DMWST algorithm.

Christofides [6] modified the previous approach so that the tours generated have total weight within 1.5 times the weight of an optimal tour. However, the currently fastest implementation of this procedure takes

time. His modification is very simple. First, observe that there are many different ways to transform a spanning tree into an Eulerian multigraph. All possible augmentations must include at least one edge incident to every odd degree vertex in the spanning tree. Let be the set of odd-degree vertices in the spanning tree. Christofides’ idea is to transform the spanning tree into an Eulerian multigraph by adding the least number of edges with the least possible total weight. He showed that such set of edges is a minimum cost complete matching on the graph induced by the set of vertices in . ATo establish the 1.5 approximation ratio we observe that an optimal tour can be transformed without increasing its total weight into another tour that visits only the vertices in

because the graph is metric. One can partition the edges in this reduced tour into two sets such that each set is a complete matching for the restricted graph . One set contains the even numbered edges in the tour and the other set the odd numbered edges. Since a minimum cost complete matching for has total cost at most equal to either of the previous two matchings, it then follows that the minimum cost complete matching has total cost at most half of the weight of an optimal tour. Therefore, the edges in the the tour constructed by Christofides’ algorithm have weight at most 1.5 times the weight of an optimal tour. The time complexity for Christofides’ algorithm is and it is dominated by the time required to construct a minimum cost complete matching [9, 10]. We formalize this result in the following theorem whose proof is omitted as it follows the above discussion.
**Theorem 3.2 [6]**
*For the metric TSP, Christofides’ algorithm generates a tour with weight at most 1.5 times the weight of an optimal tour. The time complexity of the algorithm is*

This approach used by this algorithm is similar to the one employed by Edmonds and Johnson [11] for the *Chinese postman problem*. Given an edge weighted connected undirected graph, the Chinese postman problem is to construct a minimum weight cycle, which contains every edge in the graph possibly with repeated edges. The currently best algorithm to solve this problem takes

Given a set of

points, , in two-dimensional space and an integer , theWe discuss in this section a simple approximation algorithm based on restriction for the

problem. Assume without loss of generality that and and that at least one of the points hasThe restriction to the solution space is to only allow feasible solutions where each square covers points from only one band. Note that an optimal solution to the

problem does not necessarily satisfy this property. For example, the instance with has two squares in optimal cover. The first square covers points and , and the second square covers and . However, an optimal cover for the points in band 0 (i.e., and ) is 1 square and the one for the points in band 1 (i.e., and ) is 2 squares. So an optimal cover to the restricted problem has three squares, but an optimal cover for the problem has two squares.One reason for restricting the solution space in this way is that an optimal cover for any given band can be easily generated by a greedy procedure in

time [14]. A greedy approach places a square as high as possible provided it includes the bottommost point in the band as well as all other points in the band at a vertical distance at most 1 from a bottommost point. All the points covered by this square are removed and the procedure is repeated until all the points have been covered. One can easily show that this is an optimal cover by transforming any optimal solution for the band, without increasing the number of squares, to the cover generated by the greedy algorithm. By using elaborate data structures Gonzalez [14] showed that the greedy algorithm can be implemented to take time, where is the number of squares in an optimal solution. Actually a method that uses considerable more space can be used to solve the problem in time [14].The solution generated by our algorithm for the whole problem is the union of the covers for each of the bands generated by the greedy method. Let

be the total number of squares, where ( ) is the number of square for the even (odd) numbered bands. We claim that an optimal solution to the problem has at least squares. This follows from the fact that an optimal solution for the even (odd) numbered bands is because it is not possible for a square to cover points from two different even (odd) numbered bands. Therefore, is the number of squares in an optimal solution for problem instance
**Theorem 3.3**
*For the*

A polynomial time approximation scheme for the generalization of the

to dimensions (the problem) is discussed in Volume 1, Chapter 8 and Volume 2, Chapter 5. The idea is to generate a set of solutions by shifting the bands by different amounts and then selecting as the solution the best cover computed by the algorithm. This approach is calledThe minimum edge-length rectangular partition (

) problem has applications in the area of computer aided-design of integrated circuits and systems. Given a rectangle with interior points , the problem is to introduce a set of interior lines segments with least total length such that every point in is in at least one of the partitioning line segments, and is partitioned into rectangles. Figure 3.2a shows a problem instance and Figure 2b shows an optimal rectangular partition for the problem instanceFigure 3.2 (a) Instance I of the R G P problem. (b) Rectangular partition for the instance I . (c) Guillotine partition the instance I

A rectangular partition

is said to have aFinding an optimal rectangular partition is an NP-hard problem [18]. However, an optimal guillotine partition can be constructed in polynomial time. Therefore, it is natural to restrict the solution space to guillotine partitions when approximating rectangular partitions.

In Volume 2, Chapter 6 we prove that an optimal guillotine partition has total edge length, that is at most twice the length of an optimal rectangular partition. Gonzalez and Zheng [19] presented a complex proof that shows that bound is just 1.75. In Volume 2, Chapter 6 we also explain the basic ideas behind the proof of the approximation ratio of 1.75. This approach has been extended to the multidimensional version of this problem by Gonzalez et al. [20].

An optimal guillotine partition can be constructed in

time via dynamic programming. When is large this approach is not practical. Gonzalez et al. [21] showed that suboptimal guillotine partitions that can be constructed in time generate solutions with total edge length at most four times the length of an optimal rectangular partition. As in the case of optimal guillotine partitions, this result has been extended to the multidimensional version of the problem [21]. Clearly, none of the methods dominates the other when considering both the approximation ratio and the time complexity bound.Chapter 36 discusses how more general guillotine cuts can be used to develop a PTAS for the TSP in two-dimensional space. Volume 2, Chapter 2 discusses this approach for the TSP and Steiner tree problems.

Let

be a rectangle whose sides lie on the two-dimensional integer grid. A subset of grid points on the boundary of that do not include the corners of is denoted by , and its grid points are calledThe Multiterminal net routing Around a Rectangle

problem is given a rectangle and a set of nets, find a layout, subject to the constraints defined earlier, that fits inside a rectangle with least possible area. Constructing a layout in this case reduces to just finding the wire segments for each net along the grid lines (without dog-legs) outside , since the layer assignment is straight forward.Developing a constant-ratio approximation algorithm for this problem is complex because the objective function depends on the product of two values, rather than just one value as in most other problems. Gonzalez and Lee [22] developed a linear time algorithm for the

problem when every net consists of two terminal points. It is conjectured that the problem becomes NP-hard when the nets have three terminal points each. Gonzalez and Lee [22, 23] developed constant-ratio approximation algorithms for the problem [23, 24]. The approximation ratios for these algorithms are 1.69 [23] and 1.6 [24]. The approach is to partition the set of nets into groups and then route each group of nets independently of each other. Some of the groups are routed optimally. Since the analysis of the approximation ratio for these algorithms is complex, in this section we only analyze the case when the nets contain one terminal point on the top side of , and one or more terminal points on the bottom side of . The set of these nets is called . The algorithm to route the nets is based on restriction and it is interesting. Readers interested in additional details are referred to papers [23, 24].Let

be the number of nets. Let be an optimal area layout for all the nets and let be except that the set of nets in are all connected by a path that crosses the left side of . In this case the layout for the nets is restricted (only paths that cross the left side of are allowed). We use ( ) to denote the height of the layout on the top plus the corresponding height on the bottom side of . To simplify the analysis, lets assume that every net in is connected in by a path that either crosses the left or right (but not both) sides of . Gonzalez and Lee [24] explain how to modify the analysis when some of these nets are connected by paths that cross both the left and right sides ofBy *reversing* the connecting path for a net in

We transform

to by reversals in order to quantify the difference in heights between and . The largest increase in height is when all the nets are connected in by paths that cross the right side of . In this case we need to reverse all the connecting paths for the nets, so . When one plugs this in the analysis for the whole problem it results in an algorithm with an approximation ratio greater than 2.A better approach is to use the following restriction: All the connecting paths for the

nets are identical, and either they cross the left or the right side of . In this case we construct two different layouts. Let layout ( ) be except that all the nets in are connected by a path crossing the left (right) side of . Let be a minimum area layout between and . In let ( ) be the number of nets connected by a path crossing the left (right) side of . By reversing the minimum of paths it is possible to transform to or . Therefore, , which is better by 50% than for the assignment defined before.By trying more alternatives one can obtain better solutions. Let us partition the set of nets

into two groups, and . The set contains the nets in whose terminal point on the top side of is closest to the left side of , and set contains the remaining ones. For let be except that all the nets in are connected by paths that cross the “ ” side of and all the nets in are connected by paths that cross the “ ” side of . Let be a minimum area layout among and . Let be the number of nets in connected by a path that crosses the left side of . We define and similarly, but using the set . We establish in the following lemma that
**Lemma 3.1**
*Let*

*Proof*. The proof is by contradiction. Suppose that

*Case 1*:

To transform assignment

to we need to reverse the connecting paths of connecting paths. Therefore, . Since , we know that . Applying the same argument to assignment , we know . Adding these two last inequalities and substituting the fact that , we know that . Which contradicts our previous finding that.

*Case 2*:

A contradiction in this case can be obtained applying similar arguments to assignments

and .For three groups, rather than two, Gonzalez and Lee [23] showed that

, where is the best of the eight assignments. This is enough to prove the approximation ratio of 1.69 for the problem. If instead of three groups one uses six, one can prove , where is the best of the 64 assignments generated. In this case, approximation ratio for the whole problem is 1.6. Interestingly, partitioning into more groups results in smaller bounds for this group, but does not reduce the approximation ratio for the problem because the routing of other nets becomes the bottleneck. We state Gonzalez and Lee’s theorem without a proof. Readers interested in the proof are referred to Reference 24.
**Theorem 3.4**
*For the*

An interesting observation is that the proof that the bound

holds can be carried out automatically by solving a set of linear programming problems. The linear programming problems find the ratios for and such that the minimum increase from to one of the layouts is maximized. Note that some of the “natural” constraints of the problem are in terms max which makes the solution space nonconvex. However by replacing it with inequalities of the form and we partition the optimization region into several convex regions. By solving a set of linear programming problems (one for each convex region) the maximum possible increase can be computed.A closely related approach to restriction is to generate a solution by solving a restricted problem instance constructed from the original instance. We call this approach *transformation-restriction*. For example, consider the routing multiterminal nets around a rectangle discussed in Section 3.6. Remember that there are

Figure 3.3 (a) Net with k terminal points. (b) Resulting k 2-terminal nets.

In this subsection we present an approximation algorithm for embedding hyperedges in a cycle so as to minimize the congestion (EHCMC). This problem has applications in the area of design automation and parallel computing. As input we are given a hypergraph

where is the set vertices and is the set of hyperedges (or subsets with at least two elements of the set ). Traversing the vertices the clockwise direction forms a cycle which we call . Let and be two vertices in such that is the next vertex in in clockwise direction from . Then the pair for hyperedge defines the connecting path for that begins at vertex then proceeds in the clockwise direction along the cycle until reaching vertex . Every edge in the cycle that is visited by the connecting path formed by pair is said to beGanley and Cohoon [25] showed that when the maximum congestion is bounded by a fixed constant

, the EHCMC problem is solvable in polynomial time. But, the problem is NP-hard when there is no constant bound for . Frank et al. [26] showed that when the hypergraph is a graph the EHCMC problem can be solved in polynomial time. We call this problem the embedding edges in a cycle to minimize congestion (EECMC). In this section we present the simple linear time algorithm with an approximation ratio of two for the EHCMC problem developed by Gonzalez [27].The algorithm based on *transformation-restriction* for this problem is simple and uses the same approach as in the previous subsection. This general approach also works for other routing problems. A hyperedge with

We have seen several approximation algorithms based on restriction. As we have seen the restricted problem may be solved optimally or suboptimally as in Section 3.5. One generates solutions closer to optimal, whereas the other generates the solution faster. These are many more algorithms based on this technique. For example, some computational geometry problems where the objective function is in terms of distance have been approximated via restriction [28–31]. These type of problems allow feasible solutions to be any set of points. A restricted problem allows a set of points (called *artificial points*) to be part of the feasible solution space. The more artificial points, the smaller the approximation ratio of the algorithm; however, the algorithm takes longer to generate a solution.

There are problems for which it is not know whether or not there is a constant-ratio approximation algorithm. However, heuristics based on restriction are used to generate good solutions in practice. One such problems is discussed in Volume 2, Chapter 25.

A closely related approach to restriction is *transformation-restriction*. The idea is to transform the problem instance to a restricted instance of the same problem. The difference is that the restricted problem instance is not a subproblem of original problem instance as in the case of restriction. We showed how this approached is applied to a couple of problems.

Approximation algorithms that are based on restriction and relaxation exist. These algorithms first restrict the solution space and then relaxes it resulting in a solution space that is different from the original one. Gonzalez and Gonzalez [32] have applied this approach successfully to the minimum edge length corridor problem (Vol. 2, Chap. 8).

1
Sahni, S.
, Data Structures, Algorithms, and Applications in C++, 2nd ed., Silicon Press, Summit, NJ, 2005.

2
Gilbert, E.N.
and
Pollak, H.O.
, Steiner minimal trees, SIAM Journal of Applied Mathematics, 16(1), 1, 1968.

3
Lawler, E.L.
,
Lenstra, J.K.
,
Rinnooy Kan, A.H.G.
, and
Shmoys, D.B.
, Eds., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, New York, 1985.

4
Sahni, S.
and
Gonzalez, T.
, P-complete approximation problems, JACM, 23, 555, 1976.

5
Rosenkrantz, R.
,
Stearns, R.
, and
Lewis, L.
, An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3), 563, 1977.

6
Christofides, N.
, Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 338. Grad School of Industrial Administration, CMU, Pittsburgh, PA, 1976.

7
Weiss, M.A.
, Data Structures & Algorithms in C++, 2nd ed., Addison-Wesley, Reading, MA, 1999.

8
Fredman, M.
and
Tarjan, R.E.
, Fibonacci heaps and their uses in improved network optimization algorithms, JACM, 34(3), 596, 1987.

9
Gabow
H.N.
, A scaling algorithm for weighted matching on general graphs, in Proceedings of FOCS, IEEE Press, New York p. 90, 1985.

10
Lawler, E.L.
, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.

11
Edmonds, J.
and
Johnson, E.L.
, Matching Euler tours and the Chinese postman, Mathematical Programming, 5, 88, 1973.

12
Flower, R.J.
,
Paterson, M.S.
, and
Tanimoto, S.L.
, Optimal packing and covering in the plane are NP-complete, Information Processing Letters, 12, 133, 1981.

13
Hochbaum
D.S.
and
Maass, W.
, Approximation schemes for covering and packing problems in image processing and VLSI, JACM, 32(1), 130, 1985.

14
Gonzalez, T.F.
, Covering a set of points in multidimensional space, Information Processing Letters, 40, 181, 1991.

15
Tanimoto, S.L.
, Covering and indexing an image subset, in Proceedings of the IEEE Conference on Pattern Recognition and Image Processing, IEEE Press, New York, p. 239, 1979.

16
Tanimoto, S.L.
and
Fowler, R.J.
, Covering image subsets with patches, in Proceedings of the 5th International Conference on Pattern Recognition, IEEE Press, New York, p. 835, 1980.

17
Baker, B.S.
, Approximation algorithms for NP-complete problems on planar graphs, in Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science (Tucson, AZ, November
7–9), IEEE, New York, p. 133, 1983.

18
Lingas, A.
,
Pinter, R.Y.
,
Rivest, R.L.
, and
Shamir, A.
, Minimum edge length partitioning of rectilinear polygons, in Proceedings of the 20th Allerton Conference on Communication, Control, and Computing, Monticello, IL, 1982.

19
Gonzalez, T.F.
and
Zheng, S.Q.
, Improved bounds for rectangular and guillotine partitions, Journal of Symbolic Computation, 7, 591, 1989.

20
Gonzalez, T.F.
,
Razzazi, M.
,
Shing, M.
, and
Zheng, S.Q.
, On optimal d –guillotine partitions approximating hyperrectangular partitions, Computational Geometry: Theory and Applications, 4(1), 1, 1994.

21
Gonzalez, T.F.
,
Razzazi, M.
, and
Zheng, S.Q.
, An efficient divide-and-conquer algorithm for partitioning into d-boxes, International Journal of Computational Geometry & Applications, 3(4), 417, 1993.

22
Gonzalez, T.F.
and
Lee, S.L.
, A linear time algorithm for optimal wiring around a rectangle, JACM, 35(4), 810, 1988.

23
Gonzalez, T.F.
and
Lee, S.L.
, Routing multiterminal nets around a rectangle, IEEE Transactions on Computers, 35(6), 543, 1986.

24
Gonzalez, T.F.
and
Lee, S.L.
, A 1.60 approximation algorithm for routing multiterminal nets around a rectangle, SIAM Journal on Computing, 16(4), 669, 1987.

25
Ganley, J.L.
, and
Cohoon, J.P.
, Minimum-congestion hypergraph embedding in a cycle, IEEE Transactions on Computers, 46(5), 600, 1997.

26
Frank, A.
,
Nishizeki, T.
,
Saito, N.
,
Suzuki, H.
, and
Tardos, E.
, Algorithms for routing around a rectangle, Discrete Applied Mathematics, 40(3), 363, 1992.

27
Gonzalez, T.F.
, Improved approximation algorithms for embedding hypergraphs in a cycle, Information Processing Letters, 67, 267, 1998.

28
Papadimitriou, C.H.
, An algorithm for shortest path motion in three dimensions. Information Processing Letters, 20, 259, 1985.

29
Choi, J.
,
Sellen, J.
, and
Yap, C.K.
, Approximate Euclidean shortest path in 3-space, International Journal of Computational Geometry and Applications, 7(4), 271, 1997.

30
Choi, J.
,
Sellen, J.
, and
Yap
C.K.
, Approximate Euclidean shortest path in 3-space, in Proceedings of the 10th Annual Symposium on Computational Geometry, ACM, New York, p. 41, 1994.

31
Bhosle, A.M.
and
Gonzalez, T.F.
, Exact and approximation algorithms for finding an optimal bridge connecting two simple polygons, International Journal on Computational Geometry and Applications, 15(6), 609, 2005.

32
Gonzalez, A.
and
Gonzalez, T.F.
, Approximating Corridors and Tours via Restriction and Relaxation Techniques, ACM Transactions on Algorithms, 6(3), Article number 56, 1–36, 2010.