Search

In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta et al. (ACM STOC, 2013) obtained a 2-approximation with polynomial running time for fixed k, and it remained open the question of whether there exists a c-approximation algorithm for a constant c independent of k, that runs in FPT time. We answer this question in the affirmative. We design a 2-approximation algorithm for the non-uniform sparsest cut with bounded treewidth supply graphs that runs in FPT time, when parameterized by the treewidth. Our algorithm is based on rounding the optimal solution of a linear programming relaxation inspired by the Sherali-Adams hierarchy. In contrast to the classic Sherali-Adams approach, we construct a relaxation driven by a tree decomposition of the supply graph by including a carefully chosen set of lifting variables and constraints to encode information of subsets of nodes with super-constant size, and at the same time we have a sufficiently small linear program that can be solved in FPT time. [ABSTRACT FROM AUTHOR]

Many modern day cloud hosted applications such as virtual reality, real time games require low latency data access and computation to improve response time. So it is essential to bring the computation and data storage edge servers closer to the user's geographical location to improve response times and save bandwidth. In particulars, in online gaming and on demand video services, the required application data present at cloud servers need to be placed on the edge servers to provide low latency app-functionalities. The transfer of huge amount of data from cloud server to edge server incurs high cost and time penalties. Thus, we need an efficient way to solve edge data distribution (EDD) problem which distribute the application data to the edge servers that minimizes transfer cost. In this work, we provide a refined formulation of an optimal approach to solve the EDD problem using integer linear programming (ILP) technique. Due to the time complexity limitation of the ILP approach, we propose an O(k) approximation algorithm based on network Steiner tree estimation (EDD-NSTE) for estimating solutions to dense large-scale EDD problem. The proposed approach is analyzed to be 11/6 approximation which is better than the state-of-the-art 2 approximation EDD-A approach. The experimental evaluation through simulation using real world EUA data set demonstrate that the EDD-NSTE outperform state-of-the-art approach and other representative approaches. [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]

We study several two-machine shop scheduling problems, namely flow shop, job shop and open shop scheduling problems under linear constraints. In these problems, the processing times of two stages of jobs are also decision variables and satisfy a system of linear constraints. The goal of each problem is to determine the processing time of each job, and to schedule the jobs to the shop machine such that the makespan, i.e., the completion time of all jobs, is minimized. These problems can find application in various areas, such as industrial production, advertising and automotive maintenance. We study the computational complexity and propose polynomial-time optimal or approximation algorithms for them. In particular, we show that although a two-machine flow shop scheduling problem and a two-machine job shop scheduling problem without recirculation can be solved in polynomial time, the problems where processing times satisfy linear constraints are generally NP-hard in the strong sense. Then, we design algorithms for various settings of these problems. We design polynomial-time algorithms for them when there are a fixed number of constraints. For the general case, we first propose a simple 2-approximation algorithm, and then design a polynomial-time approximation schemes. In contrast to the previous two problems, we show that the two-machine open shop scheduling problem under linear constraints can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

Constrained partially observable Markov decision processes (CPOMDPs) have been used to model various real-world phenomena. However, they are notoriously difficult to solve to optimality, and there exist only a few approximation methods for obtaining high-quality solutions. In this study, grid-based approximations are used in combination with linear programming (LP) models to generate approximate policies for CPOMDPs. A detailed numerical study is conducted with six CPOMDP problem instances considering both their finite and infinite horizon formulations. The quality of approximation algorithms for solving unconstrained POMDP problems is established through a comparative analysis with exact solution methods. Then, the performance of the LP-based CPOMDP solution approaches for varying budget levels is evaluated. Finally, the flexibility of LP-based approaches is demonstrated by applying deterministic policy constraints, and a detailed investigation into their impact on rewards and CPU run time is provided. For most of the finite horizon problems, deterministic policy constraints are found to have little impact on expected reward, but they introduce a significant increase to CPU run time. For infinite horizon problems, the reverse is observed: deterministic policies tend to yield lower expected total rewards than their stochastic counterparts, but the impact of deterministic constraints on CPU run time is negligible in this case. Overall, these results demonstrate that LP models can effectively generate approximate policies for both finite and infinite horizon problems while providing the flexibility to incorporate various additional constraints into the underlying model. [ABSTRACT FROM AUTHOR]

We study geometric variations of the discriminating code problem. In the discrete version of the problem, a finite set of points P and a finite set of objects S are given in R d . The objective is to choose a subset S ∗ ⊆ S of minimum cardinality such that for each point p i ∈ P , the subset S i ∗ ⊆ S ∗ covering p i satisfies S i ∗ ≠ ∅ , and each pair p i , p j ∈ P , i ≠ j , we have S i ∗ ≠ S j ∗ . In the continuous version of the problem, the solution set S ∗ can be chosen freely among a (potentially infinite) class of allowed geometric objects. In the 1-dimensional case ( d = 1 ), the points in P are placed on a horizontal line L, and the objects in S are finite-length line segments aligned with L (called intervals). We show that the discrete version of this problem is NP-complete. This is somewhat surprising as the continuous version is known to be polynomial-time solvable. This is also in contrast with most geometric covering problems, which are usually polynomial-time solvable in one dimension. Still for the 1-dimensional discrete version, we design a polynomial-time 2-approximation algorithm. We also design a PTAS for both discrete and continuous versions in one dimension, for the restriction where the intervals are all required to have the same length. We then study the 2-dimensional case ( d = 2 ) for axis-parallel unit square objects. We show that both continuous and discrete versions are NP-complete, and design polynomial-time approximation algorithms that produce (16 · O P T + 1) -approximate and (64 · O P T + 1) -approximate solutions respectively, using rounding of suitably defined integer linear programming problems. Finally, we apply our techniques to a related variant of the discrete problem, where instead of points and geometric objects we just have a set S of objects. The goal is to select a small subset S ∗ of objects so that all objects of S are discriminated by their intersection with the objects of S ∗ . This problem can be viewed as a graph problem by stating it in terms of the vertices of the geometric intersection graph of S. Under this graph-theoretical form, it is known as the identifying code problem. We show that the identifying code problem for axis-parallel unit square intersection graphs (in d = 2 ) can be solved in the same manner as for the discrete version of the discriminating code problem for unit square objects described above, and all our positive approximation results still hold in this setting. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (V , E) , a subset S ⊆ V is a 2-packing set if, for any pair of vertices u , v ∈ S , the shortest path between them is at least three-edge long. Finding a 2-packing set of maximum cardinality is an NP-hard problem for arbitrary graphs. This paper proposes an approximation algorithm for the maximum 2-packing set problem for planar graphs. We show that our algorithm is at least λ - 2 λ of the optimal (i.e. the approximation ratio is λ λ - 2 ), where λ is a constant related to how the proposed algorithm decomposes the input graph into smaller subgraphs. Then, we improve the solution given by our approximation algorithm by adding some vertices to the solution. Experimentally, we show that our improved algorithm computes a near-optimal 2-packing set. This algorithm is the first approximation algorithm for the maximum 2-packing set to the best of our knowledge. [ABSTRACT FROM AUTHOR]

