Search

We present a new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem. Its approximation ratio is 4 3 , which matches the current best ratio. The approximation ratio of the algorithm is 6 5 on subcubic graphs, which is an improvement upon the previous best ratio of 5 4. The algorithm is a novel extension of the primal-dual schema, which consists of two distinct phases. Both the algorithm and the analysis are much simpler than those of the previous approaches. [ABSTRACT FROM AUTHOR]

The squared metric k -facility location problem is a frequently encountered generalization of the k -means problem, where a specific cost should be paid for opening each facility. The current best approximation ratio for this problem is 44.473 + ϵ , which was obtained using a local search algorithm. We advance the state-of-the-art for the problem by devising a Lagrangian relaxation-based algorithm that achieves an improved approximation guarantee of 36.342 + ϵ. Our improvement comes from a new deterministic rounding approach, which exploits the properties of the squared metric. • We give a (36.342 + ϵ) -approximation algorithm for the squared metric k -facility location problem. • We obtain a well-behaved fractional solution to the squared metric k -facility location problem based on the framework of Lagrangian relaxation. • We give a new deterministic rounding approach that exploits the properties of the squared metric. [ABSTRACT FROM AUTHOR]

This work considers the Minimum Path-Collection Exact Cover (PCEC) and the Minimum k -Path Splitting Exact Cover (k-PSEC). Both problems receive a digraph G and a set P of paths in G , and their objective is to find a minimum cardinality set S of paths, whose elements are arc-disjoint and cover all arcs of G. Despite the similarities, the solutions for each problem must satisfy different properties. For k-PSEC , the set S must be obtained by splitting the paths in P in order to guarantee that no element of S has length greater than a given integer k. For PCEC , the paths in P cannot be split, and the elements of S are single arcs of G or complete paths of P. PCEC and k-PSEC have practical applications in network design and network monitoring systems, being also natural versions of graph covering problems. However, there are no theoretical studies on their complexity. This work not only presents NP-hardness results for the problems, but also proves that, unless P = NP , PCEC cannot be | P | O (1) -approximated in polynomial-time. Moreover, polynomial-time algorithms are presented for paths, cycles, and trees, and polynomial-time approximation algorithms are proposed for special cases of k-PSEC. [ABSTRACT FROM AUTHOR]

• We study the heterogeneous weighted delivery (HWD) problem, which was introduced in [Bärtschi et al., STACS'17]. • We efficiently 8-approximate HWD with k = O (log ⁡ n) agents, closing an open problem in [Bärtschi et al., ATMOS'17]. • We design a O (k) -approximation algorithm that runs in polynomial time regardless of the value of k. • We design a polynomial-time O ˜ (log 3 ⁡ n) -approximation algorithm. • We show that the HWD problem is 36-approximable in polynomial time when each agent has one of two possible consumption rates. We study the heterogeneous weighted delivery (HWD) problem introduced in [Bärtschi et al., STACS'17] where k heterogeneous mobile agents (e.g., robots, vehicles, etc.), initially positioned on vertices of an n -vertex edge-weighted graph G , have to deliver m messages. Each message is initially placed on a source vertex of G and needs to be delivered to a target vertex of G. Each agent can move along the edges of G and carry at most one message at any time. Each agent has a rate of energy consumption per unit of traveled distance and the goal is that of delivering all messages using the minimum overall amount of energy. This problem has been shown to be NP-hard even when k = 1 , and is 4 ρ -approximable where ρ is the ratio between the maximum and minimum energy consumption of the agents. In this paper, we provide approximation algorithms with approximation ratios independent of the energy consumption rates. First, we design a polynomial-time 8-approximation algorithm for k = O (log ⁡ n) , closing a problem left open in [Bärtschi et al., ATMOS'17]. This algorithm can be turned into an O (k) -approximation algorithm that always runs in polynomial-time, regardless of the values of k. Then, we show that HWD problem is 36-approximable in polynomial-time when each agent has one of two possible consumption rates. Finally, we design a polynomial-time O ˜ (log 3 ⁡ n) -approximation algorithm for the general case. [ABSTRACT FROM AUTHOR]

Consider an information diffusion process on a graph G that starts with k > 0 burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as k other unburnt vertices. The k-burning number of G is the minimum number of steps b k (G) such that all the vertices can be burned within b k (G) steps. Note that the last step may have smaller than k unburnt vertices available, where all of them are burned. The 1-burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to k -burning number allows us to examine different worst-case contagion scenarios by varying the spread factor k. In this paper we prove that computing k -burning number is APX-hard, for any fixed constant k. We then give an O ((n + m) log ⁡ n) -time 3-approximation algorithm for computing k -burning number, for any k ≥ 1 , where n and m are the number of vertices and edges, respectively. Finally, we show that even if the burning sources are given as an input, computing a burning sequence itself is an NP-hard problem. [ABSTRACT FROM AUTHOR]

• We combine the distorted objective function, the threshold and the greedy algorithms. • This problem includes some previously studied problems as special cases, such as submodular+supermodular maximization, γ -weakly submodular function maximization. • The approximation ratio in Algorithm 1 is the minimum of 1 − k f e − 1 and 1 − (k g) 2 , improving the result obtained by Bai et al. • Algorithm 1 has an approximation ratio 1 − (1 − γ + γ α) e − γ , improving the result obtained by Bian et al. • Set g (S) = 0. Algorithm 2 has an approximation ratio γ γ + 1 , improving the approximate ratio 1 − 1 2 γ by Wang et al. The concept of submodularity finds wide applications in data science, artificial intelligence, and machine learning, providing a boost to the investigation of new ideas, innovative techniques, and creative algorithms to solve different submodular optimization problems arising from a diversity of applications. However pure submodular or supermodular problems only represent a small portion of the problems we are facing in real life applications. The main focus of this work is to consider a non-submodular function maximization problem subject to a cardinality constraint, where the objective function is the sum of a monotone γ -weakly submodular function and a supermodular function. This problem includes some previously studied problems as special cases, such as the submodular+supermodular maximization problem when γ =1, and the γ -weakly submodular function maximization problem when the supermodular function is void. We present greedy algorithms for this generalized problem under both offline and streaming models, improving existing results. [ABSTRACT FROM AUTHOR]

