Search

We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Williamson et al. in Combinatorica 15(3):435–454, 1995. https://doi.org/10.1007/BF01299747). Williamson et al. prove an approximation ratio of two for connectivity augmentation problems where the connectivity requirements can be specified by uncrossable functions. They state: "Extending our algorithm to handle non-uncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar... A larger open issue is to explore further the power of the primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems." Our main result proves that the primal-dual algorithm of Williamson et al. achieves an approximation ratio of 16 for a class of functions that generalizes the notion of an uncrossable function. There exist instances that can be handled by our methods where none of the optimal dual solutions has a laminar support. We present three applications of our main result to problems in the area of network design. (1) A 16 -approximation algorithm for augmenting a family of small cuts of a graph G. The previous best approximation ratio was O (log | V (G) |) . (2) A 16 · ⌈ k / u min ⌉ -approximation algorithm for the Cap-k-ECSS problem which is as follows: Given an undirected graph G = (V , E) with edge costs c ∈ Q ≥ 0 E and edge capacities u ∈ Z ≥ 0 E , find a minimum-cost subset of the edges F ⊆ E such that the capacity of any cut in (V, F) is at least k; u min (respectively, u max ) denotes the minimum (respectively, maximum) capacity of an edge in E, and w.l.o.g. u max ≤ k . The previous best approximation ratio was min (O (log | V |) , k , 2 u max) . (3) A 20 -approximation algorithm for the model of (p, 2)-Flexible Graph Connectivity. The previous best approximation ratio was O (log | V (G) |) , where G denotes the input graph. [ABSTRACT FROM AUTHOR]

Minimizing the weighted completion time of jobs in the unrelated parallel machines model is a fundamental scheduling problem. The first (3 / 2 - c) –approximation algorithm for this problem, for some constant c > 0 , was obtained in the work of Bansal et al. (SIAM J Comput, 2021). A key ingredient in this work was the first dependent-rounding algorithm with a certain guaranteed amount of negative correlation. We improve upon this guaranteed amount from 1/108 to 1/27, thus also improving upon the constant c in the algorithms of Bansal et al. and Li (SIAM J Comput, 2020) for weighted completion time. Given the now-ubiquitous role played by dependent rounding in scheduling and combinatorial optimization, our improved dependent rounding is also of independent interest. [ABSTRACT FROM AUTHOR]

The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximation algorithms with guarantees below 2 for both TAP and CAP, culminating in the currently best approximation factor for both problems of 1.393 through quite sophisticated techniques. We present a new and arguably simple matching-based method for the well-known special case of leaf-to-leaf instances. Combining our work with prior techniques, we readily obtain a (4 / 3 + ε) -approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a 4 / 3 -guarantee was only known for Leaf-to-Leaf TAP instances on trees of height 2. Moreover, when combining our technique with a recently introduced stack analysis approach, which is part of the above-mentioned 1.393-approximation, we can further improve the approximation factor to 1.29, obtaining for the first time a factor below 4 3 for a nontrivial class of TAP/CAP instances. [ABSTRACT FROM AUTHOR]

We present approximation algorithms for several network design problems in the model of flexible graph connectivity (Adjiashvili et al., in: IPCO, pp 13–26, 2020, Math Program 1–33, 2021). Let k ≥ 1 , p ≥ 1 and q ≥ 0 be integers. In an instance of the (p, q)-Flexible Graph Connectivity problem, denoted (p , q) -FGC , we have an undirected connected graph G = (V , E) , a partition of E into a set of safe edges S and a set of unsafe edges U , and nonnegative costs c : E → R ≥ 0 on the edges. A subset F ⊆ E of edges is feasible for the (p , q) -FGC problem if for any set F ′ ⊆ U with | F ′ | ≤ q , the subgraph (V , F \ F ′) is p-edge connected. The algorithmic goal is to find a feasible solution F that minimizes c (F) = ∑ e ∈ F c e . We present a simple 2-approximation algorithm for the (1 , 1) -FGC problem via a reduction to the minimum-cost rooted 2-arborescence problem. This improves on the 2.527-approximation algorithm of Adjiashvili et al. Our 2-approximation algorithm for the (1 , 1) -FGC problem extends to a (k + 1) -approximation algorithm for the (1 , k) -FGC problem. We present a 4-approximation algorithm for the (k , 1) -FGC problem, and an O (q log | V |) -approximation algorithm for the (p , q) -FGC problem. Finally, we improve on the result of Adjiashvili et al. for the unweighted (1 , 1) -FGC problem by presenting a 16/11-approximation algorithm. The (p , q) -FGC problem is related to the well-known Capacitatedk-Connected Subgraph problem (denoted Cap- k -ECSS ) that arises in the area of Capacitated Network Design. We give a min (k , 2 u max) -approximation algorithm for the Cap- k -ECSS problem, where u max denotes the maximum capacity of an edge. [ABSTRACT FROM AUTHOR]

In this paper, we study the following robust optimization problem. Given a set family representing feasibility and candidate objective functions, we choose a feasible set, and then an adversary chooses one objective function, knowing our choice. The goal is to find a randomized strategy (i.e., a probability distribution over the feasible sets) that maximizes the expected objective value in the worst case. This problem is fundamental in wide areas such as artificial intelligence, machine learning, game theory, and optimization. To solve the problem, we provide a general framework based on the dual linear programming problem. In the framework, we utilize the ellipsoid algorithm with the approximate separation algorithm. We prove that there exists an α -approximation algorithm for our robust optimization problem if there exists an α -approximation algorithm for finding a (deterministic) feasible set that maximizes a nonnegative linear combination of the candidate objective functions. Using our result, we provide approximation algorithms for the max–min fair randomized allocation problem and the maximum cardinality robustness problem with a knapsack constraint. [ABSTRACT FROM AUTHOR]

In recent years, variational quantum algorithms such as the Quantum Approximation Optimization Algorithm (QAOA) have gained popularity as they provide the hope of using NISQ devices to tackle hard combinatorial optimization problems. It is, however, known that at low depth, certain locality constraints of QAOA limit its performance. To go beyond these limitations, a non-local variant of QAOA, namely recursive QAOA (RQAOA), was proposed to improve the quality of approximate solutions. The RQAOA has been studied comparatively less than QAOA, and it is less understood, for instance, for what family of instances it may fail to provide high-quality solutions. However, as we are tackling NP-hard problems (specifically, the Ising spin model), it is expected that RQAOA does fail, raising the question of designing even better quantum algorithms for combinatorial optimization. In this spirit, we identify and analyze cases where (depth-1) RQAOA fails and, based on this, propose a reinforcement learning enhanced RQAOA variant (RL-RQAOA) that improves upon RQAOA. We show that the performance of RL-RQAOA improves over RQAOA: RL-RQAOA is strictly better on these identified instances where RQAOA underperforms and is similarly performing on instances where RQAOA is near-optimal. Our work exemplifies the potentially beneficial synergy between reinforcement learning and quantum (inspired) optimization in the design of new, even better heuristics for complex problems. [ABSTRACT FROM AUTHOR]