We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the rooted Subtree Prune-and-Regraft (rSPR) distance between two phylogenetic trees. Our algorithm is combinatorial and its running time is quadratic in the input size. To prove the approximation guarantee, we construct a feasible dual solution for a novel exponential-size linear programming formulation. In addition, we show this linear program has a smaller integrality gap than previously known formulations, and we give an equivalent compact formulation, showing that it can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

We give the first 2-approximation algorithm for the cluster vertex deletion problem. This approximation factor is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines previous approaches, based on the local ratio technique and the management of twins, with a novel construction of a "good" cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem. [ABSTRACT FROM AUTHOR]

We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. Assuming the existence of an integrality gap verifier with a bounded approximation guarantee for the LP relaxation of the non-robust version of the problem, we derive approximation algorithms for the robust version under different types of uncertainty, including polyhedral and ellipsoidal uncertainty. [ABSTRACT FROM AUTHOR]

We present two new algorithms for convex Mixed Integer Nonlinear Programming (MINLP), both based on the well known Extended Cutting Plane (ECP) algorithm proposed by Weterlund and Petersson. Our first algorithm, Refined Extended Cutting Plane (RECP), incorporates additional cuts to the MILP relaxation of the original problem, obtained by solving linear relaxations of NLP problems considered in the Outer Approximation algorithm. Our second algorithm, Linear Programming based Branch-and-Bound (LP-BB), applies the strategy of generating cuts that is used in RECP, to the linear approximation scheme used by the LP/NLP based Branch-and-Bound algorithm. Our computational results show that RECP and LP-BB are highly competitive with the most popular MINLP algorithms from the literature, while keeping the nice and desirable characteristic of ECP, of being a first-order method. [ABSTRACT FROM AUTHOR]

Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters can protect up to B vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not been protected so far. The task is to find the smallest B that allows for saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2 even on trees unless P = NP (King and MacGillivray in Discret Math 310(3):614–621, 2010). Chalermsook and Chuzhoy (In: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, Texas, USA, 17–19 Jan 2010, SIAM, pp 1334–1349, 2010) presented a Linear Programming (LP) based O (log ∗ n) approximation for RMFC on trees that matches the integrality gap of the natural Linear Programming relaxation. This was recently improved by Adjiashvili et al. (ACM Trans Algorithms 15(2):20:1–20:33, 2019) to a 12-approximation through a combination of LP rounding along with several new techniques. In this paper we present an asymptotic QPTAS for RMFC on trees. More specifically, let ϵ > 0 , and I be an instance of RMFC where the optimum number of firefighters to save all the leaves is O P T (I) . We present an algorithm which uses at most ⌈ (1 + ϵ) O P T (I) ⌉ many firefighters at each time step and runs in time n O (log log n / ϵ) . This suggests that the existence of an asymptotic PTAS is plausible especially since the exponent is O (log log n) , not O (log n) . Our result combines a more refined height reduction lemma than the one in Adjiashvili et al. (2019) with LP rounding and dynamic programming to find the solution. We also apply our height reduction lemma to the algorithm provided in Adjiashvili et al. (2019) plus a more careful analysis to improve their 12-approximation and provide a polynomial time ( 5 + ϵ )-approximation. [ABSTRACT FROM AUTHOR]

For a family of graphs F , Weighted F -Deletion is the problem for which the input is a vertex weighted graph G = (V , E) and the goal is to delete S ⊆ V with minimum weight such that G \ S ∈ F . Designing a constant-factor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3-leaf power graphs, and interval graphs are known to admit constant-factor approximation algorithms, but the question is open for chordal graphs and distance-hereditary graphs. In this paper, we add one more class to this list by presenting a constant-factor approximation algorithm when F is the intersection of chordal graphs and distance-hereditary graphs. They are known as ptolemaic graphs and form a superset of both block graphs and 3-leaf power graphs above. Our proof presents new properties and algorithmic results on inter-clique digraphs as well as an approximation algorithm for a variant of Feedback Vertex Set that exploits this relationship (named Feedback Vertex Set with Precedence Constraints), each of which may be of independent interest. [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]

An instance of colorfulk-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius ρ such that there exist balls of radius ρ around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations. Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical k-center problem which this problem generalizes. algorithms either opened more than k centers or only worked in the special case when the input points are in the plane. [ABSTRACT FROM AUTHOR]