• The smallest minimum color-spanning circle (S-MCSC) problem can be solved in O (n k log ⁡ n) time. • The largest minimum color-spanning circle (L-MCSC) problem is NP-Hard. • A 1 3 -factor (1 2 , if no two distinct color disks intersect) approximation to the L-MCSC problem can be computed in O (n k log ⁡ n) time. Let R be a set of n colored imprecise points, where each point is colored by one of k colors. Each imprecise point is specified by a unit disk in which the point lies. We study the problem of computing the smallest and the largest possible minimum color spanning circle, among all possible choices of points inside their corresponding disks. We present an O (n k log ⁡ n) time algorithm to compute a smallest minimum color spanning circle. Regarding the largest minimum color spanning circle, we show that the problem is NP - Hard and present a 1 3 -factor approximation algorithm. We improve the approximation factor to 1 2 for the case where no two disks of distinct color intersect. [ABSTRACT FROM AUTHOR]

• Propose a new problem: prize-collecting sweep cover problem. • Give a 5-LMP algorithm for prize-collecting sweep cover assuming constant number of base-stations. • Give a 2-LMP algorithm for the rooted prize-collecting forest with k components problem. In a sweep cover problem, positions of interest (PoIs) are required to be visited periodically by mobile sensors. In this paper, we propose a new sweep cover problem: the prize-collecting sweep cover problem (PCSC), in which penalty is incurred by those PoIs which are not sweep-covered, and the goal is to minimize the covering cost plus the penalty. Assuming that every mobile sensor has to be linked to some base station, and the number of base stations is upper bounded by a constant, we present a 5-LMP (Lagrangian Multiplier Preserving) algorithm. As a step stone, we propose the prize-collecting forest with k components problem (PCF k), which might be interesting in its own sense, and presented a 2-LMP for rooted PCF k. [ABSTRACT FROM AUTHOR]

K-best enumeration , which asks to output k -best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, k -best enumeration tends to be intractable since, in many cases, finding one optimum solution is NP-hard. To overcome this difficulty, we combine k -best enumeration with a concept of enumeration algorithms called approximation enumeration algorithms. As a main result, we propose a 4-approximation algorithm for minimal connected edge dominating sets which outputs k minimal solutions with cardinality at most 4 ⋅ OPT ‾ , where OPT ‾ is the cardinality of a minimum solution which is not outputted by the algorithm. Our proposed algorithm runs in O (n m 2 Δ) delay, where n , m , Δ are the number of vertices, the number of edges, and the maximum degree of an input graph. [ABSTRACT FROM AUTHOR]

Let T be a tessellation composed of equilateral triangular regions, where each region has an associated positive weight. We present two methods that discretize the space based on the placement of Steiner points in the cells of T. Using such a discretization, we can use Dijkstra's algorithm for computing the shortest path in the geometric graph obtained. This will lead us to two approximation algorithms for solving the Weighted Region Problem. For a given parameter ε ∈ (0 , 1 ] , the first discretization scheme provides an approximate path that is (1 + 0.428 ε) times better than the approximation given by Aleksandrov et al. (2005) [5]. The other discretization scheme uses at least ( ε + 2 ε + 4 ε + 4) log 2 ⁡ e fewer points per segment of the triangulation with the same approximation factor. [ABSTRACT FROM AUTHOR]

In the Upper Dominating Set problem, the goal is to find a minimal dominating set of maximum size. We study the complexity of parameterized algorithms for Upper Dominating Set , as well as its sub-exponential approximation. First, we prove that, under the ETH, Upper Dominating Set cannot be solved in time O (n o (k)) (improving on O (n o (k))), and in the same time we show under the same complexity assumption that for any constant ratio r and any ε > 0 , there is no r -approximation algorithm running in time O (n k 1 − ε ). Then, we settle the problem's complexity parameterized by pathwidth by giving an algorithm running in time O ⁎ (6 p w) (improving the current best O ⁎ (7 p w)), and a lower bound showing that our algorithm is the best we can get under the SETH. Furthermore, we obtain a simple sub-exponential approximation algorithm for this problem: an algorithm that produces an r -approximation in time n O (n / r) , for any desired approximation ratio r < n. We finally show that this time-approximation trade-off is tight, up to an arbitrarily small constant in the second exponent: under the randomized ETH, and for any ratio r > 1 and ε > 0 , no algorithm can output an r -approximation in time n (n / r) 1 − ε . Hence, we completely characterize the approximability of the problem in sub-exponential time. • We show that under ETH, Upper Dominating Set cannot be solved in time n o (k). • We give a 6 p w algorithm parameterized by pathwidth and show it is optimal under SETH. • We obtain a tight time-approximation trade-off under the ETH. [ABSTRACT FROM AUTHOR]

k-median with service installation costs is a frequently encountered problem in applications involving multiple service requirements, which generalizes the standard k -median problem in that each client is associated with a specific service and can only be connected to the facilities where the service is installed. In this paper, we give a (13.349 + ϵ) -approximation algorithm for the k -median with service installation costs problem, improving upon the previous best approximation ratio of 18. We propose a new deterministic rounding approach to deal with the challenges caused by the service requirements, which is the crucial step in getting the improved ratio. • We give a (13.349 + ϵ) -approximation algorithm for the k -median with service installation costs problem. • We obtain a well-behaved fractional solution to the problem based on the framework of Lagrangian relaxation. • We give a new deterministic rounding approach to deal with the challenges caused by the service requirements. [ABSTRACT FROM AUTHOR]

