The \(k\)-opt algorithm is one of the simplest and most widely used heuristics for solving the traveling salesman problem. Starting from an arbitrary tour, the \(k\)-opt algorithm improves the current tour in each iteration by exchanging up to \(k\) edges. The algorithm continues until no further improvement of this kind is possible. For a long time, it remained an open question how many iterations the \(k\)-opt algorithm might require for small values of \(k\), assuming the use of an optimal pivot rule. In this paper, we resolve this question for the cases \(k = 3\) and \(k = 4\) by proving that in both these cases an exponential number of iterations may be needed even if an optimal pivot rule is used. Combined with a recent result by Heimann, Hoang, and Hougardy (ICALP 2024), this provides a complete answer for all \(k \ge 3\) regarding the number of iterations the \(k\)-opt algorithm may require under an optimal pivot rule. In addition we establish an analogous exponential lower bound for the 2.5-opt algorithm, a variant that generalizes 2-opt and is a restricted version of 3-opt. All our results hold for both the general and the metric traveling salesman problem.

In the Strip Packing problem, we are given a vertical strip of fixed width and unbounded height, along with a set of axis-parallel rectangles. The task is to place all rectangles within the strip, without overlaps, while minimizing the height of the packing. This problem is known to be NP-hard. The Bottom-Left Algorithm is a simple and widely used heuristic for Strip Packing. Given a fixed order of the rectangles, it places them one by one, always choosing the lowest feasible position in the strip and, in case of ties, the leftmost one. Baker, Coffman, and Rivest proved in 1980 that the Bottom-Left Algorithm has approximation ratio 3 if the rectangles are sorted by decreasing width. For the past 45 years, no alternative ordering has been found that improves this bound. We introduce a new rectangle ordering and show that with this ordering the Bottom-Left Algorithm achieves a 13/6 approximation for the Strip Packing problem.

Abstract We study the Euclidean minimum weight perfect matching problem for n points in the plane. It is known that any deterministic approximation algorithm whose approximation ratio depends only on n requires at least $$\Omega (n \log n)$$ Ω ( n log n ) time. We propose such an algorithm for the Euclidean minimum weight perfect matching problem with runtime $$O(n\log n)$$ O ( n log n ) and show that it has approximation ratio $$O(n^{0.206})$$ O ( n 0.206 ) . This improves the so far best known approximation ratio of n /2. We also develop an $$O(n \log n)$$ O ( n log n ) algorithm for the Euclidean minimum weight perfect matching problem in higher dimensions and show it has approximation ratio $$O(n^{0.412})$$ O ( n 0.412 ) in all fixed dimensions.

The $k$-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most $k$ edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the $k$-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the $k$-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires $k \gg 1000$ and has a substantial gap. We show the two properties above for a much smaller value of $k$, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for $k \geq 17$ and the exponential running time for $k \geq 5$.

Abstract. The [Formula: see text]-Opt heuristic is a simple improvement heuristic for the traveling salesman problem. It starts with an arbitrary tour and then repeatedly replaces [Formula: see text] edges of the tour by [Formula: see text] other edges, as long as this yields a shorter tour. We will prove that for the 2-dimensional Euclidean traveling salesman problem with [Formula: see text] cities the approximation ratio of the [Formula: see text]-Opt heuristic is [Formula: see text]. This improves the upper bound of [Formula: see text] given by Chandra, Karloff, and Tovey in [ SIAM J. Comput., 28 (1999), pp. 1998–2029] and provides for the first time a nontrivial lower bound for the case [Formula: see text]. Our results not only hold for the Euclidean norm but extend to arbitrary [Formula: see text]-norms with [Formula: see text].

In Placement Legalization, it is often assumed that (almost) all standard cells possess the same height and can therefore be aligned in cell rows , which can then be treated independently. However, this is no longer true for recent technologies, where a substantial number of cells of double- or even arbitrary multiple-row height is to be expected. Due to interdependencies between the cell placements within several rows, the legalization task becomes considerably harder. In this article, we show how to optimize squared cell movement for pairs of adjacent rows comprising cells of single- as well as double-row height with a fixed left-to-right ordering in time 𝒪( n · log ( n )), where n denotes the number of cells involved. Opposed to prior works, we do not artificially bound the maximum cell movement and can guarantee to find an optimum solution. Our approach also allows us to include gridding and movebound constraints for the cells. Experimental results show an average percental decrease of over 26% in the total squared movement when compared to a legalization approach that fixes cells of more than single-row height after Global Placement.

In Placement Legalization, it is often assumed that (almost) all standard cells possess the same height and can therefore be aligned in cell rows, which can then be treated independently. However, this is no longer true for recent technologies, where a substantial number of cells of double- or even arbitrary multiple-row height is to be expected. Due to interdependencies between the cell placements within several rows, the legalization task becomes considerably harder. In this paper, we show how to optimize quadratic cell movement for pairs of adjacent rows comprising cells of single- as well as double-row height with a fixed left-to-right ordering in time $\mathcalO (n\cdotłog(n))$, whereby n denotes the number of cells involved. Opposed to prior works, we thereby do not artificially bound the maximum cell movement and can guarantee to find an optimum solution. Experimental results show an average percental decrease of over $26%$ in the total quadratic movement when compared to a legalization approach that fixes cells of more than single-row height after Global Placement.