We consider the solution of the speed problem for linear time-varying discrete-time systems with convex control constraints. A method is proposed for reducing the general case of the speed problem to the case of linear control constraints using polyhedral approximation algorithms. Sufficient optimality conditions for the guaranteed solution are stated and proved. Examples are given. Based on the methods obtained, the speed-optimal damping problem for a high-rise structure located in a seismic activity zone is solved. [ABSTRACT FROM AUTHOR]

In this paper, we work on the scheduling problem with active time model. We have a set of preemptive jobs with integral release times, deadlines and required processing lengths, while the preemption of jobs is only allowed at integral time points. We have a single machine that can process at most g distinct job units at any given time unit when the machine is switched on. The objective is to find a schedule that completes all jobs within their timing constraints and minimizes the time when the machine is on, i.e., the active time. This problem has been studied by Chang et al. where they proposed an LP rounding approach which gives a 2-approximation solution. In this paper, we also give a 2-approximation algorithm based on LP rounding approach with a different rounding technique and analysis. Finally, we give a new linear programming formulation for which we conjecture that the integrality gap is 5/3, which might bring new hope for beating the barrier of 2 for the approximation ratio. [ABSTRACT FROM AUTHOR]

Clustering is a fundamental tool for analyzing large data sets. A rich body of work has been devoted to designing data-stream algorithms for the relevant optimization problems such as k-center, k-median, and k-means. Such algorithms need to be both time and and space efficient. In this paper, we address the problem of correlation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on n nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, O (n · polylog n) -space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the "quality" of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. Unfortunately, the standard LP and SDP formulations are not obviously solvable in O (n · polylog n) -space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling. [ABSTRACT FROM AUTHOR]

This paper presents a novel partially distributed outer approximation algorithm, named PaDOA, for solving a class of structured mixed integer convex programming problems to global optimality. The proposed scheme uses an iterative outer approximation method for coupled mixed integer optimization problems with separable convex objective functions, affine coupling constraints, and compact domain. PaDOA proceeds by alternating between solving large-scale structured mixed-integer linear programming problems and partially decoupled mixed-integer nonlinear programming subproblems that comprise much fewer integer variables. We establish conditions under which PaDOA converges to global minimizers after a finite number of iterations and verify these properties with an application to thermostatically controlled loads and to mixed-integer regression. [ABSTRACT FROM AUTHOR]

Motivated by the well known "four-thirds conjecture" for the traveling salesman problem (TSP), we study the problem of uniform covers. A graph G = (V , E) has an α -uniform cover for TSP (2EC, respectively) if the everywhere α vector (i.e., { α } E ) dominates a convex combination of incidence vectors of tours (2-edge-connected spanning multigraphs, respectively). The polyhedral analysis of Christofides' algorithm directly implies that a 3-edge-connected, cubic graph has a 1-uniform cover for TSP. Sebő asked if such graphs have (1 - ϵ) -uniform covers for TSP for some ϵ > 0 . Indeed, the four-thirds conjecture implies that such graphs have 8 9 -uniform covers. We show that these graphs have 18 19 -uniform covers for TSP. We also study uniform covers for 2EC and show that the everywhere 15 17 vector can be efficiently written as a convex combination of 2-edge-connected spanning multigraphs. For a weighted, 3-edge-connected, cubic graph, our results show that if the everywhere 2 3 vector is an optimal solution for the subtour elimination linear programming relaxation for TSP, then a tour with weight at most 27 19 times that of an optimal tour can be found efficiently. Node-weighted, 3-edge-connected, cubic graphs fall into this category. In this special case, we can apply our tools to obtain an even better approximation guarantee. An essential ingredient in our proofs is decompositions of graphs (e.g., cycle covers) that cover small-cardinality cuts an even (nonzero) number of times. Another essential tool we use is half-integral tree augmentation, which is known to have a small integrality gap. To extend our approach to input graphs that are 2-edge-connected, we present a procedure to decompose a point in the subtour elimination polytope into spanning, connected subgraphs that cover each 2-edge cut an even number of times. Using this decomposition, we obtain a 17 12 -approximation algorithm for minimum weight 2-edge-connected spanning subgraphs on subcubic, node-weighted graphs. [ABSTRACT FROM AUTHOR]