We consider the rooted orienteering problem in Euclidean space: Given n points P in R d , a root point s ∈ P and a budget B > 0 , find a path that starts from s , has total length at most B , and visits as many points of P as possible. This problem is known to be NP-hard, hence we study (1 − δ) -approximation algorithms. The previous Polynomial-Time Approximation Scheme (PTAS) for this problem, due to Chen and Har-Peled (2008), runs in time n O (d d / δ) 2 (d / δ) O (d) , and improving on this time bound was left as an open problem. Our main contribution is a PTAS with a significantly improved time complexity of n O (1 / δ) 2 (d / δ) O (d) . A known technique for approximating the orienteering problem is to reduce it to solving 1 / δ correlated instances of rooted k -TSP (a k -TSP tour is one that visits at least k points). However, the k -TSP tours in this reduction must achieve a certain excess guarantee (namely, their length can surpass the optimum length only in proportion to a parameter of the optimum called excess) that is stronger than the usual (1 + δ) -approximation. Our main technical contribution is to improve the running time of these k -TSP variants, particularly in its dependence on the dimension d. Indeed, our running time is polynomial even for a moderately large dimension, roughly up to d = O (log ⁡ log ⁡ n) instead of d = O (1). [ABSTRACT FROM AUTHOR]

The support of a flow x in a network is the subdigraph induced by the arcs uv for which x (u v) > 0. We discuss a number of results on flows in networks where we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example deciding whether a network N = (D , s , t , c) has a maximum flow x such that the maximum out-degree of the support D x of x is at most 2 is NP-complete as it contains the 2-linkage problem as a very special case. Another problem which is NP-complete for the same reason is that of computing the maximum flow we can send from s to t along p paths (called a maximum p -path-flow) in N. Baier et al. (2005) gave a polynomial time algorithm which finds a p -path-flow x whose value is at least 2 3 of the value of a optimum p -path-flow when p ∈ { 2 , 3 } , and at least 1 2 when p ≥ 4. When p = 2 , they show that this is best possible unless P=NP. We show for each p ≥ 2 that the value of a maximum p -path-flow cannot be approximated by any ratio larger than 9 11 , unless P=NP. We also consider a variant of the problem where the p paths must be disjoint. For this problem, we give an algorithm which gets within a factor 1 H (p) of the optimum solution, where H (p) is the p 'th harmonic number (H (p) ∼ ln ⁡ (p)). We show that in the case where the network is acyclic, we can find such a maximum p -path-flow in polynomial time for every p. We determine the complexity of a number of related problems concerning the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some sense best possible. [ABSTRACT FROM AUTHOR]

Given an edge-weighted metric complete graph with n vertices, the maximum weight metric triangle packing problem is to find a set of n / 3 vertex-disjoint triangles with the total weight of all triangles in the packing maximized. Several simple methods can lead to a 2/3-approximation ratio. However, this barrier is not easy to break. Chen et al. proposed a randomized approximation algorithm with an expected ratio of (0.66768 − ε) for any constant ε > 0. In this paper, we improve the approximation ratio to (0.66835 − ε). Furthermore, we can derandomize our algorithm. [ABSTRACT FROM AUTHOR]

The fair k -center problem has been paid lots of attention recently. In the fair k -center problem, we are given a set X of points in a metric space and a parameter k ∈ Z + , where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k -center problem objective is minimized. In this paper, we consider the fair k -center problem with outliers and capacity constraints, denoted as the fair k -center with outliers (F k CO) problem and the capacitated fair k -center (CF k C) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + ϵ) -approximations with FPT time for the F k CO and CF k C problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the F k CO problem with some reasonable assumptions. [ABSTRACT FROM AUTHOR]

We continue to study coherent partitions of graphs whereby the vertex set is partitioned into subsets that induce biclique spanned subgraphs. The problem of identifying the minimum number of edges to obtain biclique spanned connected components (CNP), called the coherence number, is NP-hard even on bipartite graphs. Here, we propose a graph transformation geared towards obtaining an O (log ⁡ n) -approximation algorithm for the CNP on a bipartite graph with n vertices. The transformation is inspired by a new characterization of biclique spanned subgraphs. In addition, we study coherent partitions on prime graphs, and show that finding coherent partitions reduces to the problem of finding coherent partitions in a prime graph. Therefore, these results provide future directions for approximation algorithms for the coherence number of a given graph. [ABSTRACT FROM AUTHOR]

Sorting permutations with various operations has applications in macro rearrangement of genes in a genome and the design of computer interconnection networks. Block-interchange is a powerful operation that swaps two substrings that are called as blocks in literature, in a given permutation. When the blocks are restricted to be adjacent then one obtains a well studied operation: transposition. We call either a prefix or a suffix as an extreme. Restricting one of the swapped blocks to be an extreme in block-interchange operation yields a prefix or a suffix block-interchange respectively, the two types of extreme block-interchanges. For prefix block-interchange operation over permutations we design: (i) an optimum algorithm to sort reverse permutation, R n , in n /2 moves, (ii) a simple 2-approximation algorithm, and (iii) for permutations with O (1) cycles, a 4/3 approximation algorithm. Due to symmetry, these results apply to suffix block-interchange operation also. [ABSTRACT FROM AUTHOR]

• A new randomized approximation algorithm for the size of set union problem. • The algorithm relaxes the computational model that requires exact set size and random element generator. • The algorithm runs in constant rounds and runs sublinear in time under certain condition. We develop a randomized approximation algorithm for the size of set union problem | A 1 ∪ A 2 ∪... ∪ A m | , which is given a list of sets A 1 ,... , A m with approximate set size m i for A i with m i ∈ ((1 − β L) | A i | , (1 + β R) | A i |) , and biased random generators with probability Prob (x = RandomElement (A i)) ∈ [ 1 − α L | A i | , 1 + α R | A i | ] for each input set A i and element x ∈ A i , where i = 1 , 2 ,... , m and α L , α R , β L , β R ∈ (0 , 1). The approximation ratio for | A 1 ∪ A 2 ∪... ∪ A m | is in the range [ (1 − ϵ) (1 − α L) (1 − β L) , (1 + ϵ) (1 + α R) (1 + β R) ] for any ϵ ∈ (0 , 1). The complexity of the algorithm is measured by both time complexity and round complexity. One round of the algorithm has non-adaptive accesses to those RandomElement (A i) functions 1 ≤ i ≤ m , and membership queries (x ∈ A i ?) to input sets A i with 1 ≤ i ≤ m. Our algorithm gives an approximation scheme with O (m ⋅ (log ⁡ m) 7) running time and O (log ⁡ m) rounds in contrast to the existing algorithm [1] that needs Ω (m) rounds in the worst case with O ((1 + ϵ) m / ϵ 2) running time, where m is the number of sets. Our algorithm gives a flexible tradeoff with time complexity O (m 1 + ξ) and round complexity O (1 ξ) for any ξ ∈ (0 , 1). Our algorithm runs sublinear in time under certain condition that each element in A 1 ∪ A 2 ∪... ∪ A m belongs to m a sets for any fixed a > 0 , to our best knowledge, we have not seen any sublinear results about this problem. Our algorithm can handle input sets that can generate random elements with bias, and its approximation ratio depends on the bias. We prove that it is #P-hard to count the number of lattice points in a set of balls, and we also show that there is no polynomial time algorithm to approximate the number of lattice points in the intersection of n -dimensional balls unless P=NP. As applications of our algorithm, we propose approximation algorithms for counting the number of lattice points in a union of high dimensional balls and for the maximal coverage problem with balls. [ABSTRACT FROM AUTHOR]