Submodular maximization is a NP-hard combinatorial optimization problem regularly used in machine learning and data mining with large-scale data sets. To quantify the running time of approximation algorithms, the query complexity and adaptive complexity are two important measures, where the adaptivity of an algorithm is the number of sequential rounds it makes when each round can execute polynomially many function evaluations in parallel. These two concepts reasonably quantify the efficiency and practicability of parallel computation. In this paper, we consider the problem of maximizing a nonnegative monotone DR-submodular function over a bounded integer lattice with a cardinality constraint in a value oracle model. Prior to our work, Soma and Yoshida (Math Program 172:539–563, 2018) have studied this problem and present an approximation algorithm with almost optimal approximate ratio and the same adaptivity and query complexity. We develop two novel algorithms, called low query algorithm and low adaptivity algorithm, which have approximation ratios equal to Soma and Yoshida (2018), but reach a new record of query complexity and adaptivity. As for methods, compared with the threshold greedy in Soma and Yoshida (2018), the low query algorithm reduces the number of possible thresholds and improves both the adaptivity and query complexity. The low adaptivity algorithm further integrates a vector sequencing technique to accelerate adaptive complexity in an exponential manner while only making logarithmic sacrifices on oracle queries. [ABSTRACT FROM AUTHOR]

The minimum weighted vertex cover (MWVC) problem is to find a subset of vertices that can cover all the edges of the network and minimize the sum of the vertex weights in the vertex subset. MWVC is a generalization of the minimum vertex cover (MVC) problem and can be regarded as a combinatorial optimization problem. This paper proposes an evolutionary algorithm based on the snowdrift game to solve the MWVC problem. We use the evolutionary algorithm framework, and the snowdrift game is combined to construct and improve the initial solution. First, the network's vertex is regarded as an intelligent agent, and each vertex and its neighbors play a snowdrift game to form an initial solution. Then local search and global search are used to improve the initial solution. The solution is improved according to the proposed score function in the local search stage to obtain a better MWVC solution. The evolutionary algorithm is used in the global search stage to escape the local optimum. Experiments on different networks show that the proposed algorithm are effective on weighted networks. [ABSTRACT FROM AUTHOR]

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement– odd , even , or unconstrained –of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparseT-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem. [ABSTRACT FROM AUTHOR]

In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms formulated in the circuit model of computation onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (Optimal qubit assignment and routing via integer programming, 2021, http://arxiv.org/abs/2106.06446), we formulate the allocation subproblem as a binary linear program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm which runs much faster than the exact approach and typically is able to determine solutions close to the optimum. We present numerical results for the fully integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of artificial gates and output circuit depth when compared to various state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods. [ABSTRACT FROM AUTHOR]

Ensuring fairness in computational problems has emerged as a key topic during recent years, buoyed by considerations for equitable resource distributions and social justice. It is possible to incorporate fairness in computational problems from several perspectives, such as using optimization, game-theoretic or machine learning frameworks. In this paper we address the problem of incorporation of fairness from a combinatorial optimization perspective. We formulate a combinatorial optimization framework, suitable for analysis by researchers in approximation algorithms and related areas, that incorporates fairness in maximum coverage problems as an interplay between two conflicting objectives. Fairness is imposed in coverage by using coloring constraints that minimizes the discrepancies between number of elements of different colors covered by selected sets; this is in contrast to the usual discrepancy minimization problems studied extensively in the literature where (usually two) colors are not given a priori but need to be selected to minimize the maximum color discrepancy of each individual set. Our main results are a set of randomized and deterministic approximation algorithms that attempts to simultaneously approximate both fairness and coverage in this framework. [ABSTRACT FROM AUTHOR]

We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement upon the classical tour partitioning algorithm by Haimovich and Rinnooy Kan (Math Oper Res 10:527–542, 1985) and Altinkemer and Gavish (Oper Res Lett 6:149–158, 1987). [ABSTRACT FROM AUTHOR]

The Unsplittable Flow on a Path (UFP) problem has garnered considerable attention as a challenging combinatorial optimization problem with notable practical implications. Steered by its pivotal applications in power engineering, the present work formulates a novel generalization of UFP, wherein demands and capacities in the input instance are monotone step functions over the set of edges. As an initial step towards tackling this generalization, we draw on and extend ideas from prior research to devise a quasi-polynomial time approximation scheme under the premise that the demands and capacities lie in a quasi-polynomial range. Second, retaining the same assumption, an efficient logarithmic approximation is introduced for the single-source variant of the problem. Finally, we round up the contributions by designing a (kind of) black-box reduction that, under some mild conditions, allows to translate LP-based approximation algorithms for the studied problem into their counterparts for the Alternating Current Optimal Power Flow problem—a fundamental workflow in operation and control of power systems. [ABSTRACT FROM AUTHOR]

In this paper, we consider the heterogeneous Chinese postman problem (the HCPP), which generalizes the k-Chinese postman problem. Specifically, given a weighted graph G = (V , E ; w ; r) with length function w : E → R + satisfying the triangle inequality, a fixed depot r ∈ V , and k vehicles having k nonuniform speeds λ 1 , λ 2 , … , λ k , respectively, it is asked to find k tours in G for these k vehicles, each starting at the same depot r, and collectively traversing each edge in E at least once. The objective is to minimize the maximum completion time of vehicles, where the completion time of a vehicle is its total travel length divided by its speed. The main contribution of our paper is to show the following two results. (1) Given any small constant δ > 0 , we design a 20.8765 (1 + δ) -approximation algorithm to solve the HCPP, where the running time required is bounded by a polynomial in the input size and 1 δ . (2) We present a (1 + Δ - 1 / k) -approximation algorithm to solve the HCPP in cubic time, where Δ is the ratio of the largest vehicle speed to the smallest one. [ABSTRACT FROM AUTHOR]

In this paper, we address the line-capacitated minimum Steiner tree problem (the Lc-MStT problem, for short), which is a variant of the (Euclidean) capacitated minimum Steiner tree problem and defined as follows. Given a set X = { r 1 , r 2 , ... , r n } of n terminals in R 2 , a demand function d : X → N and a positive integer C, we are asked to determine the location of a line l and a Steiner tree T l to interconnect these n terminals in X and at least one point located on this line l such that the total demand of terminals in each maximal subtree (of T l ) connected to the line l, where the terminals in such maximal subtree are all located at the same side of this line l, does not exceed the bound C. The objective is to minimize total weight ∑ e ∈ T l w (e) of such a Steiner tree T l among all line-capacitated Steiner trees mentioned-above, where weight w (e) = 0 if two endpoints of that edge e ∈ T l are located on the line l and otherwise weight w(e) is the Euclidean distance between two endpoints of that edge e ∈ T l . In addition, when this line l is as an input in R 2 and ∑ r ∈ X d (r) ≤ C holds, we refer to this version as the 1-line-fixed minimum Steiner tree problem (the 1Lf-MStT problem, for short). We obtain three main results. (1) Given a ρ st -approximation algorithm to solve the Euclidean minimum Steiner tree problem and a ρ 1 L f -approximation algorithm to solve the 1Lf-MStT problem, respectively, we design a (ρ st ρ 1 L f + 2) -approximation algorithm to solve the Lc-MStT problem. (2) Whenever demand of each terminal r ∈ X is less than C 2 , we provide a (ρ 1 L f + 2) -approximation algorithm to resolve the Lc-MStT problem. (3) Whenever demand of each terminal r ∈ X is at least C 2 , using the Edmonds' algorithm to solve the minimum weight perfect matching as a subroutine, we present an exact algorithm in polynomial time to resolve the Lc-MStT problem. [ABSTRACT FROM AUTHOR]

In this paper, motivated by many practical applications, we address the 1-line minimum rectilinear Steiner tree (1L-MRStT) problem, which is a variation of the Euclidean minimum rectilinear Steiner tree problem. More specifically, given n points in the Euclidean plane R 2 , it is asked to find the location of a line l and a Steiner tree T(l), consisting only of vertical and horizontal line segments plus several successive segments located on this line l, to interconnect these n points and at least one point located on the line l, the objective is to minimize total weight of this Steiner tree T(l), i.e., min { ∑ u v ∈ T (l) w (u , v) | T(l) is a Steiner tree mentioned-above } , where we define a weight w (u , v) = 0 if the two endpoints u and v of that edge u v ∈ T (l) is located on the line l and otherwise we define a weight w(u, v) as the rectilinear distance between the two endpoints u and v of that edge u v ∈ T (l) . Given a line l as an input in R 2 , we denote this problem as the 1-line-fixed minimum rectilinear Steiner tree (1LF-MRStT) problem; Furthermore, when the Steiner points of T(l) are all located on the fixed line l, we recall this problem as the 1-line-fixed-constrained minimum rectilinear Steiner tree (1LFC-MRStT) problem. We provide three following main contributions. (1) We design an algorithm A C to optimally solve the 1LFC-MRStT problem, where the algorithm A C runs in time O (n log n) ; (2) We prove that this algorithm A C is a 1.5-approximation algorithm to solve the 1LF-MRStT problem; (3) Combining the algorithm A C for many times and a key lemma proved by some techniques of computational geometry, we present a 1.5-approximation algorithm to solve the 1L-MRStT problem, where this algorithm runs in time O (n 3 log n) , and we finally provide another approximation algorithm to solve a special version of the 1L-MRStT problem, where that new algorithm runs in lower time O (n 2 log n) . [ABSTRACT FROM AUTHOR]

This paper considers approximation algorithms for generalized k-median problems. These problems can be informally described as k-median with a constant number of extra constraints, and includes k-median with outliers, and knapsack median. Our first contribution is a pseudo-approximation algorithm for generalized k-median that outputs a 6.387-approximate solution, with a constant number of fractional variables. The algorithm builds on the iterative rounding framework introduced by Krishnaswamy, Li, and Sandeep for k-median with outliers as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). The main technical innovation is allowing richer constraint sets in the iterative rounding and using the structure of the resulting extreme points. Using our pseudo-approximation algorithm, we give improved approximation algorithms for k-median with outliers and knapsack median. This involves combining our pseudo-approximation with pre- and post-processing steps to round a constant number of fractional variables at a small increase in cost. Our algorithms achieve approximation ratios 6.994+ϵ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$6.994 + \epsilon $$\end{document} and 6.387+ϵ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$6.387 + \epsilon $$\end{document} for k-median with outliers and knapsack median, respectively. These improve on the best-known approximation ratio 7.081+ϵ\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$7.081 + \epsilon $$\end{document} for both problems as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). [ABSTRACT FROM AUTHOR]

Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph G = (V , E) with edge costs c ∈ R ≥ 0 E , a root r ∈ V and k terminals K ⊆ V , we need to output the minimum-cost arborescence in G that contains an r → t path for every t ∈ K . Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time O (log 2 k / log log k) -approximation Algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general Degree-Bounded Directed Steiner Tree (DB-DST) problem, where we are additionally given a degree bound d v on each vertex v ∈ V , and we require that every vertex v in the output tree has at most d v children. We give a quasi-polynomial time (O (log n log k) , O (log 2 n)) -bicriteria approximation: The Algorithm produces a solution with cost at most O (log n log k) times the cost of the optimum solution that violates the degree constraints by at most a factor of O (log 2 n) . This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of O (log 2 n) is an O (log n) -factor away from the approximation lower bound of Ω (log n) from the set-cover hardness. The hardness result holds even on the special case of the Degree-Bounded Group Steiner Tree problem on trees (DB-GST-T). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an (O (log n log k) , O (log n)) -bicriteria approximation Algorithm for DB-GST-T. [ABSTRACT FROM AUTHOR]