The problem of computing the vertices of the convex hull of a given input set S = { v i ∈ R m : i = 1 , ⋯ , n } is a classic and fundamental problem, studied in the context of computational geometry, linear and convex programming, machine learning and more. In this article we present All Vertex Triangle Algorithm (AVTA), a robust and efficient algorithm for this problem. On the one hand, without any assumptions, AVTA computes approximation to the subset S ¯ of all K vertices of the convex hull of S so that the convex hull of the approximate subset of vertices is as close to conv(S) as desired. On the other hand, assuming a known lower bound γ on the ratio Γ ∗ / R , where Γ ∗ the minimum of the distances from each vertex to the convex hull of the remaining vertices and R the diameter of S, AVTA can recover all of S ¯ . Furthermore, assuming that instead of S the input is an ε -perturbation of S, S ¯ ε , where ‖ v i - v i ε ‖ ≤ ε R , AVTA can compute approximation to c o n v (S ¯ ε) , to any prescribed accuracy. Also, given a lower bound to the ratio Σ ∗ / R , where Σ ∗ is the minimum of the distances from each vertex to the convex hull of the remaining point of S, AVTA can recover all of S ¯ ε . We show Σ ∗ ≥ ρ ∗ Γ ∗ / R , where ρ ∗ is the minimum distance between distinct pair of points in S and prove the following main results: Given any t ∈ (0 , 1) , AVTA computes a subset S ¯ t of S ¯ of cardinality K (t) in O (n K (t) (m + t - 2)) operations so that for any p ∈ c o n v (S) its Euclidean distance to c o n v (S ¯ t) is at most tR. Given γ ≤ γ ∗ = Γ ∗ / R , AVTA computes S ¯ in O (n K (m + γ - 2)) operations. If K is known, the complexity of AVTA is O (n K (m + γ ∗ - 2) log (γ ∗ - 1)) . Assuming instead of S, its ε -perturbation, S ε is given, we prove Given any t ∈ (0 , 1) , AVTA computes a subset S ¯ ε t ⊂ S ¯ ε of cardinality K ε (t) in O (n K ε (t) (m + t - 2)) operations so that for any p ∈ c o n v (S) its distance to c o n v (S ¯ ε t) is at most (t + ε) R . Given σ ∈ [ 4 ε , σ ∗ = Γ ∗ / R ] , AVTA computes S ¯ ε in O (n K ε (m + σ - 2)) operations, where K ≤ K ε ≤ n . If γ ≤ γ ∗ = Γ ∗ / R is known satisfying 4 ε ≤ γ ρ ∗ / R , AVTA computes S ¯ ε in O (n K ε (m + (γ ρ ∗) - 2)) operations. Given σ ∈ [ 4 ε , σ ∗ ] , if K is known, AVTA computes S ¯ ε in O (n K (m + σ ∗ - 2) log (σ ∗ - 1)) operations. We also consider the application of AVTA in the recovery of vertices through the projection of S or S ε under a Johnson–Lindenstrauss randomized linear projection L : R m → R m ′ . Denoting U = L (S) and U ε = L (S ε) , by relating the robustness parameters of conv(U) and c o n v (U ε) to those of conv(S) and c o n v (S ε) , we derive analogous complexity bounds for probabilistic computation of the vertex set of conv(U) or those of c o n v (U ε) , or an approximation to them. Finally, we apply AVTA to design new practical algorithms for two popular machine learning problems: topic modeling and non-negative matrix factorization. For topic models, our new algorithm leads to significantly better reconstruction of the topic-word matrix than state of the art approaches of Arora et al. (International conference on machine learning, pp 280–288, 2013) and Bansal et al. (Advances in neural information processing systems, pp 1997–2005, 2014). Additionally, we provide a robust analysis of AVTA and empirically demonstrate that it can handle larger amounts of noise than existing methods. For non-negative matrix factorization we show that AVTA is competitive with existing methods that are specialized for this task in Arora et al. (Proceedings of the forty-fourth annual ACM symposium on theory of computing, ACM, pp 145–162, 2012a). We also contrast AVTA with Blum et al. (Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, Society for Industrial and Applied Mathematics, pp 548–557, 2016) Greedy Clustering coreset algorithm for computing approximation to the set of vertices and argue that not only there are regimes where AVTA outperforms that algorithm but it can also be used as a pre-processing step to their algorithm. Thus the two algorithms in fact complement each other. [ABSTRACT FROM AUTHOR]

We consider approximation algorithms for packing integer programs (PIPs) of the form max { ⟨ c , x ⟩ : A x ≤ b , x ∈ { 0 , 1 } n } where A, b and c are nonnegative. We let W = min i , j b i / A i , j denote the width of A which is at least 1. Previous work by Bansal et al. (Theory Comput 8(24):533–565, 2012) obtained an Ω (1 Δ 0 1 / ⌊ W ⌋ ) -approximation ratio where Δ 0 is the maximum number of nonzeroes in any column of A (in other words the ℓ 0 -column sparsity of A). They raised the question of obtaining approximation ratios based on the ℓ 1 -column sparsity of A (denoted by Δ 1 ) which can be much smaller than Δ 0 . Motivated by recent work on covering integer programs (Chekuri and Quanrud, in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1596–1615. SIAM, 2019; Chen et al., in: Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1984–2003. SIAM, 2016) we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. (Theory Comput 8(24):533–565, 2012) (but with a twist), yield approximation ratios for PIPs based on Δ 1 . First, following an integrality gap example from (Theory Comput 8(24):533–565, 2012), we observe that the case of W = 1 is as hard as maximum independent set even when Δ 1 ≤ 2 . In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width W = 1 + ϵ where ϵ ∈ (0 , 1 ] , we obtain an Ω (ϵ 2 / Δ 1) -approximation. In the large width regime, when W ≥ 2 , we obtain an Ω ((1 1 + Δ 1 / W) 1 / (W - 1)) -approximation. We also obtain a (1 - ϵ) -approximation when W = Ω (log (Δ 1 / ϵ) ϵ 2) . Viewing the rounding algorithms as contention resolution schemes, we obtain approximation algorithms in the more general setting when the objective is a non-negative submodular function. [ABSTRACT FROM AUTHOR]

We consider non-preemptive scheduling of MapReduce jobs consisting of multiple map-reduce rounds so as to minimize their average weighted completion time on identical or unrelated processor environments. For identical processors, we present LP-based O(1)-approximation algorithms, while for unrelated processors the approximation ratio naturally depends on the maximum number of rounds of any job (which is a small constant in practice). For the single-round case, we substantially improve on previously best known approximation ratios, while also we introduce into our model the crucial cost of the data shuffle phase, i.e., the cost for the transmission of intermediate data from Map to Reduce tasks. Finally, we evaluate our algorithms via simulations in the general case of unrelated processors, comparing them with a lower bound on the optimal cost of the problem as well as with a fast algorithm which combines a simple online assignment of tasks to processors with a standard scheduling policy. As we observe, for random instances that capture data locality issues, our algorithm achieves an excellent average performance. [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]

