We introduce and study a directed analogue of the weighted Tree Augmentation Problem (WTAP). In the weighted Directed Tree Augmentation Problem (WDTAP), we are given an oriented tree \(T = (V,A)\) and a set of directed links \(L \subseteq V \times V\) with positive costs. The goal is to select a minimum cost set of links which enters each fundamental dicut of \(T\) (cuts with one leaving and no entering tree arc). WDTAP captures the problem of covering a cross-free set family with directed links. It can also be used to solve weighted multi 2-TAP, in which we must cover the edges of an undirected tree at least twice. WDTAP can be approximated to within a factor of 2 using standard techniques. We provide an improved (\(1.75 + \varepsilon\))-approximation algorithm for WDTAP in the case where the links have bounded costs, a setting that has received significant attention forWTAP. To obtain this result, we discover a class of instances, called “willows”, for which the natural set covering LP is an integral formulation. We further introduce the notion of “visibly \(k\)-wide” instances which can be solved exactly using dynamic programming. Finally, we show how to leverage these tractable cases to obtain an improved approximation ratio via an elaborate structural analysis of the tree.

We revisit the a priori TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the a priori TSP, we are given a metric space $(V,c)$ and an activation probability $p(v)$ for each customer $v\in V$. We ask for a TSP tour $T$ for $V$ that minimizes the expected length after cutting $T$ short by skipping the inactive customers. All known approximation algorithms select a nonempty subset $S$ of the customers and construct a master route solution, consisting of a TSP tour for $S$ and two edges connecting every customer $v\in V\setminus S$ to a nearest customer in $S$. We address the following questions. If we randomly sample the subset $S$, what should be the sampling probabilities? How much worse than the optimum can the best master route solution be? The answers to these questions (we provide almost matching lower and upper bounds) lead to improved approximation guarantees: less than 3.1 with randomized sampling, and less than 5.9 with a deterministic polynomial-time algorithm.

We study the weighted k-Set Packing problem, which is defined as follows: Given a collection S of sets, each of cardinality at most k, together with a positive weight function , the task is to compute a sub-collection A ⊆ S of maximum total weight such that the sets in A are pairwise disjoint. For k ≤ 2, the weighted k-Set Packing problem reduces to the Maximum Weight Matching problem, and can thus be solved in polynomial time [5]. However, for k ≥ 3, already the special case of unit weights, the unweighted k-Set Packing problem, becomes NP-hard as it generalizes the 3D-matching problem [8]. The state-of-the-art algorithms for both the unweighted and the weighted k-Set Packing problem rely on local search. In the unweighted setting, the best known approximation guarantee is [6]. For general weights, Berman's algorithm SquareImp, which yields a , has remained unchallenged for twenty years [1]. Only recently, Neuwohner managed to improve on this by obtaining approximation guarantees of with limk → ∞ ∊k =0 [10]. She further showed her result to be asymptotically best possible in that no algorithm considering local improvements of logarithmically bounded size with respect to some fixed power of the weight function can yield an approximation guarantee better than [10]. In this paper, we finally show how to beat the threshold of for the weighted k-Set Packing problem by Ω(k). We achieve this by combining local search with the application of a black box algorithm for the unweighted k-Set Packing problem to carefully chosen sub-instances. In doing so, we do not only manage to link the approximation ratio for general weights to the one achievable in the unweighted case: In contrast to previous works, which yield an improvement over Berman's long-standing result of either only for large values of k ≥ 2 · 105 [10], or by less than 6 · 10-7 [9], we achieve guarantees of at most for all k ≥ 4.

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.

We introduce the problem of finding a set $B$ of $k$ points in $[0,1]^n$ such that the expected cost of the cheapest point in $B$ that dominates a random point from $[0,1]^n$ is minimized. We study the case where the coordinates of the random points are independently distributed and the cost function is linear. This problem arises naturally in various application areas where customers' requests are satisfied based on predefined products, each corresponding to a subset of features. We show that the problem is NP-hard already for $k=2$ when each coordinate is drawn from $\{0,1\}$, and obtain an FPTAS for general fixed $k$ under mild assumptions on the distributions.

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.

In this paper, we consider the task of computing an independent set of maximum weight in a given d-claw free graph G = (V,E) equipped with a positive weight function w:V → ℝ^+. Thereby, d ≥ 2 is considered a constant. The previously best known approximation algorithm for this problem is the local improvement algorithm SquareImp proposed by Berman [Berman, 2000]. It achieves a performance ratio of d/2+ε in time 𝒪(|V(G)|^(d+1)⋅(|V(G)|+|E(G)|)⋅(d-1)²⋅ (d/(2ε)+1)²) for any ε > 0, which has remained unimproved for the last twenty years. By considering a broader class of local improvements, we obtain an approximation ratio of d/2-(1/63,700,992)+ε for any ε > 0 at the cost of an additional factor of 𝒪(|V(G)|^(d-1)²) in the running time. In particular, our result implies a polynomial time d/2-approximation algorithm. Furthermore, the well-known reduction from the weighted k-Set Packing Problem to the Maximum Weight Independent Set Problem in k+1-claw free graphs provides a (k+1)/2 -(1/63,700,992)+ε-approximation algorithm for the weighted k-Set Packing Problem for any ε > 0. This improves on the previously best known approximation guarantee of (k+1)/2 + ε originating from the result of Berman [Berman, 2000].