• Present a deterministic approximation algorithm for submodular maximization with a curvature parameter α. • Generalize the previous deterministic 0.5008-approximation due to Buchbinder et al., achieving an identical ratio of 0.5008 when α = 1. • Achieve a ratio of 1 for α = 0 for which the function is actually linear that the problem is polynomial solvable. • Devise more sophisticated analysis on the inequalities about monotonicity with curvature via mathematical tools such as infinite series. In this paper, we study the generalized submodular maximization problem with a non-negative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter α ∈ [ 0 , 1 ] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for α = 1. For general value of the curvature parameter α ∈ [ 0 , 1 ] , we present an approximation algorithm with a factor of 1 + h α (y) + Δ ⋅ [ 3 + α − (2 + α) y − (1 + α) h α (y) ] 2 + α + (1 + α) (1 − y) , where y ∈ [ 0 , 1 ] is a predefined parameter for tuning the ratio. In particular, when α = 1 we obtain a ratio 0.5008 when setting y = 0.9 , coinciding with the renowned state-of-art approximate ratio; when α = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions. [ABSTRACT FROM AUTHOR]

The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common one is the receiver-centric, in which the interference of a node p is defined as the number of other nodes whose transmission range covers p. In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized. For the one-dimensional case, we show how to solve the problem optimally in O (n 3) time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

The Maximum Vertex Coverage problem (abbreviated as MVC) is to maximum the number of edges covered by a set of vertices of size exactly K on a graph. This problem is the dual of the vertex cover problem and has attracted a lot of interests in the literature of approximation algorithm. So far, the best approximation factor for the MVC problem is 3/4, which is obtained using an LP-rounding method. The main results of this paper are new approximation algorithms for MVC on cubic graphs and 3-bounded graphs (the vertex degrees are at most 3). The approximation factor on cubic graphs is 79/90 (≈0.878), which is tight by analyzing the existence of a feasible solution for a linear programming system. This algorithm can also be extended to 3-bounded graphs and guarantees an approximation factor of 19/24 (≈0.792). [ABSTRACT FROM AUTHOR]

• Scheduling problem with different types of calibrations on a single machine. • Two models are considered: jobs have agreeable deadlines and calibrations costs are agreeable. • Constant approximation algorithms are given. Machines usually require maintenance after running a fixed period. A calibration at a cost has to be performed during the process. Finding a feasible schedule minimizing the total cost of calibrations is of great importance. In this paper, we deal with a single machine scheduling model with K types of calibrations. A calibration of type k ∈ { 1 , ... , K } can be made instantaneously at any time point, which incurs a cost f k and can keep the machine active for a length T k. Given a set of n jobs with release times, deadlines, and processing times, the goal is to minimize the total cost of calibrations by assigning all jobs in the calibrated state, where job preemption is allowed. We investigate two agreeable settings. Regarding agreeable jobs, later release times imply later deadlines. We establish a pseudo-polynomial time optimal algorithm and a (3 + ε) -approximation algorithm. Moreover, if the largest job processing time is no more than any calibration length, it admits a (2 + ε) -approximation algorithm. As for agreeable calibrations, where the cost of each calibration is proportional to its length, a 2-approximation algorithm is presented. [ABSTRACT FROM AUTHOR]

• A new seeding algorithm is proposed for the fuzzy C-means problem. • Theoretical guarantees for both the new seeding algorithm and the fuzzy C-means++ algorithm are given. • Numerical experiments show the effectiveness of the new algorithm. As a kind of important soft clustering model, the fuzzy C -means method is widely applied in many fields. In this method, instead of the strict distributive ability in the classical k -means method, all the sample points are endowed with degrees of membership to each center to depict the fuzzy clustering. In this paper, we show that the fuzzy C -means++ algorithm, which introduces the k -means++ algorithm as a seeding strategy, gives a solution for which the approximation guarantee is O (k 2 ln ⁡ k). A novel seeding algorithm is then designed based on the contribution of the fuzzy potential function, which improves the approximation ratio to O (k ln ⁡ k). Preliminary numerical experiments are proposed to support the theoretical results of this paper. [ABSTRACT FROM AUTHOR]

We consider a two-stage production scheduling problem where each operation can be outsourced or processed in-house. For each operation in the same machine, the ratio of its outsourcing cost to its processing time is constant. The objective is to minimize the sum of the makespan and the total outsourcing cost. It is known that this problem is either polynomial time solvable or NP-hard according to the conditions of the ratios. Even though approximation algorithms for NP-hard cases had been developed, their tight worst-case performance ratios are still open. In this paper, we carefully analyze the approximation algorithms to identify their tight worst-case performance ratios for cases. In one case, we propose a new approximation algorithm with a better and tight worst-case performance ratio. In the process of analyzing the algorithm, we propose a technique utilizing nonlinear optimization. [ABSTRACT FROM AUTHOR]