In recent years, the popularity of graph databases has grown rapidly. This paper focuses on single-graph as an effective model to represent information and its related graph mining techniques. In frequent pattern mining in a single-graph setting, there are two main problems: support measure and search scheme. In this paper, we propose a novel framework for designing support measures that brings together existing minimum-image-based and overlap-graph-based support measures. Our framework is built on the concept of occurrence/instance hypergraphs. Based on such, we are able to design a series of new support measures: minimum instance (MI) measure, and minimum vertex cover (MVC) measure, that combine the advantages of existing measures. More importantly, we show that the existing minimum-image-based support measure is an upper bound of the MI measure, which is also linear-time computable and results in counts that are close to number of instances of a pattern. We show that not only most major existing support measures and new measures proposed in this paper can be mapped into the new framework, but also they occupy different locations of the frequency spectrum. By taking advantage of the new framework, we discover that MVC can be approximated to a constant factor (in terms of number of pattern nodes) in polynomial time. In contrast to common belief, we demonstrate that the state-of-the-art overlap-graph-based maximum independent set (MIS) measure also has constant approximation algorithms. We further show that using standard linear programming and semidefinite programming techniques, polynomial-time relaxations for both MVC and MIS measures can be developed and their counts stand between MVC and MIS. In addition, we point out that MVC, MIS, and their relaxations are bounded within constant factor. In summary, all major support measures are unified in the new hypergraph-based framework which helps reveal their bounding relations and hardness properties. [ABSTRACT FROM AUTHOR]

Social networks often provide only a binary perspective on social ties: two individuals are either connected or not. While sometimes external information can be used to infer the strength of social ties, access to such information may be restricted or impractical to obtain. Sintos and Tsaparas (KDD 2014) first suggested to infer the strength of social ties from the topology of the network alone, by leveraging the Strong Triadic Closure (STC) property. The STC property states that if person A has strong social ties with persons B and C, B and C must be connected to each other as well (whether with a weak or strong tie). They exploited this property to formulate the inference of the strength of social ties as a NP-hard maximization problem, and proposed two approximation algorithms. We refine and improve this line of work, by developing a sequence of linear relaxations of the problem, which can be solved exactly in polynomial time. Usefully, these relaxations infer more fine-grained levels of tie strength (beyond strong and weak), which also allows one to avoid making arbitrary strong/weak strength assignments when the network topology provides inconclusive evidence. Moreover, these relaxations allow us to easily change the objective function to more sensible alternatives, instead of simply maximizing the number of strong edges. An extensive theoretical analysis leads to two efficient algorithmic approaches. Finally, our experimental results elucidate the strengths of the proposed approach, while at the same time questioning the validity of leveraging the STC property for edge strength inference in practice. [ABSTRACT FROM AUTHOR]

We consider the P m | | C max scheduling problem where the goal is to schedule n jobs on m identical parallel machines (m < n) to minimize makespan. We revisit the famous Longest Processing Time (LPT) rule proposed by Graham in 1969. LPT requires to sort jobs in non-ascending order of processing times and then to assign one job at a time to the machine whose load is smallest so far. We provide new insights into LPT and discuss the approximation ratio of a modification of LPT that improves Graham's bound from 4 3 - 1 3 m to 4 3 - 1 3 (m - 1) for m ≥ 3 and from 7 6 to 9 8 for m = 2 . We use linear programming to analyze the approximation ratio of our approach. This performance analysis can be seen as a valid alternative to formal proofs based on analytical derivation. Also, we derive from the proposed approach an O (n log n) time complexity heuristic. The heuristic splits the sorted job set in tuples of m consecutive jobs ( 1 , ⋯ , m ; m + 1 , ⋯ , 2 m ; etc.) and sorts the tuples in non-increasing order of the difference (slack) between largest job and smallest job in the tuple. Then, given this new ordering of the job set, list scheduling is applied. This approach strongly outperforms LPT on benchmark literature instances and is competitive with more involved approaches such as COMBINE and LDM. [ABSTRACT FROM AUTHOR]

We study problems that integrate buy-at-bulk network design into the classical (connected) facility location problem. In such problems, we need to open facilities, build a routing network, and route every client demand to an open facility. Furthermore, capacities of the edges can be purchased in discrete units from K different cable types with costs that satisfy economies of scale. We extend the linear programming framework of Talwar (IPCO 2002) for the single-source buy-at-bulk problem to these variants and prove integrality gap upper bounds for both facility location and connected facility location buy-at-bulk problems. For the unconnected variant we prove an integrality gap bound of O(K), and for the connected version, we get the first LP-based bound of O(1). [ABSTRACT FROM AUTHOR]

We study the Unsplittable Flow problem (UFP) on trees with a submodular objective function. The input to this problem is a tree with edge capacities and a collection of tasks, each characterized by a source node, a sink node, and a demand. A subset of the tasks is feasible if the tasks can simultaneously send their demands from the source to the sink without violating the edge capacities. The goal is to select a feasible subset of the tasks that maximizes a submodular objective function. Our main result is an O(klogn)-approximation algorithm for Submodular UFP on trees where k denotes the pathwidth of the given tree. Since every tree has pathwidth O(logn), we obtain an O(log2n) approximation for arbitrary trees. This is the first non-trivial approximation guarantee for the problem, matching the best known approximation ratio for UFP on trees with a linear objective function. Our main technical contribution is a new geometric relaxation for UFP on trees that builds on the recent work of Bonsma et al. (2014, FOCS), Anagnostopoulos et al. (Amazing 2+ϵ approximation for unsplittable flow on a path, SIAM, pp 26-41, 2014) for UFP on paths with a linear objective. Our relaxation is very structured, so it can be combined with the contention resolution framework of Chekuri et al. (2009, STOC). Our approach is robust and extends to several related problems, such as UFP with bag constraints and the Storage Allocation Problem. Additionally, we study the special case of UFP on trees with a linear objective and upward instances where, for each task, the source node is a descendant of the sink node. Such instances generalize UFP on paths. We build on the work of Bansal et al. (A quasi-PTAS for unsplittable flow on line graphs, ACM, pp 721-729, 2006) for UFP on paths and obtain a QPTAS for upward instances when the input data is quasi-polynomially bounded. We complement this result by showing that, unlike the path setting, upward instances are APX-hard if the input data is arbitrary. [ABSTRACT FROM AUTHOR]

