Search

Given a graph G = (V , E) , an L (2 , 1) -labeling of the graph is an assignment ℓ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u , v) , | ℓ (u) − ℓ (v) | ≥ 2 if u and v are adjacent, and ℓ (u) ≠ ℓ (v) if u and v are at distance 2. The L (2 , 1) -labeling problem is to minimize the range of ℓ (i.e., max u ∈ V (ℓ (u)) − min u ∈ V (ℓ (u)) + 1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L (2 , 1) -labeling of unit disk graphs. • An 8-approximation algorithm of L(2,1)-labeling for unit disk graphs with geometric representations is presented. • The previously known bound is 10.67. • The presented algorithm gives a simple periodic labeling based on a new way of partitioning the plane into squares. [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]

In this work, we study a range of constrained versions of the k-supplier and k-center problems. In the classical (unconstrained) k -supplier problem, we are given a set of clients C in a metric space X , with distance function d (. ,.). We are also given a set of feasible facility locations L ⊆ X. The goal is to open a set F of k facilities in L to minimize the maximum distance of any client to the closest open facility, i.e., minimize, cost (F , C) ≡ max j ∈ C ⁡ { d (F , j) } , where d (F , j) is the distance of client j to the closest facility in F. The k -center problem is a special case of the k -supplier problem where L = C. We study various constrained versions of the k -supplier problem such as: capacitated , fault-tolerant , ℓ -diversity, etc. These problems fall under a broad framework of constrained clustering. A unified framework for constrained clustering was proposed by Ding and Xu [Algorithmica 2020] in the context of the k -median and k -means objectives. We extend this framework to the k -supplier and k -center objectives in this work. This unified framework allows us to obtain results simultaneously for the following constrained versions of the k -supplier problem: r-gather, r-capacity, balanced, chromatic, fault-tolerant, strongly private, ℓ-diversity, and fair k-supplier problems, with and without outliers. We design Fixed-Parameter Tractable (FPT) algorithms for these problems. FPT algorithms have polynomial running time if the parameter under consideration is a constant. This may be relevant even to a practitioner since the parameter k is a small number in many real clustering scenarios. We obtain the following results: • We give 3 and 2 approximation algorithms for the constrained k -supplier and k -center problems, respectively, with FPT running time k O (k) ⋅ n O (1) , where n = | C ∪ L |. Moreover, these approximation guarantees are tight; that is, for any constant ε > 0 , no algorithm can achieve (3 − ε) and (2 − ε) approximation guarantees for the constrained k -supplier and k -center problems in FPT time, assuming FPT ≠ W [ 2 ]. • We study the constrained clustering problem with outliers. Our algorithm gives 3 and 2 approximation guarantees for the constrained outlier k -supplier and k -center problems, respectively, with FPT running time (k + m) O (k) ⋅ n O (1) , where n = | C ∪ L | and m is the number of outliers. • Our techniques generalise for distance function d (. ,.) z. That is, for any positive real number z , if the cost of a client is defined by d (. ,.) z instead of d (. ,.) , then our algorithm gives 3 z and 2 z approximation guarantees for the constrained k -supplier and k -center problems, respectively. • We design 3 approximation algorithm for a wide range of constrained k -supplier problems with FPT running time f (k). p o l y (n). • We design 2 approximation algorithm for a range of constrained k -center problems with FPT running time f (k). p o l y (n). • We extend the algorithm to outlier setting with FPT running time f (k , m). p o l y (n) , where m = number of outliers. • We show matching lower bounds for the constrained k -supplier and k -center problems in the outlier and non-outlier settings. [ABSTRACT FROM AUTHOR]

We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. We prove that the symmetry gap is small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations. • Optimal line plans in an entirely symmetric city model are not symmetric by default. • Line planning on an idealized infrastructure model to represent generic cities. • Analytical examination of the deviation from the optimum by symmetry assumption. • While infinitely large in practice, the symmetry gap is provably small in practice. • Development of an approximation algorithm utilizing the symmetric structure. [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]

Given a graph G , we call a partition (V 1 , V 2 , ... , V k) of its vertex set an induced star partition of G if each set in the partition induces a star. In this paper, we consider the problem of finding an induced star partition of a graph of minimum size and its decision versions. This problem may be viewed as an amalgamation of the well-known dominating set and coloring problems. We obtain the following main results: (1) Deciding whether a graph can be partitioned into k induced stars is NP-complete for each fixed k ≥ 3 and has a polynomial time algorithm for each k ≤ 2. (2) It is NP-hard to approximate the minimum induced star partition size within n 1 2 − ϵ for all ϵ > 0. (3) The decision version of the induced star partition problem is NP-complete for subcubic bipartite planar graphs, line graphs (a subclass of K 1 , r -free graphs, r ≥ 3), K 1 , 5 -free split graphs and co-tripartite graphs. (4) The minimum induced star partition problem has an r 2 -approximation algorithm for K 1 , r -free graphs (r ≥ 2) and a 2-approximation algorithms for split graphs. We also identify some fixed parameter tractable and exact exponential time algorithms that follow from the literature. [ABSTRACT FROM AUTHOR]

• We introduce the minimum power cover problem with submodular and linear penalties. • We present a combinatorial primal-dual approximation algorithm for the minimum power cover problem with submodular penalties. • We present a polynomial time approximation scheme for the minimum power cover problem with linear penalties. In this paper, we introduce the minimum power cover problem with submodular and linear penalties. Suppose U is a set of users and S is a set of sensors in a d -dimensional space R d with d ≥ 2. Each sensor can adjust its power and the relationship between the power p (s) and the radius r (s) of the service area of sensor s satisfies p (s) = c ⋅ r (s) α , where c > 0 and α ≥ 1. Let p be the power assignment for each sensor and R be the set of users who are not covered by any sensor supported by p. The objective is to minimize the total power of p plus the rejected penalty of R. For a submodular penalty function that is normalized and nondecreasing, we present a combinatorial primal-dual (3 α + 1) -approximation algorithm. For the case in which the submodular penalty function is linear, we present a polynomial time approximation scheme based on a plane subdivision technique. [ABSTRACT FROM AUTHOR]

We investigate the recoverable robust single machine scheduling problem under interval uncertainty. In this setting, jobs have first-stage processing times p and second-stage processing times q and we aim to find a first-stage and second-stage schedule with a minimum combined sum of completion times, such that at least Δ jobs share the same position in both schedules. We provide positive complexity results for some important special cases of this problem, as well as derive a 2-approximation algorithm to the full problem. Computational experiments examine the performance of an exact mixed-integer programming formulation and the approximation algorithm, and demonstrate the strength of a proposed polynomial time greedy heuristic. [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 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]

The coordination among drones and ground vehicles for last-mile delivery has gained significant interest in recent years. In this paper, we study multiple drone delivery scheduling problem (MDSP) [1] for last-mile delivery, where we have a set of drones with an identical battery budget and a set of delivery locations; along with profit for delivery, cost, and delivery time intervals. The objective of the MDSP is to find conflict-free schedules for each drone such that the total profit gained is maximum subject to the battery constraint of the drones. This paper proposes an optimal pseudo-polynomial algorithm and a fully polynomial time approximation scheme (FPTAS) for the single drone delivery scheduling problem (SDSP). Also, we propose two approximation algorithms of factor 1 3 for the MDSP with some constraints on the number of drones. We formulate the problem for the heterogeneous case, where the drones have non-identical battery capacities, and propose a 1 6 ρ -approximation algorithm, where ρ is the ratio between the minimum and maximum battery capacity of the drones. • An optimal pseudo-polynomial algorithm and FPTAS for the single drone delivery scheduling problem is proposed. • Two approximation algorithms for the multiple drone delivery scheduling problem are proposed. • An approximation algorithm for the multiple heterogeneous drone delivery scheduling problem is proposed. • We analyzed the approximation factors of all the aforementioned proposed algorithms and time complexities. [ABSTRACT FROM AUTHOR]

We initiate the study of a generalization of the class cover problem [Cannon and Cowen [1] , Bereg et al. [2] ] the generalized class cover problem , where we are allowed to misclassify some points provided we pay an associated positive penalty for every misclassified point. Two versions: single coverage and multiple coverage , of the generalized class cover problem are investigated. We study five different variants of both versions of the generalized class cover problem with axis-parallel strips and axis-parallel half-strips extending to different directions in the plane, thus extending similar work by Bereg et al. (2012) [2] on the class cover problem. We prove that the multiple coverage version of the generalize class cover problem with axis-parallel strips are in P , whereas the single coverage version is NP -hard. A factor 2 approximation algorithm is provided for the later problem. The APX -hardness result is also shown for the single coverage version. For half-strips extending to exactly one direction, both the single and multiple coverage versions can be solved in polynomial time using dynamic programming. In the case of half-strips extending to two orthogonal directions, we prove the class cover problem is NP -hard followed by APX -hard. This gives improve hardness results compare to Bereg et al. (2012) [2] , where they proved the class cover problem with half-strips oriented in four different directions is NP -hard. These NP - and APX -hardness results can directly apply to both single and multiple versions. Finally, constant factor approximation algorithms are provided for half-strips extending to more than one direction. [ABSTRACT FROM AUTHOR]

In large-scale disasters, evacuation using public transport, such as buses, is always essential, especially with limitations on the time window and resources available. Unfortunately, a Bus Evacuation Problem (BEP) is NP-hard in nature. This means it is impossible to find an optimal evacuation plan within a reasonable time window. Therefore, it is efficacious and requisite to use an approximation algorithm such that a sub-optimal plan can be derived quickly in large-scale disasters. In the literature, an approximation algorithm for BEP has been presented. However, there is not only a lack of rigorous proof of the approximation ratio, but also the computation time of the approximation algorithm is influenced by the number of evacuees. In this work, firstly the approximation ratio is derived as 2 n b + 7 , where n b is the number of buses, which is fundamentally more precise than the existing work. Further, the approximation ratio can be reduced to n b + 6 through a new proof provided in this work. More importantly, a new approximation algorithm is proposed in this work, with an aggregated network flow model that can be quickly solved as a linear programming problem in polynomial time. The approximation ratio of the new algorithm is proven to be n b + 1 when there is a pile of buses, and the computation time is insensitive to the number of evacuees. Finally, 10 sets of random cases and a real-life disaster, the flooding in Xingguo, China in 2019 are studied to illustrate the efficiency and practical applicability of the proposed approximation algorithm. [ABSTRACT FROM AUTHOR]

Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph discovery is the densest subgraph problem, where given an edge-weighted undirected graph G = (V , E , w) , we are asked to find S ⊆ V that maximizes the density d (S) , i.e., half the weighted average degree of the induced subgraph G [ S ]. This problem can be solved exactly in polynomial time and well-approximately in almost linear time. However, a densest subgraph has a structural drawback, namely, the subgraph may not be robust to vertex/edge failure. Indeed, a densest subgraph may not be well-connected, which implies that the subgraph may be disconnected by removing only a few vertices/edges within it. In this paper, we provide an algorithmic framework to find a dense subgraph that is well-connected in terms of vertex/edge connectivity. Specifically, we introduce the following problems: given a graph G = (V , E , w) and a positive integer/real k , we are asked to find S ⊆ V that maximizes the density d (S) under the constraint that G [ S ] is k -vertex/edge-connected. For both problems, we propose polynomial-time (bicriteria and ordinary) approximation algorithms, using classic Mader's theorem in graph theory and its extensions. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph on n vertices, where d (v) denotes the degree of vertex v , and t (v) is a threshold associated with v. We consider a process in which initially a set S of vertices becomes active, and thereafter, in discrete time steps, every vertex v that has at least t (v) active neighbors becomes active as well. The set S is contagious if eventually all V becomes active. The target set selection problem TSS asks for the smallest contagious set. TSS is NP-hard and moreover, notoriously difficult to approximate. In the conservative special case of TSS, t (v) > 1 2 d (v) for every v ∈ V. In this special case, TSS can be approximated within a ratio of O (Δ) , where Δ = max v ∈ V [ d (v) ]. In this work we introduce a more general class of TSS instances that we refer to as conservative on average (CoA), that satisfy the condition ∑ v ∈ V t (v) > 1 2 ∑ v ∈ V d (v). We design approximation algorithms for some subclasses of CoA. For example, if t (v) ≥ 1 2 d (v) for every v ∈ V , we can find in polynomial time a contagious set of size O ̃ Δ ⋅ O P T 2 , where O P T is the size of a smallest contagious set in G. We also provide several hardness of approximation results. For example, assuming the unique games conjecture, we prove that TSS on CoA instances with Δ ≤ 3 cannot be approximated within any constant factor. We also present results concerning the fixed parameter tractability of CoA TSS instances. [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]

A directed hypergraph H = (V, A) is a finite set of vertices V and a set of hyper-arcs A , where each hyper-arc is an ordered pair of nonempty subsets of vertices. A flow hypergraph H = (V, A, s) is a triple, such that (V, A) is a directed hypergraph, s e V is a distinguished vertex such that s reaches every vertex of V. Reducible flow hypergraphs are a generalization of Hecht and Ullman's reducible flowgraphs. The feedback vertex set (fvs) decision problem has a directed hypergraph H and an integer k ≥ 0 as input and the question is whether there is V'⊆V, |V' |≤k such that H\V' is an acyclic directed hypergraph. It is known that fvs is polynomial time solvable for reducible flowgraphs. In this article we prove that fvs is NP-complete for reducible flow hypergraphs showing a reduction from 3-satisfiability problem with at most 3 occurrences per variable (3 sat3-). We exhibit a polynomial-time ∆-approximation for fvs in reducible flow hypergraphs, where ∆ is the maximum number of hyper-arcs adjacent to a vertex of H. [ABSTRACT FROM AUTHOR]

The input to a PPNC instance is integers n and p , and a non-negative real weighting of the edges of the clique K n on the vertex set {1,..., n }. We are asked to find a set of p disjoint cycles spanning {1,..., n } and subject to this such that the sum of the weights of the edges is minimized. We provide an efficient approximation algorithm for the metric version of this problem which has an approximation ratio of 4 if p ≤ n/5 and an approximation ratio of 51 for larger p. For p > n/5, our algorithm uses a subroutine which approximately solves the Mod 3 T -join With Slack problem. The input to an instance of Mod k T -join with Slack consists of integers n and B , a non-negative weighting of the edges of the clique K n , and a label l(v) from {0,1,..., k - 1} on each vertex of K n. We are asked to find the minimum weight spanning forest F from amongst those satisfying ∑ T∈F ((∑ v∈V(T) l(v)) mod k) ≤ B. If k = 2 and B = 0 this is the well-studied T -join problem which can be solved exactly in polynomial time. [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]

• A min number of edge rotations transforming a graph of order n into a k -degree-anonymous. • NP-hard for k = n / q , q ≥ 3. • Polynomial-time 2-approximable under some constraints. • Polynomial-time solvable when k = n and for trees when k = θ (n). The Min Anonymous-Edge-Rotation problem asks for an input graph G and a positive integer k to find a minimum number of edge rotations that transform G into a graph such that for each vertex there are at least k − 1 other vertices of the same degree (a k -degree-anonymous graph). In this paper, we prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k = n / q , where n is the order of a graph and q any positive integer, q ≥ 3. We argue that under some constrains on the number of edges in a graph and k , Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Furthermore, we show that the problem is solvable in polynomial time for any graph when k = n and for trees when k = θ (n). Additionally, we establish sufficient conditions for an input graph and k such that a solution for Min Anonymous-Edge-Rotation exists. [ABSTRACT FROM AUTHOR]

We consider the problem of collectively delivering a package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent starts from some vertex of the graph; it can move along the edges of the graph and can pick up the package from a vertex and drop it in another vertex during the course of its movement. However, each agent has limited energy budget allowing it to traverse a path of bounded length B ; thus, multiple agents need to collaborate to move the package to its destination. Given the positions of the agents in the graph and their energy budgets, the problem of finding a feasible movement schedule is called the Collaborative Delivery problem and has been studied before. One of the open questions from previous results is what happens when the delivery must follow a fixed path given in advance. Although this special constraint reduces the search space for feasible solutions, the problem remains NP hard, as the general version of the problem. We consider the optimization version of the problem that asks for the optimal energy budget B per agent which allows for a feasible delivery schedule along a fixed path, given the initial positions of the agents. We provide polynomial time approximation algorithms for both directed and undirected graphs, and establish hardness of approximation for the directed case. Note that the fixed path version of collaborative delivery requires completely different techniques since a single agent may be used multiple times, unlike the general version of collaborative delivery studied before. We show that restricting each agent to a single pickup allows better approximations for fixed path collaborative delivery compared to the original problem. Finally, we provide a polynomial time algorithm for determining a feasible delivery strategy, if any exists, for a given budget B when the number of available agents is bounded by a constant. [ABSTRACT FROM AUTHOR]

• The approximability and the computational complexity of the Maximum Happy Set problem (MaxHS) are studied. • A (2 Δ + 1) -approximation algorithm for MaxHS on graphs with maximum degree Δ is presented. • The approximation ratio is improved to Δ if the maximum degree Δ is a constant. • The polynomial-time solvability of MaxHS on block/interval graphs is proved. • The NP-hardness of MaxHS on bipartite/cubic graphs is proved. In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G = (V , E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S ; otherwise unhappy. Given an undirected graph G = (V , E) and an integer k , the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2 Δ + 1) -approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard. [ABSTRACT FROM AUTHOR]

We study the problem of decomposing a graph into stars so that the minimum size star in the decomposition is as large as possible. Problems of graph decomposition have been actively investigated since the 70's. The question we consider here also combines the structure of a facility location problem (choosing the centres of the stars) with a max–min fairness optimization criterion that has recently received attention in resource allocation problems, e.g., the Santa Claus problem. We focus on computational and algorithmic questions: We show that the problem is hard even in the case of planar graphs of maximum degree not larger than four, and already for decompositions into stars of size at least three. We are able to tightly characterize the boundaries between efficiently solvable instances and hard ones: we show that relaxing any of the conditions in our hardness result (minimum size of the stars or degree of the input graph) makes the problem polynomially solvable. Our complexity result implies also the APX hardness of the problem ruling out any approximation guarantee better than 2/3. We complement this inapproximability result with a 1/2-approximation algorithm. Finally, we give a polynomial time algorithm for trees. A nice property of our algorithms is that they can all be implemented to run in time linear in the size of the input graph. [ABSTRACT FROM AUTHOR]

We consider scheduling on identical and unrelated parallel machines with job assignment restrictions. These problems are NP-hard and they do not admit polynomial time approximation algorithms with approximation ratios smaller than 1.5 unless P=NP. However, if we impose limitations on the set of machines that can process a job, the problem sometimes becomes easier in the sense that algorithms with approximation ratios better than 1.5 exist. We introduce a graph framework based on the assignment restrictions and study the computational complexity of the scheduling problem with respect to structural properties of the resulting graphs, in particular, their tree- and cliquewidth. We identify cases that admit polynomial time approximation schemes or FPT algorithms generalizing and extending previous results in this area. [ABSTRACT FROM AUTHOR]

Line of Sight (LoS) networks provide a model of wireless communication which incorporates visibility constraints. Vertices of such networks can be embedded onto the cube { (x 1 , x 2 , ... , x d) : x i ∈ { 1 , ... , n } , 1 ≤ i ≤ d } so that two vertices are adjacent if and only if their images lay on a line parallel to one of the cube edges and their distance is less than a given range parameter ω. In this paper we study large independent sets in LoS networks. We prove that the computational problem of finding a maximum independent set can be solved optimally in polynomial time for one dimensional LoS networks. However, for d ≥ 2 , the (decision version of) the problem becomes NP-complete for any fixed ω ≥ 3. In addition, we show that the problem is APX-hard when ω = n for d ≥ 3. On the positive side, we show that LoS networks generalize chordal graphs. This implies that there exists a simple d -approximation algorithm for the maximum independent set problem in LoS networks. Finally, we describe a polynomial time approximation scheme for the maximum independent set problem in LoS networks for the case when ω is a constant and present an improved heuristic algorithm for the problem in the case ω = n. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling jobs with sizes, release times and delivery times on identical parallel batch machines. All machines have the same capacity. Each machine can simultaneously process several jobs as a batch as long as the total size of these jobs does not exceed the capacity. The release time, processing time and delivery time of a batch are defined to be the latest release time, longest processing time and largest delivery time of all the jobs in the batch, respectively. The objective is to minimize the maximum delivery completion time, i.e., the time by which all jobs are delivered. For this strongly NP-hard problem, there does not exist any polynomial time algorithm with approximation ratio better than 2 unless P=NP, even if all jobs have equal processing times and all release times and delivery times are zero. We present an algorithm with approximation ratio arbitrarily close to 2. • Study parallel batch scheduling of minimizing maximum delivery completion time. • Jobs have non-identical sizes, release times and delivery times. • Present an algorithm with approximation ratio arbitrarily close to 2. [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]

For a graph G and a non-negative integral weight function w on the vertex set of G , a set S of vertices of G is w -safe if w (C) ≥ w (D) for every component C of the subgraph of G induced by S and every component D of the subgraph of G induced by the complement of S such that some vertex in C is adjacent to some vertex of D. The minimum weight w (S) of a w -safe set S is the safe number s (G , w) of the weighted graph (G , w) , and the minimum weight of a w -safe set that induces a connected subgraph of G is its connected safe number c s (G , w). Bapat et al. showed that computing c s (G , w) is NP-hard even when G is a star. For a given weighted tree (T , w) , they described a polynomial time 2-approximation algorithm for c s (T , w) as well as a polynomial time 4-approximation algorithm for s (T , w). Addressing a problem they posed, we present a PTAS for the connected safe number of a weighted tree. Our PTAS partly relies on an exact pseudopolynomial time algorithm, which also allows to derive an asymptotic FPTAS for restricted instances. Finally, we extend a bound due to Fujita et al. from trees to block graphs. [ABSTRACT FROM AUTHOR]

In this paper we study some generalizations of the parking permit problem (Meyerson, FOCS'05), in which we are given a demand r t ∈ { 0 , 1 } for instant of time t = 0 , ... , T − 1 , along with K permit types with lengths of time δ 1 , ... , δ K and sub-additive costs. A permit is a pair (k , t ˆ) ∈ K × Z + , and it covers interval t ˆ , t ˆ + δ k). We wish to find a minimum-cost set of permits that covers every t with r t = 1. Meyerson gave deterministic O (K) -competitive and randomized O (lg K) -competitive online algorithms for this problem, as well as matching lower bounds. The first variant we propose is the multi parking permit problem, in which an arbitrary demand is given at each instant ( r t ∈ Z + ) and we may buy multiple permits to serve it. We prove that the offline version of this problem can be solved in polynomial time, and we show how to reduce it to the parking permit problem, while losing a constant cost factor. This approximation-preserving reduction yields a deterministic O (K) -competitive online algorithm and a randomized O (lg K) -competitive online algorithm. For a leasing variant of the Steiner network problem, these results imply a O (lg n) -approximation algorithm and a O (lg K lg | V |) -competitive online algorithm, where n is the number of requests and | V | is the size of the input metric. The second variant we propose is the group parking permit problem, in which we also have an arbitrary demand for each instant, and each permit of type k can be either a single permit, costing γ k and covering one demand per instant of time, or a group permit, which costs M ⋅ γ k for some constant M ≥ 1 and covers an arbitrary number of demands in the interval covered by this permit. (I.e., group permits have infinite capacity.) For this version of the problem, we give an 8-approximation algorithm and a deterministic O (K) -competitive online algorithm. The first result yields an improvement on the previous best approximation algorithm for the leasing version of the rent-or-buy problem. Finally, we study the 2D parking permit problem, proposed by Hu, Ludwig, Richa and Schmid (2015), in which a permit type is defined by a length of time and an integer capacity. They presented a constant approximation algorithm and a deterministic O (K) -competitive online algorithm for a hierarchical version of the problem, but those algorithms have pseudo-polynomial running time. We show how to turn their algorithms into polynomial time algorithms. Moreover, these results yield approximation and competitive online algorithms for a hierarchical leasing version of the buy-at-bulk network design problem. We also show that their original pseudo-polynomial offline algorithm works for a more general version of the 2D parking permit problem, which we prove to be NP-hard. [ABSTRACT FROM AUTHOR]

Let there be a set M of m parallel machines and a set J of n jobs, where each job j takes p i , j time units on machine M i. In makespan minimization the goal is to schedule each job non-preemptively on a machine such that the length of the schedule, the makespan, is minimum. We investigate a generalization of makespan minimization on unrelated parallel machines (R | | C m a x) where J is partitioned into b bags B = (B 1 , ... , B b) , and no two jobs belonging to the same bag can be scheduled on the same machine. First we present a simple b -approximation algorithm for R | | C m a x with bags (R | b a g | C m a x). We also give a polynomial-time approximation scheme (PTAS) for R | b a g | C m a x with machine types where both the number of machine types and bags are constant; two machines M i and M i ′ have the same machine type if p i , j = p i ′ , j for all j ∈ J. This result infers the existence of a PTAS for uniform parallel machines (Q | b a g | C m a x) when the number of machine speeds and number of bags are both constant. Then, we present a b / 2 -approximation algorithm for the graph balancing problem with b ≥ 2 bags; the approximation ratio is tight for b = 3 , unless P = NP , and this algorithm solves the graph balancing problem with b = 2 bags in polynomial time. In addition, we present a polynomial-time algorithm for the restricted assignment problem on uniform parallel machines with bags when all the jobs have unit length. To complement our algorithmic results, we show that when the jobs have lengths 1 or 2 it is NP -hard to approximate the optimum makespan within a factor smaller than 3/2 for both the restricted assignment and graph balancing problems with b = 2 bags and b = 3 bags, respectively. We also prove that Q | b a g | C m a x with b = 2 bags is strongly NP -hard. [ABSTRACT FROM AUTHOR]

• Polynomial time algorithm for the discrete speed model and fixed order of jobs. • Polynomial time algorithm for the sense-and-aggregate model. • Heuristic for the continuous speed model for arbitrary order of jobs. We study the following flow shop scheduling problem on two processors. We are given n jobs with a common deadline D , where each job j has workload p i , j on processor i and a set of processors which can vary their speed dynamically. Job j can be executed on the second processor if the execution of job j is completed on the first processor. Our objective is to find a feasible schedule such that all jobs are completed by the common deadline D with minimized energy consumption. For this model, we present a linear program for the discrete speed case, where the processor can only run at specific speeds in S = { s 1 , s 2 , ⋯ , s q } and the job execution order is fixed. We also provide a m α − 1 -approximation algorithm for the arbitrary order case and for continuous speed model where m is the number of processors and α is a parameter of the processor. We then introduce a new variant of flow shop scheduling problem called sense-and-aggregate model motivated by data aggregation in wireless sensor networks where the base station needs to receive data from sensors and then compute a single aggregate result. In this model, the first processor will receive unit size data from sensors and the second processor is responsible for calculating the aggregate result. The second processor can decide when to aggregate and the workload that needs to be done to aggregate x data will be f (x) and another unit size data will be generated as the result of the partial aggregation which will then be used in the next round aggregation. Our objective is to find a schedule such that all data are received and aggregated by the deadline with minimum energy consumption. We present an O (n 5) dynamic programming algorithm when f (x) = x and a greedy algorithm when f (x) = x − 1. Finally, we investigate the performance of the flowshop problem when the order of jobs is fixed by comparing it to the approximation algorithm with an arbitrary order. We show experimentally that the approximation ratio is close to 1 when there are few machines and when there are more jobs. [ABSTRACT FROM AUTHOR]

Given a set B of d -dimensional boxes (i.e., axis-aligned hyperrectangles), a minimum coverage kernel is a subset of B of minimum size covering the same region as B. Computing it is NP -hard, but as for many similar NP -hard problems (e.g., Box Cover , and Orthogonal Polygon Covering), the problem becomes solvable in polynomial time under restrictions on B. We show that computing minimum coverage kernels remains NP -hard even when restricting the graph induced by the input to a highly constrained class of graphs. Alternatively, we present two polynomial-time approximation algorithms for this problem: one deterministic with an approximation ratio within O (log ⁡ n) , and one randomized with an improved approximation ratio within O (lg ⁡ OPT) (with high probability). [ABSTRACT FROM AUTHOR]

Given a set D = { d 1 , ... , d n } of imprecise points modeled as disks, the minimum diameter problem is to locate a set P = { p 1 , ... , p n } of fixed points, where p i ∈ d i , such that the furthest distance between any pair of points in P is as small as possible. This introduces a tight lower bound on the size of the diameter of any instance P. In this paper, we present a fully polynomial time approximation scheme (FPTAS) for computing the minimum diameter of a set of disjoint disks that runs in O (n 2 ϵ − 1) time. Then we relax the disjointness assumption and we show that adjusting the presented FPTAS will cost O (n 2 ϵ − 2) time. We also show that our results can be generalized in R d when the dimension d is an arbitrary fixed constant. [ABSTRACT FROM AUTHOR]

An instance of the Connected Maximum Cut problem consists of an undirected graph G = (V , E) and the goal is to find a subset of vertices S ⊆ V that maximizes the number of edges in the cut δ (S) such that the induced graph G [ S ] is connected. We present the first non-trivial Ω (1 log ⁡ n) approximation algorithm for the Connected Maximum Cut problem in general graphs using novel techniques. We then extend our algorithm to edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in contrast to the classical Max-Cut problem that can be solved in polynomial time on planar graphs, we show that the Connected Maximum Cut problem remains NP-hard on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the Connected Maximum Cut problem on planar graphs and more generally on bounded genus graphs. [ABSTRACT FROM AUTHOR]

An l-pseudoforest is a graph each of whose connected components is at most l edges removal being a tree. The l-Pseudoforest Deletion problem is to delete a vertex set P of minimum weight from a given vertex-weighted graph G = (V , E) such that the remaining graph G [ V ∖ P ] is an l -pseudoforest. The Feedback Vertex Set problem is a special case of the l -Pseudoforest Deletion problem with l = 0. In this paper, we present a polynomial time 4 l -approximation algorithm for the l -Pseudoforest Deletion problem with l ≥ 1 by using the local ratio technique. When l = 1 , we get a better approximation ratio 2 for the problem by further analyzing the local ratio, which matches the current best constant approximation factor for the Feedback Vertex Set problem. • This paper studies a generalization of the FVS problem, called the l -pseudoforest deletion problem. The FVS problem is its special case with l = 0. • By extracting a sequence of subgraphs with some structure and special weight, and splitting a graph into decomposition subgraphs. This paper presents a polynomial time approximation algorithm for the l -Pseudoforest Deletion problem. • We obtain the approximation ratio 4 l of the algorithm when l > 0 by analyzing the properties and local ratio of the decomposition subgraphs. • By further analyzing local ratio of the decomposition subgraphs, we obtain an interesting approximation ratio 2 for the problem with l = 1 , which matches the current best constant approximation factor for the FVS problem. [ABSTRACT FROM AUTHOR]

A mixed shop is a manufacturing infrastructure designed to process a mixture of a set of flow-shop jobs and a set of open-shop jobs. Mixed shops are in general much more complex to schedule than flow-shops and open-shops, and have been studied since the 1980's. We consider the three machine proportionate mixed shop problem denoted as M 3 | p r p t | C max , in which by "proportionate" each job has equal processing times on all three machines. Koulamas and Kyparisis (2015) [6] showed that the problem is solvable in polynomial time in some very special cases; for the non-solvable case, they proposed a 5/3-approximation algorithm. In this paper, we first present an improved 4/3-approximation algorithm and show that this ratio of 4/3 is asymptotically tight; when the largest job is a flow-shop job, we then present a fully polynomial-time approximation scheme (FPTAS). On the negative side, while the F 3 | p r p t | C max problem is polynomial-time solvable, we show an interesting hardness result that adding one open-shop job to the job set makes the problem NP-hard if this open-shop job is larger than any flow-shop job. We are able to design an FPTAS for this special case too. [ABSTRACT FROM AUTHOR]

• Models the scheduling problem as an optimization problem with congruence constraints. • Proposes a new graph representation of the problem. • Provides optimal inapproximability results for the optimization problem. • Exposes the close bounds that relate this problem with the MAX DICUT problem. • Customizes and applies approximation algorithms for MAX DICUT in real case studies. This paper aims to synchronize timetables in a transit network so as to minimize the total passenger transfer waiting time. Assuming a fixed headway for each line, we first formulate the problem as an optimization problem with congruence constraints. We show that the problem is NP-hard, and investigate several special cases of the problem that are solvable in polynomial time. Furthermore, we show that the local search for the general problem is equivalent to the well-studied maximum directed cut problem. As such, we use an approximation algorithm for the maximum directed cut problem to solve the timetable synchronization problem. We assess the quality of the algorithm on a real-world case study, and show that our algorithm significantly outperforms the state-of-the-art in the literature. Lastly, we relax the fixed headway assumption, and propose an efficient recursive quasi-linear time algorithm to minimize the total transfer waiting time in this general setting. [ABSTRACT FROM AUTHOR]

Certain answers are a widely accepted semantics of query answering over incomplete databases. As their computation is a coNP-hard problem, recent research has focused on developing (polynomial time) evaluation algorithms with correctness guarantees , that is, techniques computing a sound but possibly incomplete set of certain answers. The aim is to make the computation of certain answers feasible in practice, settling for under-approximations. In this paper, we present novel evaluation algorithms with correctness guarantees, which provide better approximations than current techniques, while retaining polynomial time data complexity. The central tools of our approach are conditional tables and the conditional evaluation of queries. We propose different strategies to evaluate conditions, leading to different approximation algorithms—more accurate evaluation strategies have higher running times, but they pay off with more certain answers being returned. Thus, our approach offers a suite of approximation algorithms enabling users to choose the technique that best meets their needs in terms of balance between efficiency and quality of the results. • Algorithms to compute sound sets of certain query answers over incomplete databases. • Approximation algorithms trading-off evaluation time vs. quality of the approximation. • Suite of algorithms enabling users to choose the method that best meets their needs. [ABSTRACT FROM AUTHOR]

We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of n points in R d each of which has an existence probability, a SCH refers to the convex hull of a realization of the dataset, i.e., a random sample including each point with its existence probability. We are interested in computing certain expected statistics of a SCH, including diameter, width, and combinatorial complexity. For diameter, we establish a deterministic 1.633-approximation algorithm with a time complexity polynomial in both n and d. For width, two approximation algorithms are provided: a deterministic O (1) -approximation running in O (n d + 1 log ⁡ n) time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact O (n d) -time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest. [ABSTRACT FROM AUTHOR]

We study the problem of motion planning for a collection of n labeled unit disc robots in a polygonal environment. We assume that the robots have revolving areas around their start and final positions: that each start and each final is contained in a radius 2 disc lying in the free space, not necessarily concentric with the start or final position, which is free from other start or final positions. This assumption allows a weakly-monotone motion plan, in which robots move according to an ordering as follows: during the turn of a robot R in the ordering, it moves fully from its start to final position, while other robots do not leave their revolving areas. As R passes through a revolving area, a robot R ′ that is inside this area may move within the revolving area to avoid a collision. Notwithstanding the existence of a motion plan, we show that minimizing the total traveled distance in this setting, specifically even when the motion plan is restricted to be weakly-monotone, is APX-hard, ruling out any polynomial-time (1 + ε) -approximation algorithm. On the positive side, we present the first constant-factor approximation algorithm for computing a feasible weakly-monotone motion plan. The total distance traveled by the robots is within an O (1) factor of that of the optimal motion plan, which need not be weakly monotone. Our algorithm extends to an online setting in which the polygonal environment is fixed but the initial and final positions of robots are specified in an online manner. Finally, we observe that the overhead in the overall cost that we add while editing the paths to avoid robot-robot collision can vary significantly depending on the ordering we chose. Finding the best ordering in this respect is known to be NP-hard, and we provide a polynomial time O (log ⁡ n log ⁡ log ⁡ n) -approximation algorithm for this problem. [ABSTRACT FROM AUTHOR]

We consider the 0–1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed afterwards. The contribution of a packed item in each time period depends on its profit as well as on a time factor which reflects the importance of the period in the objective function. The problem calls for maximizing the weighted sum of the profits over the whole time horizon. In this work, we provide approximation results for IKP and its restricted variants. In some results, we rely on Linear Programming (LP) to derive approximation bounds and show how the proposed LP-based analysis can be seen as a valid alternative to more formal proof systems. We first manage to prove the tightness of some approximation ratios of a general purpose algorithm currently available in the literature and originally applied to a time-invariant version of the problem. We also devise a Polynomial Time Approximation Scheme (PTAS) when the input value indicating the number of periods is considered as a constant. Then, we add the mild and natural assumption that each item can be packed in the first time period. For this variant, we discuss different approximation algorithms suited for any number of time periods and for the special case with two periods. [ABSTRACT FROM AUTHOR]

Highlights • An approaximation algorithm for the case with bounded number of divisible resources. • A 6 + 2 10 + ε -approximation algorithm for the case where u ij ∈ {0, u j }. • A polynomial-time approximation algorithm for the general case. Abstract Resource allocation is a classic problem in economics and computer science. The application scenarios of resource allocation include inheritance settlements, computation resource sharing and so on. This paper focuses on the max-min fair allocation of resources in which m resources need to be allocated to n agents while maximizing the minimum utility of any agent. When money transfer is not allowed, the existing work on max-min fair allocation only focuses on the fair allocation of indivisible resources. However, in real applications, the allocated resource set may simultaneously include indivisible resources and divisible resources, e.g., the allocated resources in distributed systems include the indivisible CPU resources, the divisible storage resource and the divisible bandwidth resource. The combination of indivisible resources and divisible resources creates a new challenge and requires us to consider how to coordinate the allocations of indivisible resources and divisible resources in the allocation process. Therefore, we investigate the combined max-min fair allocation problem in which the allocated resource set consists of both indivisible resources and divisible resources. We present a 6+2 10 + ε (ε > 0)-factor approximation algorithm for the restricted case where u ij ∈ {0, u j } (i.e., the utility of a resource j is either 0 or u j for each agent i) and the agent valuations for the divisible resources are in proximity to each other. Moreover, we propose an approximation algorithm for the general case based on the augmented flow idea. Experiments conducted on real data show that the average performance of the proposed approximation algorithm is better than 80% of the performance of the optimal algorithm, which requires exponential time in the worst case unless P = NP. To the best of our knowledge, the proposed algorithm is the first approximation algorithm for the general case of the combined max-min fair allocation problem when money transfer is not allowed. The proposed algorithm can be adopted to design more efficient expert systems that apply to resource allocation in distributed systems, inheritance settlements and so on. The adoption of the proposed algorithm contributes to promoting the broader application of expert systems in the fair allocation of computation resources and social resources. The experimental results show that the proposed algorithm can perform well in real applications. [ABSTRACT FROM AUTHOR]

Abstract This work considers the optimum weighted source–destination communication spanning tree problem (WSDOCT), which is an NP-hard special case of the optimum communication spanning tree problem (OCT). Given an undirected graph G = (V , E) with non-negative lengths ω (e) associated to the edges and non-negative routing weights σ (u) and ρ (u) respectively to sending and receiving communication of nodes u ∈ V , the objective is to find a spanning tree T of G , that minimizes: ∑ u , v ∈ V (σ (u) ρ (v) + ρ (u) σ (v)) d (T , u , v) , where d (H , x , y) is the minimum distance between nodes x and y in a graph H ⊆ G. We present a polynomial time approximation scheme for the metric case of the WSDOCT. This result improves the until now best existing approximation algorithm for this problem. Also, we give a 2-approximation for the problem which improves the time complexity required by our PTAS to achieve this approximation ratio. [ABSTRACT FROM AUTHOR]

In this work we study min max robust scheduling problems assuming that the processing times can take any value in the budgeted uncertainty set introduced by Bertsimas and Sim (2003, 2004). We consider problems on a single machine that minimize the (weighted and unweighted) sum of completion times and problems that minimize the makespan on parallel and unrelated machines. We provide approximation algorithms: constant factor, average non-constant factor, (fully or not) polynomial time approximation schemes. In addition, we prove that the robust version of minimizing the weighted completion time on a single machine is NP -hard in the strong sense. [ABSTRACT FROM AUTHOR]

Abstract In phylogenetics, the consensus problem consists in summarizing a set of phylogenetic trees that all classify the same set of species into a single tree. Several definitions of consensus exist in the literature; in this paper we focus on the Weighted Quartet Consensus problem, whose complexity status has remained open since it was posed in 2008. Here we show that the Weighted Quartet Consensus problem is NP-hard, and provide several results on the approximability of the problem. Namely, we show that Weighted Quartet Consensus admits a polynomial-time approximation scheme (PTAS) based on prior work of Jiang, Kearney and Li. The algorithm is unfortunately impractical, and so we also present an implementable 1/2-factor approximation algorithm. During the process, we propose a derandomization procedure of a previously known randomized 1/3-factor approximation, which guarantees that a tree that contains a third of any given multi-set of quartets can be found deterministically. We also investigate the fixed-parameter tractability of this problem. [ABSTRACT FROM AUTHOR]

Highlights • Periodic cyclic executives (CEs) can be synthesized by solving linear programs (LPs). • Preemptive CEs can be obtained by a polynomial-time algorithm. • Obtaining non-preemptive CEs takes worst-case exponential time. • Approximation algorithms for non-preemptive CEs appear efficient and effective. • Improved approximate solutions exist for some restricted special cases. Abstract In a cyclic executive, a series of pre-determined frames are executed in sequence; once the series is complete the sequence is repeated. Within each frame individual units of computation are executed, again in a pre-specified sequence. Although they suffer from a number of limitations, cyclic executives have the advantage of being fully deterministic, and may be implemented with very low runtime overhead; as a consequence of these advantages, run-time schedulers in highly safety-critical real-time systems have historically been implemented as cyclic executives. Industrial applications of the cyclic executive framework are currently primarily restricted to uniprocessor platforms; in this paper, we consider the implementation of cyclic executives upon multi-core platforms. We present a Linear Programming (LP) based formulation of the problem of constructing cyclic executives upon multiprocessors for a particular kind of recurrent real-time workload — collections of implicit-deadline periodic tasks. We describe techniques for solving the LP formulation under different kinds of restrictions in order to obtain preemptive and non-preemptive cyclic executives. Our algorithms for constructing preemptive cyclic executives have running time polynomial in the size of the cyclic executive. We present an exact algorithm for constructing non-preemptive cyclic executives that has worst-case running time exponential in the size of the cyclic executive; however, state-of-the-art LP solvers appear to often be able to construct fairly large cyclic executives in a reasonable amount of time. We also present an approximation algorithm for constructing non-preemptive cyclic executives that does run in polynomial time, and evaluate the effectiveness of this approximation algorithm both theoretically via the speedup factor metric, and experimentally via experiments on synthetically generated workloads. We additionally identify a particular restricted kind of workload that is quite commonly found in practice, for which non-preemptive cyclic executives can be constructed more efficiently than in the general case. [ABSTRACT FROM AUTHOR]

Abstract The maximin share guarantee is, in the context of allocating indivisible goods to a set of agents, a recent fairness criterion. A solution achieving a constant approximation of this guarantee always exists and can be computed in polynomial time. We extend the problem to the case where the goods collectively received by the agents satisfy a matroidal constraint. Polynomial approximation algorithms for this generalization are provided: a 1/2-approximation for any number of agents, a (1 − ε) -approximation for two agents, and a (8 / 9 − ε) -approximation for three agents. Apart from the extension to matroids, the (8 / 9 − ε) -approximation for three agents improves on a (7 / 8 − ε) -approximation by Amanatidis et al. (ICALP 2015). Some special cases are also presented and some extensions of the model are discussed. [ABSTRACT FROM AUTHOR]

Abstract A bounded-degree-1 set S in an undirected graph G = (V , E) is a vertex subset such that the maximum degree of G [ S ] is at most one. Given a graph G , the Maximum Bounded-Degree-1Set (Max 1-bds) problem is to find a bounded-degree-1 set S of maximum size in G.A notion related to bounded-degree sets is that of an s - plex used to define the cohesiveness of subgraphs in social networks. An s -plex S in a graph G = (V , E) is a vertex subset such that for each v ∈ S , deg G [ S ] (v) ≥ | S | − s. One can easily show that a graph G has a2-plex of size k iff the complement graph of G has a bounded-degree-1 set of size k. Both the Maximum 2-Plex problem and the Maximum Bounded-Degree-1 Set problem are NP-hard. We give a simple branch-and-reduce algorithm running in polynomial space and applying branching strategies with at most three branches for Max 1-bds. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time O ∗ (1. 461 3 n) which is faster than previous exact algorithms. Moreover, we show that the Max 1-bds problem cannot be approximated to a ratio greater than n ϵ − 1 in polynomial time for all ϵ > 0 unless P = NP. Some moderately exponential time approximation algorithms are given for Max 1-bds and its dual problem. [ABSTRACT FROM AUTHOR]

In this paper, we consider a variation of the classic dominating set problem - The Two Disjoint Connected Dominating Sets (DCDS) problem, which finds applications in many real domains including wireless sensor networks. In the DCDS problem, we are given a graph G = ( V , E ) and required to find a new edge set E ′ with minimum cardinality such that the resulting new graph after the adding of E ′ has a pair of disjoint connected dominating sets. This problem is very hard in general graphs, and we show that it is NP -hard even restricted to trees. We also present a polynomial time approximation algorithm for the DCDS problem for arbitrary trees with performance ratio 3 2 asymptotically. [ABSTRACT FROM AUTHOR]

In this paper, we study two classic optimization problems: minimum geometric dominating set and set cover. In the dominating-set problem, for a given set of objects in the plane as input, the objective is to choose a minimum number of input objects such that every input object is dominated by the chosen set of objects. Here, we say that one object is dominated by another if their intersection is nonempty. For the second problem, for a given set of points and objects in the plane, the objective is to choose a minimum number of objects to cover all the points. This is a particular version of the set-cover problem. Both problems have been well-studied, subject to various restrictions on the input objects. These problems are APX -hard for object sets consisting of axis-parallel rectangles, ellipses, α -fat objects of constant description complexity, and convex polygons. On the other hand, PTAS s (polynomial time approximation schemes) are known for object sets consisting of disks or unit squares. Surprisingly, a PTAS was unknown even for arbitrary squares. For both problems obtaining a PTAS remains open for a large class of objects. For the dominating-set problem, we prove that a popular local-search algorithm leads to a (1 + ε) approximation for a family of homothets of a convex object (which includes arbitrary squares, k -regular polygons, translated and scaled copies of a convex set, etc.) in n O (1 / ε 2) time. On the other hand, the same approach leads to a PTAS for the geometric covering problem when the objects are convex pseudodisks (which include disks, unit height rectangles, homothetic convex objects, etc.). Consequently, we obtain an easy-to-implement approximation algorithm for both problems for a large class of objects, significantly improving the best-known approximation guarantees. [ABSTRACT FROM AUTHOR]