We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of n tasks and m resources, where each task j uses some subset of the resources. Tasks have random sizes X j , and our goal is to non-adaptively select t tasks to minimize the expected maximum load over all resources, where the load on any resource i is the total size of all selected tasks that use i. For example, when resources are points and tasks are intervals in a line, we obtain an O (log log m) -approximation algorithm. Our technique is also applicable to other problems with some geometric structure in the relation between tasks and resources; e.g., packing paths, rectangles, and "fat" objects. Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show that this LP has an Ω (log ∗ m) integrality gap, even for the problem of selecting intervals on a line; here log ∗ m is the iterated logarithm function. [ABSTRACT FROM AUTHOR]

In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the root of the tree such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1.For the special case when all terminals have equal demands, a long line of research culminated in a quasi-polynomial time approximation scheme [Jayaprakash and Salavatipour, TALG 2023] and a polynomial time approximation scheme [Mathieu and Zhou, TALG 2023].In this work, we study the general case when the terminals have arbitrary demands. Our main contribution is a polynomial time (1.5+ϵ)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(1.5+\epsilon )$$\end{document}-approximation algorithm for the UCVRP on trees. This is the first improvement upon the 2-approximation algorithm more than 30 years ago. Our approximation ratio is essentially best possible, since it is NP-hard to approximate the UCVRP on trees to better than a 1.5 factor. [ABSTRACT FROM AUTHOR]

We study the generalized minimum Manhattan network (GMMN) problem: given a set P of pairs of points in the Euclidean plane R 2 , we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the L 1 metric (a so-called Manhattan path) for each pair in P . This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in P , and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach. [ABSTRACT FROM AUTHOR]

Motivated by the celebrated paper of Hooker (J Heuristics 1(1): 33–42, 1995) published in the first issue of this journal, and by the relative lack of progress of both approximation algorithms and fixed-parameter algorithms for the classical decision and optimization problems related to covering edges by vertices, we aimed at developing an approach centered in augmenting our intuition about what is indeed needed. We present a case study of a novel design methodology by which algorithm weaknesses will be identified by computer-based and fixed-parameter tractable algorithmic challenges on their performance. Comprehensive benchmarkings on all instances of small size then become an integral part of the design process. Subsequent analyses of cases where human intuition "fails", supported by computational testing, will then lead to the development of new methods by avoiding the traps of relying only on human perspicacity and ultimately will improve the quality of the results. Consequently, the computer-aided design process is seen as a tool to augment human intuition. It aims at accelerating and foster theory development in areas such as graph theory and combinatorial optimization since some safe reduction rules for pre-processing can be mathematically proved via theorems. This approach can also lead to the generation of new interesting heuristics. We test our ideas with a fundamental problem in graph theory that has attracted the attention of many researchers over decades, but for which seems it seems to be that a certain stagnation has occurred. The lessons learned are certainly beneficial, suggesting that we can bridge the increasing gap between theory and practice by a more concerted approach that would fuel human imagination from a data-driven discovery perspective. [ABSTRACT FROM AUTHOR]