The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7 n / 22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7 n / 22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way. [ABSTRACT FROM AUTHOR]

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 − o (1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) without an isolated edge, a set D ⊆ E is an edge total dominating set of G if every edge e ∈ E is adjacent to at least one edge of D. The Minimum Edge Total Dominating Set problem is to compute a minimum cardinality edge total dominating set of G. It is known that the decision version of the problem is NP-complete for bipartite graphs, chordal graphs, and planar graphs. On the positive side, the problem is efficiently solvable for trees. In this paper, we further study the complexity of this problem in other graph classes. We design a linear-time algorithm to compute a minimum cardinality edge total dominating set in chain graphs, a subclass of bipartite graphs. We also propose linear-time algorithms for two subclasses of chordal graphs, namely, split graphs and proper interval graphs with no cut vertices. In addition, we show that the problem is APX-complete for graphs with maximum degree 3 and propose an approximation algorithm for the problem in k -regular graphs, where k ≥ 4. We discuss the complexity difference between the Minimum Edge Dominating Set problem and Minimum Edge Total Dominating Set problem which seem to be closely related. [ABSTRACT FROM AUTHOR]

In this work, we investigate the problem of maximizing nonmonotone DR-submodular function (possibly negative) subject to cardinality constraints on an integer lattice space. We propose a M -Threshold Decrease Algorithm that uses a compensation constant M from a special decomposition h (x) = f (x) − g (x) , which achieves a 1 − e − δ − ϵ approximation guarantee. To ensure that the algorithm ends in finite time, the supremum of δ is δ (ϵ) = ϵ max s ∈ Ω ⁡ h (χ s | 0) 2 k max s ∈ Ω ⁡ g (χ s | 0) + ϵ max s ∈ Ω ⁡ h (χ s | 0). If max s ∈ Ω ⁡ h (χ s | 0) > 2 k max s ∈ Ω ⁡ g (χ s | 0) , there exists ϵ ⁎ = arg ⁡ max ϵ ∈ (0 , 1) ⁡ 1 − e − δ (ϵ) − ϵ such that 1 − e − δ (ϵ ⁎) − ϵ ⁎ > 0. This implies that there is a valid δ such that 1 − e − δ − ϵ > 0. To accelerate the algorithm, we employ a random subset to replace the ground set and propose a Random M -Threshold Decrease Algorithm, where δ (ϵ) = ϵ r max s ∈ Ω ⁡ h (χ s | 0) 2 n k max s ∈ Ω ⁡ g (χ s | 0) + [ k (n − r) + ϵ r ] max s ∈ Ω ⁡ h (χ s | 0) with r being the size of the random subset and n being the size of the ground set. Furthermore, we demonstrate that, based on the DR-ratio γ d and the DS decomposition, the M -Threshold Decrease Algorithm is also suitable for solving the monotone non-DR-submodular maximization problem, achieving a 1 − e − γ d δ − O (ϵ) approximation guarantee. Because γ d is a challenging metric to calculate, we refine the M -Threshold Decrease Algorithm, which can return an estimate of γ d. To the best of our knowledge, this is the first time that a single factor approximation ratio has been proposed for the nonmonotone DR-submodular maximization problem (possibly negative) subject to cardinality constraints. • This paper adopts the decomposition structure to compensate the non-monotonicity and non-negativity for DR-submodular maximization. • Using a compensation constant M , we design a 1 − e − δ − ϵ approximation algorithm, namely M -Threshold Decrease Algorithm. • Based on the DR-ratio γ d , our algorithm is a 1 − e − δ γ d − O (ϵ) approximation algorithm for monotone non-DR-submodular maximization. [ABSTRACT FROM AUTHOR]

• Consider the problem of finding low-rank approximations for norm in presence of ℓ p outliers in the dataset, where p ≥ 2. • Technique is sampling based and suggests additive and multiplicative approximation guarantees for the problem. • We extend our results to M-estimator loss functions and affine subspace approximation in presence of outliers. The subspace approximation problem with outliers, for given n points in d dimensions x 1 , x 2 , ... , x n ∈ R d , an integer 1 ≤ k ≤ d , and an outlier parameter 0 ≤ α ≤ 1 , is to find a k -dimensional linear subspace of R d that minimizes the sum of squared distances to its nearest (1 − α) n points. More generally, the ℓ p subspace approximation problem with outliers minimizes the sum of p -th powers of distances instead of the sum of squared distances. Even the case of p = 2 or robust PCA is non-trivial, and previous work requires additional assumptions on the input or generative models for it. Any multiplicative approximation algorithm for the subspace approximation problem with outliers must solve the robust subspace recovery problem, a special case in which the (1 − α) n inliers in the optimal solution are promised to lie exactly on a k -dimensional linear subspace. However, robust subspace recovery is Small Set Expansion (SSE)-hard, and known algorithmic results for robust subspace recovery require strong assumptions on the input, e.g., any d outliers must be linearly independent. In this paper, we show how to extend dimension reduction techniques and bi-criteria approximations based on sampling and coresets to the problem of subspace approximation with outliers. To get around the SSE-hardness of robust subspace recovery, we assume that the squared distance error of the optimal k -dimensional subspace summed over the optimal (1 − α) n inliers is at least δ times its squared-error summed over all n points, for some 0 < δ ≤ 1 − α. Under this assumption, we give an efficient algorithm to find a weak coreset or a subset of poly (k / ϵ) log ⁡ (1 / δ) log ⁡ log ⁡ (1 / δ) points whose span contains a k -dimensional subspace that gives a multiplicative (1 + ϵ) -approximation to the optimal solution. Our technique is based on the squared-length sampling algorithm suggested for low-rank approximation problems in the seminal work of Frieze, Kannan, and Vempala [12]. The running time of our algorithm is linear in n and d. Interestingly, our results hold even when the fraction of outliers α is large, as long as the obvious condition 0 < δ ≤ 1 − α is satisfied. We show similar results for subspace approximation with ℓ p error or more general M-estimator loss functions, and also give an additive approximation for the affine subspace approximation problem. [ABSTRACT FROM AUTHOR]