Multipatterning technology used in 7-nm technology and beyond imposes more and more complex design rules on the layout of cells. The often nonlocal nature of these new design rules is a great challenge not only for human designers but also for existing algorithms. We present a new flow for automatic cell layout generation that is able to deal with these challenges by globally optimizing several design objectives simultaneously. Our transistor placement algorithm not only minimizes the total cell area but at the same time guarantees the routability of the cell and finds a best arrangement and folding of the transistors. Our routing engine computes a detailed routing of all nets simultaneously. It computes a netlength optimal routing using a mixed-integer programming formulation. Additional DFM constraints are added to this model to improve yield and reduce chip manufacturing costs. We present experimental results on current 7-nm designs. Our approach allows to compute optimized layouts within a few minutes, even for large complex cells. The algorithms are used for the design of logic cells compatible with a published 7-nm technology from a leading chip manufacturer where they meet manufacturability requirements and significantly reduced design turn around times.

Multi patterning technology used in 7nm technology and beyond imposes more and more complex design rules on the layout of cells. The often non local nature of these new design rules is a great challenge not only for human designers but also for existing algorithms. We present a new flow for the automatic cell layout that is able to deal with these challenges by globally optimizing several design objectives simultaneously. Our transistor placement algorithm not only minimizes the total cell area but simultaneously optimizes the routability of the cell and finds a best folding of the transistors. Our routing engine computes a detailed routing of all nets simultaneously. In a first step it computes an electrically correct routing using a mixed integer programming formulation. To improve yield and optimize DFM, additional constraints are added to this model.

In this paper we present BonnCell, our solution to compute leaf cell layouts in VLSI design. Our placement algorithm allows to find very compact solutions and uses an accurate target function to guarantee routability. The routing algorithm handles all nets simultaneously using a constraint generation MIP based approach. Finally, yield and electromigration properties are improved in a post-processing phase. Our approach considers design rules already during placement and routing, is able to treat gridless technologies, and easily adapts to new design rules and future technologies as for example double patterning in 14nm and beyond. The experimental results on current 22nm designs of our industry partner show significant improvements both in terms of design quality and turnaround time compared to manual designs done by experienced designers.

Abstract The Steiner tree problem is to find a shortest subgraph that spans a given set of vertices in a graph. This problem is known to be NP‐hard, and it is well known that a polynomial time 2‐approximation algorithm exists. In 1996, Zelikovsky suggested an approximation algorithm for the Steiner tree problem that is called the relative greedy algorithm. Until now the performance ratio of this algorithm has not been known. Zelikovsky provided 1.694 as an upper bound, and Gröpl, Hougardy, Nierhoff, and Prömel proved that 1.333 is a lower bound. In this article we improve the lower bound for the performance ratio of the relative greedy algorithm to 1.385. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 111–115 2006

Approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. Here we propose an approximation algorithm for the weighted matching problem in graphs which can be solved in polynomial time. The weighted matching problem is to find a matching in an edge weighted graph that has maximum weight. The first polynomial-time algorithm for this problem was given by Edmonds in 1965. The fastest known algorithm for the weighted matching problem has a running time of O ( nm + n 2 log n ). Many real world problems require graphs of such large size that this running time is too costly. Therefore, there is considerable need for faster approximation algorithms for the weighted matching problem. We present a linear-time approximation algorithm for the weighted matching problem with a performance ratio arbitrarily close to 2/3. This improves the previously best performance ratio of 1/2. Our algorithm is not only of theoretical interest, but because it is easy to implement and the constants involved are quite small it is also useful in practice.

The terminal Steiner tree problem is a special version of the Steiner tree problem, where a Steiner minimum tree has to be found in which all terminals are leaves. We prove that no polynomial time approximation algorithm for the terminal Steiner tree problem can achieve an approximation ratio less than (1−o(1))ln n unless NP has slightly superpolynomial time algorithms. Moreover, we present a polynomial time approximation algorithm for the metric version of this problem with a performance ratio of 2 ρ , where ρ denotes the best known approximation ratio for the Steiner tree problem. This improves the previously best known approximation ratio for the metric terminal Steiner tree problem of ρ +2.

A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case $n\choose 2$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g., planarity or k-colorability. A famous conjecture of Karp says that every nontrivial monotone graph property is elusive. We prove that a nonmonotone but hereditary graph property is elusive: perfectness.

MOTIVATION: The Dictionary of Interfaces in Proteins (DIP) is a database collecting the 3D structure of interacting parts of proteins that are called patches. It serves as a repository, in which patches similar to given query patches can be found. The computation of the similarity of two patches is time consuming and traversing the entire DIP requires some hours. In this work we address the question of how the patches similar to a given query can be identified by scanning only a small part of DIP. The answer to this question requires the investigation of the distribution of the similarity of patches. RESULTS: The score values describing the similarity of two patches can roughly be divided into three ranges that correspond to different levels of spatial similarity. Interestingly, the two iso-score lines separating the three classes can be determined by two different approaches. Applying a concept of the theory of random graphs reveals significant structural properties of the data in DIP. These can be used to accelerate scanning the DIP for patches similar to a given query. Searches for very similar patches could be accelerated by a factor of more than 25. Patches with a medium similarity could be found 10 times faster than by brute-force search.