In this paper, we propose to study a wide class of combinatorial optimization problems called combinatorial optimization problems with labelling. First, we give a combinatorial method to deal with the labelling version of some classical combinatorial optimization problems including minimum vertex cover, maximum independent set, minimum dominating set and minimum set cover, and convert the labelling problems into the original problems by polynomial-time reduction. We show that, although the labelling version of these problem seems more universal than their original counterparts, they are actually equivalent to the corresponding original problem from an algorithmic point of view. Moreover, we generalize the greedy approach for solving submodular cover problem to its labelling version, and as simple applications of our new method, we use it to solve the labelling versions of the minimum weighted spanning tree and connected vertex cover problem in a unified way. [ABSTRACT FROM AUTHOR]

In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal, so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for k ≥ 3 is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrák (Proceedings of the forty-sixth annual ACM symposium on theory of computing, STOC, 2014) while the best known inapproximability result due to Angelidakis et al. (Integer programming and combinatorial optimization, IPCO, 2017) rules out efficient algorithms to achieve an approximation factor less than 1.2 under the unique games conjecture (UGC). In this work, we improve the lower bound to 1.20016 under UGC by constructing an integrality gap instance for the CKR relaxation. The CKR relaxation embeds the graph into a simplex and it is known that its integrality gap translates to inapproximability under UGC. A technical challenge in improving the integrality gap has been the lack of geometric tools to understand higher-dimensional simplices. Our instance is a non-trivial 3-dimensional instance that overcomes this technical challenge. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. We believe that this technique could be exploited further to construct instances with larger integrality gap. One of the ingredients of our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrák (Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, SODA, 2015) that might be of independent combinatorial interest. [ABSTRACT FROM AUTHOR]

We study the capacitated assortment and price optimization problem, where a retailer sells categories of substitutable products subject to a capacity constraint. The goal of the retailer is to determine the subset of products as well as their selling prices so as to maximize the expected revenue. We model the customer purchase behavior using the nested logit model and formulate this problem as a non-linear binary integer program. For this NP-complete problem, we show that there exists a pseudo polynomial time approximation scheme that finds its ϵ -approximate solution. We first convert the original problem into an equivalent fixed point problem. We then show that finding an ϵ -approximate solution to the fixed point problem can be achieved by binary search, where a non-linear auxiliary problem is repeatedly approximated by a dynamic programing based algorithm involving an approximation to a series of multiple-choice parametric knapsack problems. For the special case when the capacity constraints are cardinal and nest-specific, we develop an algorithm that finds the optimal solution in strongly polynomial time. Moreover, our algorithm can be directly applied to find an ϵ -approximate solution to the capacitated assortment optimization problem under the nested logit model, which is the first approximate algorithm that is polynomial with respect to the number of nests in the literature. [ABSTRACT FROM AUTHOR]

We consider a stochastic variant of the packing-type integer linear programming problem, which contains random variables in the objective vector. We are allowed to reveal each entry of the objective vector by conducting a query, and the task is to find a good solution by conducting a small number of queries. We propose a general framework of adaptive and non-adaptive algorithms for this problem, and provide a unified methodology for analyzing the performance of those algorithms. We also demonstrate our framework by applying it to a variety of stochastic combinatorial optimization problems such as matching, matroid, and stable set problems. [ABSTRACT FROM AUTHOR]

We present a 7 4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any given MAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a 7 4 approximation algorithm for a well-structured MAP instance. The algorithm starts with a min-cost 2-edge cover and then applies ear-augmentation steps. We analyze the cost of the ear-augmentations using an approach similar to the one proposed by Vempala and Vetta for the (unweighted) min-size 2-ECSS problem (in: Jansen and Khuller (eds.) Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Proceedings, LNCS 1913, pp.262–273, Springer, Berlin, 2000). [ABSTRACT FROM AUTHOR]