• Show that every interval graph G has an equitable tree- k -coloring for any integer k ≥ ⌈ Δ (G) + 1 / 2 ⌉. • Design linear algorithm for proper interval graphs. • Prove the NP-hardness of the problems. • Design a quadratic 2-approximation algorithm for the equitable tree coloring problem in chordal graphs. • Prove that the problem has no α -approximation algorithm for any α < 3 2. An equitable tree- k -coloring of a graph is a vertex k -coloring such that each color class induces a forest and the size of any two color classes differs by at most one. In this work, we show that every interval graph G has an equitable tree- k -coloring for any integer k ≥ ⌈ (Δ (G) + 1) / 2 ⌉ , solving a conjecture of Wu, Zhang and Li (2013) for interval graphs, and furthermore, give a linear-time algorithm for determining whether a proper interval graph admits an equitable tree- k -coloring for a given integer k. For disjoint union of split graphs, or K 1 , r -free interval graphs with r ≥ 4 , we prove that it is W 1 -hard to decide whether there is an equitable tree- k -coloring when parameterized by number of colors, or by treewidth, number of colors and maximum degree, respectively. On the positive side, we propose a quadratic 2-approximation algorithm for the equitable tree-coloring problem in chordal graphs. Moreover, it is proved that there is no α -approximation algorithm for any α < 3 2. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the two-stage submodular maximization problem, where there is a collection F = { f 1 ,... , f m } of m submodular functions which are defined on the same element ground set Ω. The goal is to select a subset S ⊆ Ω of size at most ℓ such that 1 m ∑ f ∈ F max T ⊆ S , T ∈ I ⁡ f (T) is maximized, where I denotes a specifically-defined independence system. We consider the two-stage submodular maximization with a P -matroid constraint and present a (1 / (P + 1)) (1 − 1 / e (P + 1)) -approximation algorithm. Furthermore, we extend the algorithm to the two-stage submodular maximization with a more generalized P -exchange system constraint and show the approximation ratio can be maintained with slightly modifications of the algorithm. [ABSTRACT FROM AUTHOR]

• We present the first linear-time approximation algorithm for non-monotone adaptive submodular maximization. • Our results do not rely on pointwise submodularity. • We present a faster algorithm for the monotone case. • We propose an enhanced algorithm for the montone case subject to a partition matroid constraint. • We develop a linear-time algorithm for maximizing fully adaptive submodular functions subject to a parition matroid constraint. In this paper, we study the non-monotone adaptive submodular maximization problem subject to a cardinality constraint. We first revisit the adaptive random greedy algorithm proposed in [13] , where they show that this algorithm achieves a 1 / e approximation ratio if the objective function is adaptive submodular and pointwise submodular. It is not clear whether the same guarantee holds under adaptive submodularity (without resorting to pointwise submodularity) or not. Our first contribution is to show that the adaptive random greedy algorithm achieves a 1 / e approximation ratio under adaptive submodularity. One limitation of the adaptive random greedy algorithm is that it requires O (n × k) value oracle queries, where n is the size of the ground set and k is the cardinality constraint. Our second contribution is to develop the first linear-time algorithm for the non-monotone adaptive submodular maximization problem. Our algorithm achieves a 1 / e − ϵ approximation ratio (this bound is improved to 1 − 1 / e − ϵ for monotone case), using only O (n ϵ − 2 log ⁡ ϵ − 1) value oracle queries. Notably, O (n ϵ − 2 log ⁡ ϵ − 1) is independent of the cardinality constraint. For the monotone case, we propose a faster algorithm that achieves a 1 − 1 / e − ϵ approximation ratio in expectation with O (n log ⁡ 1 ϵ) value oracle queries. We also generalize our study by considering a partition matroid constraint, and develop a linear-time algorithm for monotone and fully adaptive submodular functions. [ABSTRACT FROM AUTHOR]

We study the worst-case behavior of Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, we revisit a randomized approach of Boppana that forms a simple 1-round distributed algorithm, as well as a streaming algorithm and a preemptive online algorithm. We show that it gives a tight (Δ + 1) / 2 -approximation in unweighted graphs of maximum degree Δ, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a (Δ + 1) -approximation, but a simple modification results in an asymptotic expected 0.529 (Δ + 1) -approximation. [ABSTRACT FROM AUTHOR]

For a given b ∈ N n and a hypergraph H = (V , E) with maximum degree Δ, the b -set multicover problem which we are concerned with in this paper may be stated as follows: find a minimum cardinality subset C ⊆ E such that no vertex v i ∈ V is contained in less than b i hyperedges of C. Peleg, Schechtman, and Wool (1997) conjectured that for any fixed Δ and b = min i ⁡ b i , the problem cannot be approximated with a ratio strictly smaller than δ : = Δ − b + 1 , unless P = NP. In this paper, we show that the conjecture of Peleg et al. is not true on ℓ -uniform hypergraphs by presenting a polynomial-time approximation algorithm based on a matching/covering duality for hypergraphs due to Ray-Chaudhuri (1960), which we convert into an approximative form. The given algorithm yields a ratio smaller than (1 − b (ℓ + 1) Δ) Δ b. Moreover, we prove that the lower bound conjectured by Peleg et al. holds for regular hypergraphs under the unique games conjecture. [ABSTRACT FROM AUTHOR]

Vertex deletion problems on graphs involve finding a set of minimum number of vertices whose deletion results in a graph with some specific property. In a recent study on vertex deletion problems on split graphs, it was shown that transforming a split graph to a block graph or a threshold graph using minimum number of vertex deletions is NP -hard. We call the decision version of these problems as Split to Block Vertex Deletion (SBVD) and Split to Threshold Vertex Deletion (STVD), respectively. In this paper, we study the parameterized complexity of these problems with the number of vertex deletions, k , as a parameter. These problems are implicit 4- Hitting Set and thus admit an algorithm with running time O ⋆ (3.0755 k) , a kernel with O (k 3) vertices, and a 4-approximation algorithm. In this paper, we exploit the structural properties of the concerned graph classes and obtain a kernel for SBVD with O (k 2) vertices and FPT algorithms for SBVD and STVD with running times O ⋆ (2.3028 k) and O ⋆ (2.7913 k) , respectively. We further give improved approximation algorithms for SBVD and STVD. [ABSTRACT FROM AUTHOR]