Concave mixed-integer quadratic programming is the problem of minimizing a concave quadratic polynomial over the mixed-integer points in a polyhedral region. In this work we describe an algorithm that finds an ϵ-approximate solution to a concave mixed-integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in 1/ϵ, provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. The running time of the proposed algorithm is expected unless P=NP. [ABSTRACT FROM AUTHOR]

Real-world problems often have parameters that are uncertain during the optimization phase; stochastic optimization or stochastic programming is a key approach introduced by Beale and by Dantzig in the 1950s to address such uncertainty. Matching is a classical problem in combinatorial optimization. Modern stochastic versions of this problem model problems in kidney exchange, for instance. We improve upon the current-best approximation bound of 3.709 for stochastic matching due to Adamczyk et al. (in: Algorithms-ESA 2015, Springer, Berlin, 2015) to 3.224; we also present improvements on Bansal et al. (Algorithmica 63(4):733-762, 2012) for hypergraph matching and for relaxed versions of the problem. These results are obtained by improved analyses and/or algorithms for rounding linear-programming relaxations of these problems. [ABSTRACT FROM AUTHOR]

We consider a variety of NP-Complete network connectivity problems. We introduce a novel dual-based approach to approximating network design problems with cut-based linear programming relaxations. This approach gives a 3/2-approximation to MINIMUM 2-EDGE-CONNECTED SPANNING SUBGRAPH that is equivalent to a previously proposed algorithm. One well-studied branch of network design models ad hoc networks where each node can either operate at high or low power. If we allow unidirectional links, we can formalize this into the problem DUAL POWER ASSIGNMENT (DPA). Our dual-based approach gives a 3 / 2-approximation to DPA, improving the previous best approximation known of 11/7≈1.57. Another standard network design problem is MINIMUM STRONGLY CONNECTED SPANNING SUBGRAPH (MSCS). We propose a new problem generalizing MSCS and DPA called STAR STRONG CONNECTIVITY (SSC). Then we show that our dual-based approach achieves a 1.6-approximation ratio on SSC. As a consequence of our dual-based approximations, we prove new upper bounds on the integrality gaps of these problems. [ABSTRACT FROM AUTHOR]

The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of n jobs on m distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into m “subjobs” and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem. [ABSTRACT FROM AUTHOR]

Given an undirected simple graph G, a set of vertices is an r-clique transversal if it has at least one vertex from every r-clique. Such sets generalize vertex covers as a vertex cover is a 2-clique transversal. Perfect graphs are a well-studied class of graphs on which a minimum weight vertex cover can be obtained in polynomial time. Further, an r-clique transversal in a perfect graph is also a set of vertices whose deletion results in an (r-1)-colorable graph. In this work, we study the problem of finding a minimum weight r-clique transversal in a perfect graph. This problem is known to be NP-hard for r≥3 and admits a straightforward r-approximation algorithm. We describe two different r+12-approximation algorithms for the problem. Both the algorithms are based on (different) linear programming relaxations. The first algorithm employs the primal-dual method while the second uses rounding based on a threshold value. We also show that the problem is APX-hard and describe hardness results in the context of parameterized algorithms and kernelization. [ABSTRACT FROM AUTHOR]

The paper defines new distances between univariate probability distributions, based on the concept of the CVaR norm. We consider the problem of approximation of a discrete distribution by some other discrete distribution. The approximating distribution has a smaller number of atoms than the original one. Such problems, for instance, must be solved for generation of scenarios in stochastic programming. The quality of the approximation is evaluated with new distances suggested in this paper. We use CVaR constraints to assure that the approximating distribution has tail characteristics similar to the target distribution. The numerical algorithm is based on two main steps: (i) optimal placement of positions of atoms of the approximating distribution with fixed probabilities; (ii) optimization of probabilities with fixed positions of atoms. These two steps are iterated to find both optimal atom positions and probabilities. Numerical experiments show high efficiency of the proposed algorithms, solved with convex and linear programming. [ABSTRACT FROM AUTHOR]

In Part II, we study the unweighted tree augmentation problem (TAP) via the Lasserre (sum of squares) system. We prove that the integrality ratio of an SDP relaxation (the Lasserre tightening of an LP relaxation) is ≤32+ϵ, where ϵ>0 can be any small constant. We obtain this result by designing a polynomial-time algorithm for TAP that achieves an approximation guarantee of (32+ϵ) relative to the SDP relaxation. The algorithm is combinatorial and does not solve the SDP relaxation, but our analysis relies on the SDP relaxation. We generalize the combinatorial analysis of integral solutions from the previous literature to fractional solutions by identifying some properties of fractional solutions of the Lasserre system via the decomposition result of Karlin et al. (Integer Programming and Combinatorial Optimization, LNCS, volume 6655, Springer, pp 301–314, 2011). [ABSTRACT FROM AUTHOR]

We present a fast combinatorial 3/4-approximation algorithm for the maximum asymmetric TSP with weights zero and one. The approximation factor of this algorithm matches the currently best one given by Bläser in 2004 and based on linear programming. Our algorithm first computes a maximum size matching and a maximum weight cycle cover without certain cycles of length two but possibly with half-edges - a half-edge of a given edge e is informally speaking a half of e that contains one of the endpoints of e. Then from the computed matching and cycle cover it extracts a set of paths, whose weight is large enough to be able to construct a traveling salesman tour with the claimed guarantee. [ABSTRACT FROM AUTHOR]

We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-nonmigratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-nonmigratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem. [ABSTRACT FROM AUTHOR]