We study the Maximum Cardinality Matching (MCM) and the Maximum Weight Matching (MWM) problems, on trees and on some special classes of graphs, in the online preemptive and the incremental graph models. In the Online Preemptive model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. If accepted, then the adjacent edges are discarded, and all rejections are permanent. In this model, the complexity of the problems is settled for deterministic algorithms (McGregor, in: Proceedings of the 8th international workshop on approximation, randomization and combinatorial optimization problems, and proceedings of the 9th international conference on randomization and computation: algorithms and techniques, APPROX'05/RANDOM'05, Springer, Berlin, pp. 170–181, 2005; Varadaraja, in: Automata, languages and programming: 38th international colloquium, ICALP 2011, Zurich, Switzerland, proceedings, part I, pp. 379–390, 2011. https://doi.org/10.1007/978-3-642-22006-7%5f32). Epstein et al. (in: 30th international symposium on theoretical aspects of computer science, STACS 2013, Kiel, Germany, pp. 389–399, 2013. https://doi.org/10.4230/LIPIcs.STACS.2013.389) gave a 5.356-competitive randomized algorithm for MWM, and also proved a lower bound on the competitive ratio of (1 + ln 2) ≈ 1.693 for MCM. The same lower bound applies for MWM. In the Incremental Graph model, at each step an edge is added to the graph, and the algorithm is supposed to quickly update its current matching. Gupta (in: 34th international conference on foundation of software technology and theoretical computer science, FSTTCS 2014, 15–17 Dec 2014, New Delhi, India, pp. 227–239, 2014. https://doi.org/10.4230/LIPIcs.FSTTCS.2014.227) proved that for any ϵ ≤ 1 / 2 , there exists an algorithm that maintains a (1 + ϵ) -approximate MCM for an incremental bipartite graph in an amortized update time of O log 2 n ϵ 4 . No (2 - ϵ) -approximation algorithm with a worst case update time of O(1) is known in this model, even for special classes of graphs. In this paper we show that some of the results can be improved for trees, and for some special classes of graphs. In the online preemptive model, we present a 64 / 33-competitive randomized algorithm (which uses only two bits of randomness) for MCM on trees. Inspired by the above mentioned algorithm for MCM, we present the main result of the paper, a randomized algorithm for MCM with a worst case update time of O(1), in the incremental graph model, which is 3 / 2-approximate (in expectation) on trees, and 1.8-approximate (in expectation) on general graphs with maximum degree 3. Note that this algorithm works only against an oblivious adversary. We derandomize this algorithm, and give a (3 / 2 + ϵ) -approximate deterministic algorithm for MCM on trees, with an amortized update time of O (1 / ϵ) . We also present a minor result for MWM in the online preemptive model, a 3-competitive randomized algorithm (that uses only O(1) bits of randomness) on growing trees (where the input revealed upto any stage is always a tree, i.e. a new edge never connects two disconnected trees). [ABSTRACT FROM AUTHOR]

The classical algorithm of Agrawal et al. (SIAM J Comput 24(3):440–456, 1995), stated in the setting of the primal-dual schema by Goemans and Williamson (SIAM J Comput 24(2):296–317, 1995) uses the undirected cut relaxation for the Steiner forest problem. Its approximation ratio is 2 - 1 k , where k is the number of terminal pairs. A variant of this algorithm more recently proposed by Könemann et al. (SIAM J Comput 37(5):1319–1341, 2008) is based on the lifted cut relaxation. In this paper, we continue this line of work and consider the bidirected cut relaxation for the Steiner forest problem, which lends itself to a novel algorithmic idea yielding the same approximation ratio as the classical algorithm. In doing so, we introduce an extension of the primal-dual schema in which we run two different phases to satisfy connectivity requirements in both directions. This reveals more about the combinatorial structure of the problem. In particular, there are examples on which the classical algorithm fails to give a good approximation, but the new algorithm finds a near-optimal solution. [ABSTRACT FROM AUTHOR]

In this paper, we propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a (1 - ϵ) -approximate solution with a running time significantly faster than most known exact algorithms. The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. More precisely, we show that we can solve the weighted matroid intersection problem via solving W instances of the unweighted matroid intersection problem, where W is the largest given weight, assuming that all given weights are integral. Furthermore, we can find a (1 - ϵ) -approximate solution via solving O (ϵ - 1 log r) instances of the unweighted matroid intersection problem, where r is the smaller rank of the two given matroids. Our algorithms make use of the weight-splitting approach of Frank (J Algorithms 2(4):328–336, 1981) and the geometric scaling scheme of Duan and Pettie (J ACM 61(1):1, 2014). Our algorithms are simple and flexible: they can be adapted to special cases of the weighted matroid intersection problem, using specialized unweighted matroid intersection algorithms. In addition, we give a further application of our decomposition technique: we solve efficiently the rank-maximal matroid intersection problem, a problem motivated by matching problems under preferences. [ABSTRACT FROM AUTHOR]

In robust combinatorial optimization with discrete uncertainty, approximation algorithms based on constructing a single scenario representing the whole uncertainty set are frequently used. One is the midpoint method, which uses the average case scenario. It is known to be an N-approximation, where N is the number of scenarios. In this paper, we present a linear program to construct a representative scenario for the uncertainty set, which gives an approximation guarantee that is at least as good as for previous methods. We further employ hyper heuristic techniques operating over a space of preprocessing and aggregation steps to evolve algorithms that construct alternative representative single scenarios for the uncertainty set. In numerical experiments on the selection problem we demonstrate that our approaches can improve the approximation guarantee of the midpoint approach by more than 20%. [ABSTRACT FROM AUTHOR]

We outline a relatively new research agenda aiming at building a new approximation paradigm by matching two distinct domains, the polynomial approximation and the exact solution ofNP-hard problems by algorithms with guaranteed and non-trivial upper complexity bounds. We show how one can design approximation algorithms achieving ratios that are “forbidden” in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower than that of an exact computation. [ABSTRACT FROM AUTHOR]

In the partial degree bounded edge packing problem (PDBEP), the input is an undirected graph G=(V,E) with capacity cv∈N on each vertex v. The objective is to find a feasible subgraph G′=(V,E′) maximizing |E′|, where G′ is said to be feasible if for each e={u,v}∈E′, degG′(u)≤cu or degG′(v)≤cv. In the weighted version of the problem, additionally each edge e∈E has a weight w(e) and we want to find a feasible subgraph G′=(V,E′) maximizing ∑e∈E′w(e). The problem is already NP-hard if cv=1 for all v∈V (Zhang in: Proceedings of the joint international conference on frontiers in algorithmics and algorithmic aspects in information and management, FAW-AAIM 2012, Beijing, China, May 14-16, pp 359-367, 2012). In this paper, we introduce a generalization of the PDBEP problem. We let the edges have weights as well as demands, and we present the first constant-factor approximation algorithms for this problem. Our results imply the first constant-factor approximation algorithm for the weighted PDBEP problem, improving the result of Aurora et al. (FAW-AAIM 2013) who presented an O(logn)-approximation for the weighted case. We also study the weighted PDBEP problem on hypergraphs and present a constant factor approximation if the maximum degree of the hypergraph is bounded above by a constant. We study a generalization of the weighted PDBEP problem with demands where each edge additionally specifies whether it requires at least one, or both its end-points to not exceed the capacity. The objective is to pick a maximum weight subset of edges. We give a constant factor approximation for this problem. We also present a PTAS for the weighted PDBEP problem with demands on H-minor free graphs, if the demands on the edges are bounded by polynomial. We show that the PDBEP problem is APX-hard even for bipartite graphs with cv=1,∀v∈V and having degree at most 3. [ABSTRACT FROM AUTHOR]

We are given an interval graph G=(V,E) where each interval I∈V has a weight wI∈Q+. The goal is to color the intervals V with an arbitrary number of color classes C1,C2,…,Ck such that ∑i=1kmaxI∈CiwI is minimized. This problem, called max-coloring interval graphs or weighted coloring interval graphs, contains the classical problem of coloring interval graphs as a special case for uniform weights, and it arises in many practical scenarios such as memory management. Pemmaraju, Raman, and Varadarajan showed that max-coloring interval graphs is NP-hard [21] and presented a 2-approximation algorithm. We settle the approximation complexity of this problem by giving a polynomial-time approximation scheme (PTAS), that is, we show that there is an (1+ϵ)-approximation algorithm for any ϵ>0. The PTAS also works for the bounded case where the sizes of the color classes are bounded by some arbitrary k≤n. [ABSTRACT FROM AUTHOR]

Bin packing with fragmentable items is a variant of the classic bin packing problem where items may be cut into smaller fragments. The objective is to minimize the number of item fragments, or equivalently, to minimize the number of cuts, for a given number of bins. Models based on packing fragmentable items are useful for representing finite shared resources. In this article, we present improvements to approximation and metaheuristic algorithms to obtain an optimality-preserving optimization algorithm with polynomial complexity, worst-case performance guarantees and parametrizable running time. We also present a new family of fast lower bounds and prove their worst-case performance ratios. We evaluate the performance and quality of the algorithm and the best lower bound through a series of computational experiments on representative problem instances. For the studied problem sets, one consisting of 180 problems with up to 20 items and another consisting of 450 problems with up to 1024 items, the lower bound performs no worse than 5 / 6. For the first problem set, the algorithm found an optimal solution in 92 % of all 1800 runs. For the second problem set, the algorithm found an optimal solution in 99 % of all 4500 runs. No run lasted longer than 220 ms. [ABSTRACT FROM AUTHOR]

Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact solutions when some part of the input is a fixed parameter. In this paper, we continue this study and show that several additional cases of fundamental scheduling problems are fixed-parameter tractable for some natural parameters. Our main tool is n-fold integer programming, a recent variable dimension technique which we believe to be highly relevant for the parameterized complexity community. This paper serves to showcase and highlight this technique. Specifically, we show the following four scheduling problems to be fixed-parameter tractable, where pmax is the maximum processing time of a job and wmax is the maximum weight of a job:Makespan minimization on uniformly related machines (Q||Cmax) parameterized by pmax,Makespan minimization on unrelated machines (R||Cmax) parameterized by pmax and the number of kinds of machines (defined later),Sum of weighted completion times minimization on unrelated machines (R||∑wjCj) parameterized by pmax+wmax and the number of kinds of machines,The same problem, R||∑wjCj, parameterized by the number of distinct job times and the number of machines. [ABSTRACT FROM AUTHOR]

We study variants of the capacitated vehicle routing problem. In the multiple depot capacitatedk-travelling repairmen problem (MD-CkTRP), we have a collection of clients to be served by one vehicle in a fleet of k identical vehicles based at given depots. Each client has a given demand that must be satisfied, and each vehicle can carry a total of at most Q demand before it must resupply at its original depot. We wish to route the vehicles in a way that obeys the constraints while minimizing the average time (latency) required to serve a client. This generalizes the Multi-depot k-Travelling Repairman Problem (MD-kTRP) (Chaudhuri et al. in 44th IEEE-FOCS, pp 36-45, 2003; Post and Swamy in 26th ACM-SIAM SODA, pp 512-531, 2015) to the capacitated vehicle setting, and while it has been previously studied (Lysgaard and Wholk in Eur J Oper Res 236(3):800-810, 2014), no approximation algorithm with a proven ratio is known. We give a 42.49-approximation to this general problem, and refine this constant to 25.49 when clients have unit demands. As far as we are aware, these are the first constant-factor approximations for capacitated vehicle routing problems with a latency objective. We achieve these results by developing a framework allowing us to solve a wider range of latency problems, and crafting various orienteering-style oracles for use in this framework. We also show a simple LP rounding algorithm has a better approximation ratio for the maximum coverage problem with groups (MCG), first studied by Chekuri and Kumar (Approximation, randomization, and combinatorial optimization, algorithms and techniques, pp 72-83, 2004), and use it as a subroutine in our framework. Our approximation ratio for MD-CkTRP when restricted to uncapacitated setting matches the best known bound for it (Post and Swamy in 26th ACM-SIAM SODA, pp 512-531, 2015). With our framework, any improvements to our oracles or our MCG approximation will result in improved approximations to the corresponding k-TRP problem. [ABSTRACT FROM AUTHOR]

Deadlock prevention techniques are essential in the design of robust distributed systems. However, despite the large number of different algorithmic approaches to detect and solve deadlock situations, yet there remains quite a wide field to be explored in the study of deadlock-related combinatorial properties. In this work we consider a simplified AND-OR model, where the processes and their communication are given as a graph G. Each vertex of G is labelled AND or OR, in such a way that an AND-vertex (resp., OR-vertex) depends on the computation of all (resp., at least one) of its neighbors. We define a graph convexity based on this model, such that a set S⊆V(G) is convex if and only if every AND-vertex (resp., OR-vertex) v∈V(G)\S has at least one (resp., all) of its neighbors in V(G)\S. We relate some classical convexity parameters to blocking sets that cause deadlock. In particular, we show that those parameters in a graph represent the sizes of minimum or maximum blocking sets, and also the computation time until system stability is reached. Finally, a study on the complexity of combinatorial problems related to such graph convexity is provided. [ABSTRACT FROM AUTHOR]

The minimum weight dominating set problem (MWDSP) is an NP-hard problem with a lot of real-world applications. Several heuristic algorithms have been presented to produce good quality solutions. However, the solution time of them grows very quickly as the size of the instance increases. In this paper, we propose a binary particle swarm optimization (FBPSO) for solving the MWDSP approximately. Based on the characteristic of MWDSP, this approach designs a new position updating rule to guide the search to a promising area. An iterated greedy tabu search is used to enhance the solution quality quickly. In addition, several stochastic strategies are employed to diversify the search and prevent premature convergence. These methods maintain a good balance between the exploration and the exploitation. Experimental studies on 106 groups of 1 060 instances show that FBPSO is able to identify near optimal solutions in a short running time. The average deviation between the solutions obtained by FBPSO and the best known solutions is 0.441%. Moreover, the average solution time of FBPSO is much less than that of other existing algorithms. In particular, with the increasing of instance size, the solution time of FBPSO grows much more slowly than that of other existing algorithms. [ABSTRACT FROM AUTHOR]

In this work, we consider the robust/soft-capacitated 2-level facility location problems. For the robust version, we propose a primal-dual based $$(3+\epsilon )$$ -approximation algorithm via construction of an adapted instance which explores some open facilities in the optimal solution. For the soft-capacitated version, we propose a $$ (4+ 1/ (e-1) +\epsilon )$$ -approximation algorithm via construction of the associated uncapacitated version whose connection cost is re-defined appropriately. [ABSTRACT FROM AUTHOR]

We consider the Combinatorial RNA Design problem, a minimal instance of RNA design where one must produce an RNA sequence that adopts a given secondary structure as its minimal free-energy structure. We consider two free-energy models where the contributions of base pairs are additive and independent: the purely combinatorial Watson-Crick model, which only allows equally-contributing $$\mathsf{A}$$ - $$\mathsf{U}$$ and $$\mathsf{C}$$ - $$\mathsf{G}$$ base pairs, and the real-valued Nussinov-Jacobson model, which associates arbitrary energies to $$\mathsf{A}$$ - $$\mathsf{U}$$ , $$\mathsf{C}$$ - $$\mathsf{G}$$ and $$\mathsf{G}$$ - $$\mathsf{U}$$ base pairs. We first provide a complete characterization of designable structures using restricted alphabets and, in the four-letter alphabet, provide a complete characterization for designable structures without unpaired bases. When unpaired bases are allowed, we characterize extensive classes of (non-)designable structures, and prove the closure of the set of designable structures under the stutter operation. Membership of a given structure to any of the classes can be tested in $$\varTheta (n)$$ time, including the generation of a solution sequence for positive instances. Finally, we consider a structure-approximating relaxation of the design, and provide a $$\varTheta (n)$$ algorithm which, given a structure S that avoids two trivially non-designable motifs, transforms S into a designable structure constructively by adding at most one base-pair to each of its stems. [ABSTRACT FROM AUTHOR]

We characterize the best possible trade-off achievable when optimizing the construction of a decision tree with respect to both the worst and the expected cost. It is known that a decision tree achieving the minimum possible worst case cost can behave very poorly in expectation (even exponentially worse than the optimal), and the vice versa is also true. Led by applications where deciding which optimization criterion might not be easy, several authors recently have focussed on the bicriteria optimization of decision trees. Here we sharply define the limits of the best possible trade-offs between expected and worst case cost. More precisely, we show that for every $$\rho >0$$ there is a decision tree D with worst testing cost at most $$(1 + \rho )\textit{OPT}_W$$ and expected testing cost at most $$\frac{1}{1 - e^{-\rho }} \textit{OPT}_E,$$ where $$\textit{OPT}_W$$ and $$\textit{OPT}_E$$ denote the minimum worst testing cost and the minimum expected testing cost of a decision tree for the given instance. We also show that this is the best possible trade-off in the sense that there are infinitely many instances for which we cannot obtain a decision tree with both worst testing cost smaller than $$(1 + \rho )\textit{OPT}_W$$ and expected testing cost smaller than $$\frac{1}{1 - e^{-\rho }} \textit{OPT}_E$$ . [ABSTRACT FROM AUTHOR]

Recent papers on approximation algorithms for the traveling salesman problem (TSP) have given a new variant of the well-known Christofides' algorithm for the TSP, called the Best-of-Many Christofides' algorithm. The algorithm involves sampling a spanning tree from the solution to the standard LP relaxation of the TSP, subject to the condition that each edge is sampled with probability at most its value in the LP relaxation. One then runs Christofides' algorithm on the tree by computing a minimum-cost matching on the odd-degree vertices in the tree, and shortcutting a traversal of the resulting Eulerian graph to a tour. In this paper we perform an experimental evaluation of the Best-of-Many Christofides' algorithm to see if there are empirical reasons to believe its performance is better than that of Christofides' algorithm. Furthermore, several different sampling schemes have been proposed; we implement several different schemes to determine which ones might be the most promising for obtaining improved performance guarantees over that of Christofides' algorithm. In our experiments, all of the implemented methods perform significantly better than Christofides' algorithm; an algorithm that samples from a maximum entropy distribution over spanning trees seems to be particularly good, though there are others that perform almost as well. [ABSTRACT FROM AUTHOR]

Over the past several decades there has been steady progress towards the goal of polynomial-time approximation schemes (PTAS) for fundamental geometric combinatorial optimization problems. A foremost example is the geometric hitting set problem: given a set P of points and a set $$\mathcal {D}$$ of geometric objects, compute the minimum-sized subset of P that hits all objects in $$\mathcal {D}$$ . For the case where $$\mathcal {D}$$ is a set of disks in the plane, the 30-year quest for a PTAS, starting from the seminal work of Hochbaum (SIAM J Comput 11:555-556, 1982), was finally achieved in Mustafa and Ray (Discret Comput Geom 44:883-895, 2010). Surprisingly, the algorithm to achieve the PTAS is simple: local-search. In particular, the algorithm starts with any hitting set, and iteratively tries to decrease its size by trying to replace some k points by $$k-1$$ points; call such an algorithm a $$(k, k-1)$$ -local search algorithm. Since then, local-search has turned out to be a powerful algorithmic approach towards achieving good approximation ratios for geometric problems (for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others). Unfortunately all these algorithms have the same limitation: local search is able to give a PTAS, but with large running times. In particular, the current best work shows that if $$k \ge 30$$ , then local-search is able to give a constant factor (as a function of k) approximation ratio (Fraser in Algorithms for Geometric Covering and Piercing Problems, 2012). Unfortunately this then implies that the running time for local-search to provably work at all is $$\Omega (n^{30})$$ using the current framework. As currently local search is the only known method that gives approximation factors that could be useful in practice, it becomes important to explore the limits-in both efficiency and quality-of local search. Simple examples show that (1, 0) and (2, 1) local search cannot give constant factor approximations. In this paper, we show that, surprisingly, just (3, 2) local search is able to give a constant-factor approximation; in fact we are able to get the precise quality limit of (3, 2)-local search: factor 8 approximation. This simplest working instance of local search already gives an approximation factor that is better than all known other methods! In fact, our improvement applies to all algorithms that use local-search for geometric independent-set problem, for dominating sets, for the terrain guarding problem and several others. Finding efficient (3, 2)-local search algorithms then becomes the key bottleneck in efficient and good-quality algorithms. In this paper we present such improved algorithms. [ABSTRACT FROM AUTHOR]

The bottleneck of the currently best $$(\ln (4)+{\varepsilon })$$ -approximation algorithm for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are strongly NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well. We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be solved efficiently. Its integrality gap is known to be greater than 1.16, and while this is widely conjectured to be close to the real answer, only a (trivial) upper bound of 2 is known. In this article, we give an efficient constructive proof that BCR and HYP are polyhedrally equivalent in instances that do not have an (edge-induced) claw on Steiner vertices, i.e., they do not contain a Steiner vertex with three Steiner neighbours. This implies faster $$\ln (4)$$ -approximations for these graphs, and is a significant step forward from the previously known equivalence for (so called quasi-bipartite) instances in which Steiner vertices form an independent set. We complement our results by showing that even restricting to instances where Steiner vertices induce one single star, determining whether the two relaxations are equivalent is NP-hard. [ABSTRACT FROM AUTHOR]

The little Grothendieck problem consists of maximizing $$\sum _{ij}C_{ij}x_ix_j$$ for a positive semidefinite matrix C, over binary variables $$x_i\in \{\pm 1\}$$ . In this paper we focus on a natural generalization of this problem, the little Grothendieck problem over the orthogonal group. Given $$C\in \mathbb {R}^{dn\times dn}$$ a positive semidefinite matrix, the objective is to maximize $$\sum _{ij}{\text {tr}}\left( C^T_{ij}O_iO_j^T\right) $$ restricting $$O_i$$ to take values in the group of orthogonal matrices $$\mathcal {O}_d$$ , where $$C_{ij}$$ denotes the ( ij)-th $$d\times d$$ block of C. We propose an approximation algorithm, which we refer to as Orthogonal-Cut, to solve the little Grothendieck problem over the group of orthogonal matrices $$\mathcal {O}_d$$ and show a constant approximation ratio. Our method is based on semidefinite programming. For a given $$d\ge 1$$ , we show a constant approximation ratio of $$\alpha _{\mathbb {R}}(d)^2$$ , where $$\alpha _{\mathbb {R}}(d)$$ is the expected average singular value of a $$d\times d$$ matrix with random Gaussian $$\mathcal {N}\left( 0,\frac{1}{d}\right) $$ i.i.d. entries. For $$d=1$$ we recover the known $$\alpha _{\mathbb {R}}(1)^2=2/\pi $$ approximation guarantee for the classical little Grothendieck problem. Our algorithm and analysis naturally extends to the complex valued case also providing a constant approximation ratio for the analogous little Grothendieck problem over the Unitary Group $$\mathcal {U}_d$$ . Orthogonal-Cut also serves as an approximation algorithm for several applications, including the Procrustes problem where it improves over the best previously known approximation ratio of $$\frac{1}{2\sqrt{2}}$$ . The little Grothendieck problem falls under the larger class of problems approximated by a recent algorithm proposed in the context of the non-commutative Grothendieck inequality. Nonetheless, our approach is simpler and provides better approximation with matching integrality gaps. Finally, we also provide an improved approximation algorithm for the more general little Grothendieck problem over the orthogonal (or unitary) group with rank constraints, recovering, when $$d=1$$ , the sharp, known ratios. [ABSTRACT FROM AUTHOR]

Let $$b\in {\mathbb {N}}_{\ge 1}$$ and let $${\mathcal {H}}=(V,{\mathcal {E}})$$ be a hypergraph with maximum vertex degree $${\varDelta }$$ and maximum edge size $$l$$ . A set $$b$$ -multicover in $${\mathcal {H}}$$ is a set of edges $$C \subseteq {\mathcal {E}}$$ such that every vertex in $$V$$ belongs to at least $$b$$ edges in $$C$$ . $${\textsc {set }}\, b\text {-}{\textsc {multicover}}$$ is the problem of finding a set $$b$$ -multicover of minimum cardinality, and for $$b=1$$ it is the fundamental set cover problem. Peleg et al. (Algorithmica 18(1):44-66, ) gave a randomized algorithm achieving an approximation ratio of $$\delta \cdot \big (1-\big (\frac{c}{n}\big )^\frac{1}{\delta }\big )$$ , where $$\delta := {\varDelta }- b + 1$$ and $$c>0$$ is a constant. As this ratio depends on the instance size $$n$$ and tends to $$\delta $$ as $$n$$ tends to $$\infty $$ , it remained an open problem whether an approximation ratio of $$\delta \alpha $$ with a constant $$\alpha < 1$$ can be proved. In fact, the authors conjectured that for any fixed $${\varDelta }$$ and $$b$$ , the problem is not approximable within a ratio smaller than $$\delta $$ , unless $${\mathcal {P}}={\mathcal {NP}}$$ . We present a randomized algorithm of hybrid type for $${\textsc {set }}\, b\text {-}{\textsc {multicover}}$$ , $$b \ge 2$$ , combining LP-based randomized rounding with greedy repairing, and achieve an approximation ratio of $$\delta \cdot \left( 1 - \frac{11({\varDelta }- b)}{72l} \right) $$ for hypergraphs with maximum edge size $$l \in {\mathcal {O}}\left( \max \big \{(nb)^\frac{1}{5},n^\frac{1}{4}\big \}\right) $$ . In particular, for all hypergraphs where $$l$$ is constant, we get an $$\alpha \delta $$ -ratio with constant $$\alpha < 1$$ . Hence the above stated conjecture does not hold for hypergraphs with constant $$l$$ and we have identified the boundedness of the maximum hyperedge size as a relevant parameter responsible for approximations below $$\delta $$ . [ABSTRACT FROM AUTHOR]

Let $$\mathcal {H}=(V,\mathcal {E})$$ be a hypergraph with set of vertices $$V, n:=|V|$$ and set of (hyper-)edges $$\mathcal {E}, m:=|\mathcal {E}|$$ . Let $$l$$ be the maximum size of an edge, $$\varDelta $$ be the maximum vertex degree and $$D$$ be the maximum edge degree. The $$k$$ -partial vertex cover problem in hypergraphs is the problem of finding a minimum cardinality subset of vertices in which at least $$k$$ hyperedges are incident. For the case of $$k=m$$ and constant $$l$$ it known that an approximation ratio better than $$l$$ cannot be achieved in polynomial time under the unique games conjecture (UGC) (Khot and Ragev J Comput Syst Sci, 74(3):335-349, ), but an $$l$$ -approximation ratio can be proved for arbitrary $$k$$ (Gandhi et al. J Algorithms, 53(1):55-84, ). The open problem in this context has been to give an $$\alpha l$$ -ratio approximation with $$\alpha < 1$$ , as small as possible, for interesting classes of hypergraphs. In this paper we present a randomized polynomial-time approximation algorithm which not only achieves this goal, but whose analysis exhibits approximation phenomena for hypergraphs with $$l\ge 3$$ not visible in graphs: if $$\varDelta $$ and $$l$$ are constant, and $$2\le l\le 4\varDelta $$ , we prove for $$l$$ -uniform hypergraphs a ratio of $$l\left( 1-\frac{l-1}{4\varDelta }\right) $$ , which tends to the optimal ratio 1 as $$l\ge 3$$ tends to $$4\varDelta $$ . For the larger class of hypergraphs where $$l, l \ge 3$$ , is not constant, but $$D$$ is a constant, we show a ratio of $$l(1-1/6D)$$ . Finally for hypergraphs with non-constant $$l$$ , but constant $$\varDelta $$ , we get a ratio of $$ l (1- \frac{2 - \sqrt{3}}{6\varDelta })$$ for $$k\ge m/4$$ , leaving open the problem of finding such an approximation for $$k < m/4$$ . [ABSTRACT FROM AUTHOR]

In this paper we give improved approximation algorithms for some network design problems. In the bounded-diameter or shallow-light $$k$$ -Steiner tree problem (SL $$k$$ ST), we are given an undirected graph $$G=(V,E)$$ with terminals $$T\subseteq V$$ containing a root $$r\in T$$ , a cost function $$c:E\rightarrow \mathbb {R}^+$$ , a length function $$\ell :E\rightarrow \mathbb {R}^+$$ , a bound $$L>0$$ and an integer $$k\ge 1$$ . The goal is to find a minimum $$c$$ -cost $$r$$ -rooted Steiner tree containing at least $$k$$ terminals whose diameter under $$\ell $$ metric is at most $$L$$ . The input to the buy-at-bulk $$k$$ -Steiner tree problem (BB $$k$$ ST) is similar: graph $$G=(V,E)$$ , terminals $$T\subseteq V$$ containing a root $$r\in T$$ , cost and length functions $$c,\ell :E\rightarrow \mathbb {R}^+$$ , and an integer $$k\ge 1$$ . The goal is to find a minimum total cost $$r$$ -rooted Steiner tree $$H$$ containing at least $$k$$ terminals, where the cost of each edge $$e$$ is $$c(e)+\ell (e)\cdot f(e)$$ where $$f(e)$$ denotes the number of terminals whose path to root in $$H$$ contains edge $$e$$ . We present a bicriteria $$(O(\log ^2 n),O(\log n))$$ -approximation for SL $$k$$ ST: the algorithm finds a $$k$$ -Steiner tree with cost at most $$O(\log ^2 n\cdot \text{ opt }^*)$$ where $$\text{ opt }^*$$ is the cost of an LP relaxation of the problem and diameter at most $$O(L\cdot \log n)$$ . This improves on the algorithm of Hajiaghayi et al. () (APPROX'06/Algorithmica'09) which had ratio $$(O(\log ^4 n), O(\log ^2 n))$$ . Using this, we obtain an $$O(\log ^3 n)$$ -approximation for BB $$k$$ ST, which improves upon the $$O(\log ^4 n)$$ -approximation of Hajiaghayi et al. (). We also consider the problem of finding a minimum cost $$2$$ -edge-connected subgraph with at least $$k$$ vertices, which is introduced as the $$(k,2)$$ -subgraph problem in Lau et al. () (STOC'07/SICOMP09). This generalizes some well-studied classical problems such as the $$k$$ -MST and the minimum cost $$2$$ -edge-connected subgraph problems. We give an $$O(\log n)$$ -approximation algorithm for this problem which improves upon the $$O(\log ^2 n)$$ -approximation algorithm of Lau et al. (). [ABSTRACT FROM AUTHOR]

We consider the capacitated $$k$$ -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) $$k$$ locations (called centers) and assign each location to an open center to minimize the maximum, over all locations, of the distance of the location to its assigned center. The number of locations assigned to a center cannot exceed the center's capacity. The uncapacitated $$k$$ -center problem has a simple tight $$2$$ -approximation from the 80's. In contrast, the first constant factor approximation for the capacitated problem was obtained only recently by Cygan, Hajiaghayi and Khuller who gave an intricate LP-rounding algorithm that achieves an approximation guarantee in the hundreds. In this paper we give a simple algorithm with a clean analysis and prove an approximation guarantee of $$9$$ . It uses the standard LP relaxation and comes close to settling the integrality gap (after necessary preprocessing), which is narrowed down to either $$7, 8$$ or $$9$$ . The algorithm proceeds by first reducing to special tree instances, and then uses our best-possible algorithm to solve such instances. Our concept of tree instances is versatile and applies to natural variants of the capacitated $$k$$ -center problem for which we also obtain improved algorithms. Finally, we give evidence to show that more powerful preprocessing could lead to better algorithms, by giving an approximation algorithm that beats the integrality gap for instances where all non-zero capacities are the same. [ABSTRACT FROM AUTHOR]