In this paper, we consider the k -prize-collecting multicut on a tree (k -PCM(T)) problem. In this problem, we are given an undirected tree T = (V , E) , a set of m distinct pairs of vertices P = { (s 1 , t 1) , ... , (s m , t m) } and a parameter k with k ≤ m. Every edge in E has a nonnegative cost c e. Every pair (s i , t i) in P has a nonnegative penalty cost π i. Our goal is to find a multicut M that separates at least k pairs in P such that the total cost, including the edge cost of the multicut M and the penalty cost of the pairs not separated by M , is minimized. This problem generalizes the well-known multicut on a tree problem. Our main work is to present a (4 + ε) -approximation algorithm for the k -PCM(T) problem via the methods of primal-dual and Lagrangean relaxation, where ε is any fixed positive number. [ABSTRACT FROM AUTHOR]

The minimum tracking set problem is an optimization problem that deals with monitoring communication paths that can be used for exchanging point-to-point messages using as few tracking devices as possible. More precisely, a tracking set of a given graph G and a set of source-destination pairs of vertices is a subset T of vertices of G such that the vertices in T traversed by any source-destination shortest path P uniquely identify P. The minimum tracking set problem has been introduced in Banik et al., CIAC (2017) [1] for the case of a single source-destination pair. There, the authors show that the problem is APX-hard and that it can be 2-approximated for the class of planar graphs, even though no hardness result is known for this case. In this paper we focus on the case of multiple source-destination pairs and we present the first O ˜ (n) -approximation algorithm for general graphs. Moreover, we prove that the problem remains NP-hard even for cubic planar graphs and all pairs S × D , where S and D are the sets of sources and destinations, respectively. Finally, for the case of a single source-destination pair, we design an (exact) FPT algorithm w.r.t. the maximum number of vertices at the same distance from the source. [ABSTRACT FROM AUTHOR]

In this paper we consider two problems concerning string factorisation. Specifically given a string w and an integer k find a factorisation of w where each factor has length bounded by k and has the minimum (the F-Min-D problem) or the maximum (the F-Max-D problem) number of different factors. The F-Min-D has been proved to be NP-hard even if k = 2 in [9] and for this case we provide a 3/2-approximation algorithm. The F-Max-D problem, up to our knowledge has not been considered in the literature. We show that this problem is NP-hard for any k ≥ 3. In view of this we propose a 2-approximation algorithm (for any k) and an FPT algorithm w.r.t. parameter max ⁡ { k , | Σ | }. [ABSTRACT FROM AUTHOR]

The problem of constrained clustering has attracted significant attention in the past decades. In this paper, we study the balanced k -center, k -median, and k -means clustering problems where the size of each cluster is constrained by the given lower and upper bounds. The problems are motivated by the applications in processing large-scale data in high dimension. Existing methods often need to compute complicated matchings (or min cost flows) to satisfy the balance constraint, and thus suffer from high complexities especially in high dimension. We develop an effective framework for the three balanced clustering problems to address this issue, and our method is based on a novel spatial partition idea in geometry. For the balanced k -center clustering, we provide a 4-approximation algorithm that improves the existing approximation factors; for the balanced k -median and k -means clusterings, our algorithms yield constant and (1 + ϵ) -approximation factors with any ϵ > 0. More importantly, our algorithms achieve linear or nearly linear running times when k is a constant, and significantly improve the existing ones. Our results can be easily extended to metric balanced clusterings and the running times are sub-linear in terms of the complexity of n -point metric. [ABSTRACT FROM AUTHOR]

We consider the aggregation problem in radio networks: find a spanning tree in a given graph and a conflict-free schedule of the edges so as to minimize the latency of the computation. While a large body of literature exists on this and related problems, we give the first approximation results in graphs that are not induced by unit ranges in the plane. We give a polynomial-time O ˜ (d n) -approximation algorithm, where d is the average degree and n the number of vertices in the graph, and show that the problem is Ω (n 1 − ϵ) -hard (and Ω ((d n) 1 / 2 − ϵ) -hard) to approximate even on bipartite graphs, for any ϵ > 0 , rendering our algorithm essentially optimal. We also obtain a O (log ⁡ n) -approximation in interval graphs. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of maximizing a non-monotone and non-negative DR-submodular function on a bounded integer lattice [ B → ] = { (x 1 , ... , x n) ∈ Z + n : 0 ≤ x k ≤ B k , ∀ 1 ≤ k ≤ n } without any constraint, where B → = (B 1 , ... , B n) ∈ Z + n. We design an algorithm for the problem and measure its performance by its approximation ratio and the number of value oracle queries it needs, where the latter one is the dominating term in the running time of an algorithm. It has been showed that, for the problem considered, any algorithm achieving an approximation ratio greater than 1 2 requires an exponential number of value oracle queries. In the literature there are two algorithms that reach 1 2 approximation guarantee. The first algorithm needs O (n | | B | | ∞) oracle queries. The second one reduces its number of oracle queries to O (n max ⁡ { 1 , log ⁡ | | B → | | ∞ }) but it needs large storage. In this paper we present a randomized approximation algorithm that has an approximation guarantee of 1 2 , calls O (n max ⁡ { 1 , log ⁡ | | B → | | ∞ }) oracle queries and does not need large storage, improving the results of the literature. [ABSTRACT FROM AUTHOR]

We consider the following basic scheduling problem in wireless networks: partition a given set of unit demand communication links into the minimum number of feasible subsets. A subset is feasible if all communications can be done simultaneously, subject to mutual interference. We use the so-called physical model to formulate feasibility. We consider the two families of approximation algorithms that are known to guarantee O (log ⁡ n) approximation for the scheduling problem, where n is the number of links. We present network constructions showing that the approximation ratios of those algorithms are no better than logarithmic, both in n and in Δ, where Δ is a geometric parameter – the ratio of the maximum and minimum link lengths. [ABSTRACT FROM AUTHOR]

Given an edge-weighted undirected graph G = (V , E , w) and a subset T ⊆ V of p terminals, a k-Steiner forest spanning all the terminals in T includes k branches, where every branch is a Steiner tree. The diameter of a k -Steiner forest is referred to as the maximum distance between two terminals of a branch. This paper studies the minimum diameter k-Steiner forest problem (MD k SFP) and establishes the relationship between MD k SFP and the absolute k-Steiner center problem (A k SCP). We first obtain a 2-factor dual approximation algorithm for A k SCP, and then achieve a 2-approximation algorithm for MD k SFP based on the 2-approximation to A k SCP. Furthermore, we develop an improved 2 ρ -approximation algorithm for MD k SFP, where ρ < 1 in general, by perturbing the sites of facilities and re-clustering the terminals. [ABSTRACT FROM AUTHOR]