Process systems engineering faces increasing demands and opportunities for better process modeling and optimization strategies, particularly in the area of dynamic operations. Modern optimization strategies for dynamic optimization trace their inception to the groundbreaking work Pontryagin and his coworkers, starting 60 years ago. Since then the application of large-scale non-linear programming strategies has extended their discoveries to deal with challenging real-world process optimization problems. This study discusses the evolution of dynamic optimization strategies and how they have impacted the optimal design and operation of chemical processes. We demonstrate the effectiveness of dynamic optimization on three case studies for real-world reactive processes. In the first case, we consider the optimal design of runaway reactors, where simulation models may lead to unbounded profiles for many choices of design and operating conditions. As a result, optimization based on repeated simulations typically fails, and a simultaneous, equationbased approach must be applied. Next we consider optimal operating policies for grade transitions in polymer processes. Modeled as an optimal control problem, we demonstrate how product specifications lead to multistage formulations that greatly improve process performance and reduce waste. Third, we consider an optimization strategy for the integration of scheduling and dynamic process operation for general continuous/batch processes. The method introduces a discrete time formulation for simultaneous optimization of scheduling and operating decisions. For all of these cases we provide a summary of directions and challenges for future integration of these tasks and extensions in optimization formulations and strategies. [ABSTRACT FROM AUTHOR]

The generalized connectivity of a graph is a natural generalization of the connectivity and can serve for measuring the capability of a network G to connect any k vertices in G. Given a graph $$G=(V,E)$$ and a subset $$S\subseteq V$$ of at least two vertices, we denote by $$\kappa _G(S)$$ the maximum number r of edge-disjoint trees $$T_1, T_2, \ldots , T_r$$ in G such that $$V(T_i)\cap V(T_j)=S$$ for any pair of distinct integers i, j, where $$1\le i,j\le r$$ . For an integer k with $$2\le k\le n$$ , the generalized k- connectivity is defined as $$\kappa _k(G)=\min \{\kappa _G(S)| S\subseteq V(G)\ \mathrm{and}\ |S|=k\}$$ . That is, $$\kappa _k(G)$$ is the minimum value of $$\kappa _G(S)$$ over all k-subsets S of vertices. The study of Cayley graphs has many applications in the field of design and analysis of interconnection networks. Let Sym( n) be the group of all permutations on $$\{1,\ldots ,n\}$$ and $${\mathcal {T}}$$ be a set of transpositions of Sym( n). Let $$G({\mathcal {T}})$$ be the graph on n vertices $$\{1,2,\ldots ,n\}$$ such that there is an edge ij in $$G({\mathcal {T}})$$ if and only if the transposition $$[ij]\in {\mathcal {T}}$$ . If $$G({\mathcal {T}})$$ is a tree, we use the notation $${\mathbb {T}}_n$$ to denote the Cayley graph $$Cay(Sym(n),{\mathcal {T}})$$ on symmetric groups generated by $$G({\mathcal {T}})$$ . If $$G({\mathcal {T}})$$ is a cycle, we use the notation $$MB_{n}$$ to denote the Cayley graph $$Cay(Sym(n),{\mathcal {T}})$$ on symmetric groups generated by $$G({\mathcal {T}})$$ . In this paper, we investigate the generalized 3-connectivity of $${\mathbb {T}}_{n}$$ and $$MB_{n}$$ and show that $$\kappa _{3}({\mathbb {T}}_{n})=n-2$$ and $$\kappa _{3}(MB_{n})=n-1$$ . [ABSTRACT FROM AUTHOR]

A covering problem is an integer linear program of type $$\min \{c^Tx\mid Ax\ge D,\ 0\le x\le d,\ x \in \mathbb {Z}\}$$ where $$A\in \mathbb {Z}^{m\times n}_+$$ , $$D\in \mathbb {Z}_+^m$$ , and $$c,d\in \mathbb {Z}_+^n$$ . In this paper, we study covering problems with additional precedence constraints $$\{x_i\le x_j \ \forall j\preceq i \in \mathcal {P}\}$$ , where $$\mathcal {P}=([n], \preceq )$$ is some arbitrary, but fixed partial order on the items represented by the column-indices of A. Such precedence constrained covering problems ( PCCPs) are of high theoretical and practical importance even in the special case of the precedence constrained knapsack problem, that is, where $$m=1$$ and $$d\equiv 1$$ . Our main result is a strongly-polynomial primal-dual approximation algorithm for PCCP with $$d\equiv 1$$ . Our approach generalizes the well-known knapsack cover inequalities to obtain an IP formulation which renders any explicit precedence constraints redundant. The approximation ratio of this algorithm is upper bounded by the width of $$\mathcal {P}$$ , that is, by the size of a maximum antichain in $$\mathcal {P}$$ . Interestingly, this bound is independent of the number of constraints. We are not aware of any other results on approximation algorithms for PCCP on arbitrary posets $$\mathcal {P}$$ . For the general case with $$d\not \equiv 1$$ , we present pseudo-polynomial algorithms. Finally, we show that the problem does not admit a PTAS under standard complexity assumptions. [ABSTRACT FROM AUTHOR]

Mutation region detection is the first step of searching for a disease gene and has facilitated the identification of several hundred human genes that can harbor mutations leading to a disease phenotype. Recently, the closest shared center problem (CSC) was proposed as a core to solve the mutation region detection problem when the pedigree is not given (Ma et al. in IEEE ACM Trans Comput Biol Bioinform 9(2):372-384, 2012). A ratio-2 approximation algorithm was proposed for the CSC problem in Ma et al. (IEEE ACM Trans Comput Biol Bioinform 9(2):372-384, 2012). In this paper, we will design a polynomial time approximation scheme for this problem. [ABSTRACT FROM AUTHOR]

R. Lavi and C. Swamy (FOCS 2005, J. ACM 58(6), 25, 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees. [ABSTRACT FROM AUTHOR]

An alternative formulation of collaborative optimization (CO) combined with linear approximations (CLA-CO) is recently developed to improve the computational efficiency of CO. However, for optimization problems with nonconvex constraints, conflicting linear approximations may be added into the system level in the CLA-CO iteration process. In this case, CLA-CO is inapplicable because the conflicting constraints lead to a problem that does not have any feasible region. In this paper, a linear approximation filter (LAF) strategy for CLA-CO is proposed to address the application difficulty with nonconvex constraints. In LAF strategy, whether conflict exists is first identified through transforming the identification problem into the existence problem of feasible region of linear programming; then, the conflicting linear approximations are coordinated by eliminating the larger violated linear approximations. Thereafter, the minimum violated linear approximation replaces the accumulative linear approximations as the system-level constraint. To evaluate the violation of linear approximation, a quantification of the violation is introduced based on the CO process. By using the proposed LAF strategy, CLA-CO can solve the optimization problems with nonconvex constraints. The verification of CLA-CO with LAF strategy to three optimizations, a numerical test problem, a speed reducer design problem, and a compound cylinder design problem, illustrates the capabilities of the proposed LAF strategy. [ABSTRACT FROM AUTHOR]

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this problem and their implications on the approximability of the problem. First we show that the straightforward LP, extending the approach for the original problem, has an integrality gap of 3 and yields an approximation algorithm of the same factor. By applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to $$1+\phi $$ , where $$\phi $$ is the golden ratio. Since this bound remains tight for the seemingly stronger machine configuration LP, we propose a new job configuration LP that is based on an infinite continuum of fractional assignments of each job to the machines. We prove that this LP has a finite representation and can be solved in polynomial time up to any accuracy. Interestingly, we show that our problem cannot be approximated within a factor better than $$\frac{e}{e-1}\approx 1.582\, (\hbox {unless } \mathcal {P}=\mathcal {NP})$$ , which is larger than the inapproximability bound of 1.5 for the original problem. [ABSTRACT FROM AUTHOR]

We consider the problem of computing a large stable matching in a bipartite graph $$G = (A\cup B, E)$$ where each vertex $$u \in A\cup B$$ ranks its neighbors in an order of preference, perhaps involving ties. Let the matched partner of u in a matching M be M( u). A matching M is said to be stable if there is no edge ( a, b) such that a is unmatched or prefers b to M( a) and similarly, b is unmatched or prefers a to M( b). While a stable matching in G can be easily computed in linear time by the Gale-Shapley algorithm, it is known that computing a maximum size stable matching is APX-hard. In this paper we first consider the case when the preference lists of vertices in A are strict while the preference lists of vertices in B may include ties. This case is also APX-hard and the current best approximation ratio known here is 25/17 $$\approx 1.4706$$ which relies on solving an LP. We improve this ratio to 22/15 $$\approx 1.4667$$ by a simple linear time algorithm. Here we first compute a half-integral stable matching in $$\{0,0.5,1\}^{|E|}$$ and then round it to an integral stable matching M. The ratio $$|\mathsf {OPT}|/{|M|}$$ is bounded via a payment scheme that charges other components in $$\mathsf {OPT}\oplus M$$ to cover the costs of length-5 augmenting paths. There will be no length-3 augmenting paths here. We next consider the following special case of two-sided ties, where every tie length is 2. This case is known to be UGC-hard to approximate to within 4/3. We show a 10/7 $$\approx 1.4286$$ approximation algorithm here that runs in linear time. [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]

In modern data centers and cloud computing systems, jobs often require resources distributed across nodes providing a wide variety of services. Motivated by this, we study the Coupled Placement problem, in which we place jobs into computation and storage nodes with capacity constraints, so as to optimize some costs or profits associated with the placement. The coupled placement problem is a natural generalization of the widely-studied generalized assignment problem, which concerns the placement of jobs into single nodes providing one kind of service. We also study a further generalization, the k- Sided Placement problem, in which we place jobs into k-tuples of nodes, each node in a tuple offering one of k services. For both the coupled and k-sided placement problems, we consider minimization and maximization versions. In the minimization versions ( MinCPand Min $$k$$ SP), the goal is to achieve minimum placement cost, while incurring a minimum blowup in the capacity of the individual nodes. Our first main result is an algorithm for Min $$k$$ SP that achieves optimal cost while increasing capacities by at most a factor of $$k+1$$ , also yielding the first constant-factor approximation for MinCP. In the maximization versions ( MaxCP and Max $$k$$ SP), the goal is to maximize the total weight of the jobs that are placed under hard capacity constraints. Max $$k$$ SP can be expressed as a k-column sparse integer program, and can be approximated to within a factor of O( k) factor using randomized rounding of a linear program relaxation. We consider alternative combinatorial algorithms that are much more efficient in practice. Our second main result is a local search based combinatorial algorithm that yields a 15-approximation and $$O(k^2)$$ -approximation for MaxCP and Max $$k$$ SP respectively. Finally, we consider an online version of Max $$k$$ SP and present algorithms that achieve logarithmic competitive ratio under certain necessary technical assumptions. [ABSTRACT FROM AUTHOR]

The Joint Replenishment Problem ( $${\hbox {JRP}}$$ ) is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers' waiting costs. We study the approximability of $${\hbox {JRP-D}}$$ , the version of $${\hbox {JRP}}$$ with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of $$1.207$$ , a stronger, computer-assisted lower bound of $$1.245$$ , as well as an upper bound and approximation ratio of $$1.574$$ . The best previous upper bound and approximation ratio was $$1.667$$ ; no lower bound was previously published. For the special case when all demand periods are of equal length, we give an upper bound of $$1.5$$ , a lower bound of $$1.2$$ , and show APX-hardness. [ABSTRACT FROM AUTHOR]