• NP-hardness proof for the partial assignment problem. • A 1 / m -approximation for the partial assignment problem with general value functions. • A (1 − 1 / e) -approximation for the partial assignment problem with sub- modular value functions. In the partial assignment problem, a seller has an item set M = { i 1 , i 2 , ... , i m } , the amount of each item is exactly one. There are n buyers N = { b 1 , b 2 ,... , b n } , each buyer b p has a preferred bundle B p ⊆ M and a value function f p (⋅). Assume that each item should be sold integrally and thus can be only assigned to at most one buyer. In previous works, buyers are often considered to be single-minded, i.e., a buyer can be either assigned the whole preferred bundle, or nothing. In this paper, we consider a more generalized and realistic model where the buyer can be partially satisfied, i.e., buyer b p can have some positive value if the seller assigns a subset of b p 's preferred bundle. However, there might be exponential number of subsets, to tackle this situation, a value oracle is implemented. We can get the value f p (S p) for buyer b p and S p ⊆ B p by querying the value oracle. The objective is to assign items to buyers such that the total values are maximized, i.e., max ⁡ ∑ p = 1 n f p (S p). We first show that in this model, maximizing the total values is NP-hard. We then propose provably efficient approximation algorithms for general and submodular value functions respectively. If the value function satisfies non-negative, monotone and normalized, an 1 / m -approximation algorithm can be achieved. If the value function is submodular, the total values can be approximated within a factor of (1 − 1 / e). [ABSTRACT FROM AUTHOR]

• A (k − 1)-approximation for the minimum weight connected- k -subgraph cover for a graph with girth > 2 k / 3 when k > 4. • This improves a previous result by relaxing the girth constraint from at least k to greater than 2 k / 3. • It improves previous ratio O (log ⁡ k) for the cardinality version when k < 45. For a given graph G , the minimum weight connected- k -subgraph cover problem (MinWC k SC) is to find a minimum weight vertex subset C of G such that each connected subgraph of G on k vertices contains at least one vertex of C. Previously, Zhang et al. [37] presented a (k − 1) -approximation algorithm for MinWC k SC under the assumption that the girth of G , which is the length of a shortest cycle of G , is at least k. In this paper, we improve this result by showing that (k − 1) -approximation can be achieved when the girth requirement is relaxed from k to 2 k / 3. [ABSTRACT FROM AUTHOR]

In this paper, we study the minimum (connected) k -bounded-degree node deletion problem (Min(C) k BDND). For a connected graph G , a constant k and a weight function w : V → R + , a vertex set C ⊆ V (G) is a k BDND-set if the maximum degree of graph G − C is at most k. If furthermore, the subgraph of G induced by C is connected, then C is a C k BDND-set. The goal of MinW k BDND (resp. MinWC k BDND) is to find a k BDND-set (resp. C k BDND-set) with the minimum weight. In this paper, we focus on their cardinality versions with w (v) ≡ 1 , v ∈ V , which are denoted as Min k BDND and MinC k BDND. This paper presents a (1 + ε) and a 3.76-approximation algorithm for Min k BDND and MinC k BDND on unit disk graphs, respectively, where 0 < ε < 1 is an arbitrary constant. [ABSTRACT FROM AUTHOR]

• We present a deterministic approximation algorithm for a #P-hard problem. • Our algorithm is a fully polynomial time approximation scheme (FPTAS). • To this end, the intersection volume of two cross-polytopes is also considered. • We propose an FPTAS also for the intersection volume of cross-polytopes. • We prove that computing the intersection volume is, surprisingly, still #P-hard. Given an n -dimensional convex body by a membership oracle in general, it is known that any polynomial-time deterministic algorithm cannot approximate its volume within ratio (n / log ⁡ n) n. There is a substantial progress on randomized approximation such as Markov chain Monte Carlo for a high-dimensional volume, and for many #P-hard problems, while only a few #P-hard problems are known to yield deterministic approximation. Motivated by the problem of deterministically approximating the volume of a V -polytope, that is a polytope with a small number of vertices and (possibly) exponentially many facets, this paper investigates the problem of computing the volume of a "knapsack dual polytope," which is known to be #P-hard due to Khachiyan (1989) [16]. We reduce an approximate volume of a knapsack dual polytope to that of the intersection of two cross-polytopes in a short distance, and give FPTASs for those volume computations. Interestingly, computing the volume of the intersection of two cross-polytopes (i.e., L 1 -balls) is #P-hard, unlike the cases of L ∞ -balls or L 2 -balls. [ABSTRACT FROM AUTHOR]

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MaxCut) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least 1 2 in expectation. When the graph is d -regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MaxCut in regular graphs. We first prove that if G is d -regular, with d even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of 1 d for d -regular graphs when d is odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio 1 d + ϵ (with ϵ > 0) can run in a constant number of rounds. We also prove results of a similar flavor for the MaxDiCut problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut. [ABSTRACT FROM AUTHOR]

A mixed domination of a graph G = (V , E) is a mixed set D of vertices and edges such that for every edge or vertex, if it is not in D , then it is adjacent or incident to at least one vertex or edge in D. The Mixed Domination problem is to check whether there is a mixed domination of size at most k in a graph. Mixed domination is a mixture concept of vertex domination and edge domination, and the mixed domination problem has been studied from the view of approximation algorithms, parameterized algorithms, and so on. In this paper, we give a branch-and-search algorithm with running time bound of O ⁎ (4.172 k) , which improves the previous bound of O ⁎ (7.465 k). For kernelization, it is known that the problem parameterized by k in general graphs is unlikely to have a polynomial kernel. We show the problem in planar graphs allows linear kernel by giving a kernel of 11 k − 16 vertices. [ABSTRACT FROM AUTHOR]