Search

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G , a temporal graph is represented by assigning a set of integer time-labels to every edge e of G , indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching , taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching , we are looking for the largest possible number of time-labeled edges (simply time-edges) (e , t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ N is given. We prove strong computational hardness results for Maximum Temporal Matching , even for elementary cases, as well as fixed-parameter algorithms with respect to natural parameters and polynomial-time approximation algorithms. [ABSTRACT FROM AUTHOR]

The problem of deletion of vertices to a hereditary graph class is a well-studied problem in parameterized complexity. Recently, a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes and we determine whether k vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be fixed parameter tractable (FPT) when the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. This paper focuses on pairs of specific graph classes (Π 1 , Π 2) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. [ABSTRACT FROM AUTHOR]

We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP (constant factor approximations that invest more runtime with respect to a chosen parameter). The parameters we consider are upper bounded by the number of asymmetric distances , which yields algorithms to efficiently compute good approximations for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, with the size of a vertex cover for the subgraph induced by the edges with asymmetric distances as parameter. Our generalization of tree doubling gives a parameterized 3-approximation, where the parameter is the minimum number of asymmetric distances in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the parameters we consider are theoretically incomparable, we present experimental results showing that generalized tree doubling frequently outperforms generalized Christofides with respect to parameter size. [ABSTRACT FROM AUTHOR]

Trees with many leaves have applications for broadcasting a message to all recipients simultaneously. Internal nodes of a broadcasting tree require more expensive technology to forward the messages received. We address a problem that captures the main goal: finding spanning trees with few internal nodes in a given network. The Maximum Leaf Spanning Arborescence problem consists of, given a directed graph D , finding a spanning arborescence of D , if one exists, with the maximum number of leaves. This problem is NP-hard in general and MaxSNP-hard in the rooted directed acyclic graphs class. This paper explores a relationship between Maximum Leaf Spanning Arborescence in rooted directed acyclic graphs and maximum weight set packing. The latter problem is related to independent sets on particular classes of intersection graphs. Exploiting this relation, we derive a 7/5-approximation for Maximum Leaf Spanning Arborescence on rooted directed acyclic graphs, improving on the previous 3/2-approximation. [ABSTRACT FROM AUTHOR]

Network coding (NC), when combined with multipath routing, enables a linear programming (LP) formulation for a multi-source multicast with intra-session network coding (MISNC) problem. However, it is still hard to solve using conventional methods due to the enormous scale of variables or constraints. In this paper, we try to solve this problem in terms of throughput maximization from an algorithmic perspective. We propose a novel formulation based on the extreme flow decomposition technique, which facilitates the design and analysis of approximation and online algorithms. For the offline scenario, we develop a fully polynomial time approximation scheme (FPTAS) which can find a (1 + ω) -approximation solution for any specified ω > 0. For the online scenario, we develop an online primal-dual algorithm which proves O (1) -competitive and violates link capacities by a factor of O (log ⁡ m) , where m is the link number. The proposed algorithms share an elegant primal-dual form and thereby have inherent advantages of simplicity, efficiency, and scalability. To better understand the proposed approach, we devise delicate numerical examples on an extended butterfly network to validate the effects of algorithmic parameters and make an interesting comparison between the offline and online cases. We also perform large-scale simulations on real networks to validate the effectiveness of the proposed FPTAS and online algorithm. • Extreme flow decomposition technique for intra-session network coding. • Offline FPTAS with provable approximation ratio. • Online primal-dual algorithm with provable competitive ratio. • Large-scale experiments using public datasets. [ABSTRACT FROM AUTHOR]

We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the p -Edge-Connected and p -Vertex-Connected VC problem (where p ≥ 2 is a fixed integer). We obtain an 2 O (p k) n O (1) -time algorithm for p -Edge-Connected VC and an 2 O (k 2) n O (1) -time algorithm for p -Vertex-Connected VC. Thus, like Connected VC, both constrained VC problems are FPT. Furthermore, like Connected VC, neither problem admits a polynomial kernel unless NP ⊆ coNP/poly, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. Finally, we describe a 2 (p + 1) -approximation algorithm for the p -Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning p -vertex/edge-connected subgraphs of a p -vertex/edge-connected graph by Nishizeki and Poljak (1994) [30] and Nagamochi and Ibaraki (1992) [27]. [ABSTRACT FROM AUTHOR]

Scheduling independent tasks on a parallel platform is a widely-studied problem, in particular when the goal is to minimize the total execution time, or makespan (P | | C max problem in Graham's notations). Also, many applications do not consist of sequential tasks, but rather parallel tasks, either rigid, with a fixed degree of parallelism, or moldable, with a variable degree of parallelism (i.e., for which we can decide at the execution on how many processors they are executed). Furthermore, since the energy consumption of data centers is a growing concern, both from an environmental and economical point of view, minimizing the energy consumption of a schedule is a main challenge to be addressed. One can then decide, for each task, on how many processors it is executed, and at which speed the processors are operated, with the goal to minimize the total energy consumption. We further focus on co-schedules, where tasks are partitioned into shelves, and we prove that the problem of minimizing the energy consumption remains NP-complete when static energy is consumed during the whole duration of the application. We are however able to provide an optimal algorithm for the schedule within one shelf, i.e., for a set of tasks that start at the same time. Several approximation results are derived, both with discrete and continuous speed models, and extensive simulations are performed to show the performance of the proposed algorithms. • A model for a theoretical analysis of the energy consumption of a schedule for moldable and rigid tasks. • Most presented scheduling problems are NP-complete. • There exist approximation algorithms for the presented problems (from 1.59 to 3 depending on the problem). • An experimental study of the trade-off between the time complexity of the scheduler and the energy consumed by the schedule. [ABSTRACT FROM AUTHOR]

We study two generalizations of classic clustering problems called dynamic ordered k-median and dynamic k-supplier , where the points that need clustering evolve over time, and we are allowed to move the cluster centers between consecutive time steps. In these dynamic clustering problems, the general goal is to minimize certain combinations of the service cost of points and the movement cost of centers, or to minimize one subject to some constraints on the other. We obtain a constant-factor approximation algorithm for dynamic ordered k -median under mild assumptions on the input. We give a 3-approximation for dynamic k -supplier and a multi-criteria approximation for its outlier version where some points can be discarded, when the number of time steps is two. We complement the algorithms with almost matching hardness results. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the shortest link scheduling (SLS) in wireless networks under the Signal-to-Interference-plus-Noise-Ratio (SINR) constraints. We introduce a consistent graph G ¯ = (V ¯ , E ¯) where V ¯ is the links set and each edge in E ¯ indicates that its two ends can be active simultaneously. We interpret SLS as the finding of a clique partition in G ¯ and propose a fast approximation algorithm, MCBS (Maximum Clique Based Scheduling), for SLS with a uniform power assignment and with an approximation ratio to the optimal solution of O (1). Theoretical analysis demonstrates the correctness and effectiveness of the proposed algorithm. Our simulation results show that the MCBS algorithm overcomes the best known algorithms in terms of execution time and the number of time slots. [ABSTRACT FROM AUTHOR]

We introduce a novel domination problem, which we call Dual Domination (DD). We assume that the nodes in a network are partitioned into two categories: Positive nodes (V +) and negative nodes (V −). We study the Maximum Bounded Dual Domination , where, given a bound k , the problem is to find a set D ⊆ V + , which maximizes the number of nodes dominated in V + , dominating at most k nodes in V −. We show that such problem is hard to approximate to a factor better than (1 − 1 / e). We give a polynomial time algorithm with approximation guaranteed (1 − e − 1 / Δ) , where Δ represents the maximum number of neighbors in V + of any node in V − , and an O (| V | k 2) time algorithm to solve the problem on trees. We also study two related problems named Maximum Dual Domination and minimum Negative Dual Domination. For both problems, we show hardness results and provide O (| V |) time algorithms on trees. [ABSTRACT FROM AUTHOR]

For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time tractability of Horn formulas (Aspvall, Plass, and Tarjan, 1979) and Krom (i.e., 2CNF) formulas (Dowling and Gallier, 1984). Backdoors, introduced by Williams, Gomes and Selman (2003), gradually extend such a tractable class to all formulas of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a formula and a tractable class. Backdoor depth, introduced by Mählmann, Siebertz, and Vigny (2021), is a more refined distance measure, which admits the utilization of different backdoor variables in parallel. We propose FPT approximation algorithms to compute backdoor depth into the classes Horn and Krom. This leads to a linear-time algorithm for deciding the satisfiability of formulas of bounded backdoor depth into these classes. [ABSTRACT FROM AUTHOR]

Fair clustering is a constrained clustering problem where we need to partition a set of colored points. The fraction of points of each color in every cluster should be more or less equal to the fraction of points of this color in the dataset. The problem was recently introduced by Chierichetti et al. (2017) [1]. We propose a new construction of coresets for fair clustering for Euclidean and general metrics based on random sampling. For the Euclidean space R d , we provide the first coreset whose size does not depend exponentially on the dimension d. The question of whether such constructions exist was asked by Schmidt et al. (2019) [2] and Huang et al. (2019) [5]. For general metrics, our construction provides the first coreset for fair clustering. New coresets appear to be a handy tool for designing better approximation and streaming algorithms for fair and other constrained clustering variants. [ABSTRACT FROM AUTHOR]

Many systems have to be maintained while the underlying constraints, costs and/or profits change over time. Although the state of a system may evolve during time, a non-negligible transition cost is incurred for transitioning from one state to another. In order to model such situations, we look at a recently introduced multistage model where the input is a sequence of instances (one for each time step), and the goal is to find a sequence of solutions (one for each time step) that are both (i) near optimal for each time step and (ii) as stable as possible. We propose a PTAS for the Multistage Knapsack problem. This is the first approximation scheme for a combinatorial optimization problem in the considered multistage setting, and its existence contrasts with the inapproximability results for other combinatorial optimization problems that are even polynomial-time solvable in the static case. [ABSTRACT FROM AUTHOR]

We consider the directed minimum latency problem (DirLat), wherein we seek a path P visiting all points (or clients) in a given asymmetric metric starting at a given root node r , so as to minimize the sum of the client waiting times along P. We give the first constant-factor approximation guarantee for DirLat , but in quasi-polynomial time. A key ingredient of our result, and our chief technical contribution, is an extension of a recent result of Köhne et al. (2019) [17] showing that the integrality gap of the natural Held-Karp relaxation for asymmetric TSP-Path (ATSPP) is at most a constant. We also give a better approximation guarantee for the minimum total-regret problem , where the goal is to find a path P that minimizes the total time that nodes spend in excess of their shortest-path distances from r , which can be cast as a special case of DirLat involving so-called regret metrics. [ABSTRACT FROM AUTHOR]

We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint. The input is a set I of items, each has a non-negative weight, and a set of bins of arbitrary capacities. Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a packing of a subset of items A ⊆ I in the bins such that f (A) is maximized. Our main result is an almost optimal polynomial time (1 − e − 1 − ε) -approximation algorithm for the problem, for any ε > 0. The algorithm relies on a structuring technique which converts a general multiple knapsack constraint to a constraint in which the bins are partitioned into groups of exponentially increasing cardinalities, each consisting of bins of uniform capacity. We derive the result by combining structuring with a refined analysis of techniques for submodular optimization subject to knapsack constraints. [ABSTRACT FROM AUTHOR]

We study the approximability of the NP-complete Maximum Minimal Feedback Vertex Set problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied problems of this type: Maximum Minimal Vertex Cover , for which the best achievable approximation ratio is n , and Upper Dominating Set , which does not admit any n 1 − ϵ approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for Maximum Minimal Feedback Vertex Set with a ratio of O (n 2 / 3) , as well as a matching hardness of approximation bound of n 2 / 3 − ϵ , improving the previously known hardness of n 1 / 2 − ϵ. Having settled the problem's approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio r , produces an r -approximate solution in time n O (n / r 3 / 2). This time-approximation trade-off is essentially tight under the ETH. [ABSTRACT FROM AUTHOR]

We show that a constant factor approximation of the shortest and closest lattice vector problem in any ℓ p -norm can be computed in time 2 (0.802 + ε) n. This matches the currently fastest constant factor approximation algorithm for the shortest vector problem in the ℓ 2 norm. To obtain our result, we combine the latter algorithm for ℓ 2 with geometric insights related to coverings. [ABSTRACT FROM AUTHOR]

Given a set of n integer-valued coin types and a target value t , the well-known change-making problem asks for the minimum number of coins that sum to t , assuming an unlimited number of coins in each type. In the more general all-targets version of the problem, we want the minimum number of coins summing to j , for every j = 0 , ... , t. We obtain a number of new results on these problems, including (i) an algorithm for the all-targets problem with running time O ˜ (t 4 / 3) (improving a previous O ˜ (t 3 / 2) -time algorithm), (ii) a very simple O ˜ (u 2 + t) -time algorithm for the all-targets problem, where u denotes the maximum coin value, and (iii) an algorithm for the original (single-target) problem with running time O ˜ (u) (improving a previous O ˜ (t) -time algorithm by Chan and He (SOSA'20)). We also describe applications to the (single-capacity) unbounded knapsack problem and the minimum word break problem. [ABSTRACT FROM AUTHOR]

Given a digraph G = (V , E) , the k -path partition problem aims to find a minimum collection of vertex-disjoint directed paths, of order at most k , to cover all the vertices. The problem has various applications. Its special case on undirected graphs is NP-hard when k ≥ 3 , and has received much study recently from the approximation algorithm perspective. However, the general problem on digraphs is seemingly untouched in the literature. We fill the gap with the first k / 2 -approximation algorithm, based on a novel concept of enlarging walk to minimize the number of singletons. Secondly, for k = 3 , we define a second novel kind of enlarging walks to greedily reduce the number of 2-paths in the 3-path partition and propose an improved 13/9-approximation algorithm. Lastly, for any k ≥ 7 , we present an improved (k + 2) / 3 -approximation algorithm built on the maximum path-cycle cover followed by a careful 2-cycle elimination process. [ABSTRACT FROM AUTHOR]

This work firstly studies the Steiner tree problem with bounded edge-length d in which d is the ratio of the maximum edge cost to the minimum edge cost. This work analyzes the algorithm of Byrka et al. [19] and shows that the approximation ratio of d ln ⁡ 4 d + ln ⁡ 4 − 1 + ϵ for general graphs and approximation ratio of 73 ⋅ d 60 ⋅ d + 13 + ϵ for quasi-bipartite graphs. The algorithm implies approximation ratio of 1.162 + ϵ for the problem on complete graphs with edge distances 1 and 2. This finding represents an improvement upon the previous best approximation ratio of 1.25. This work then presents a combinatorial two-phase heuristic for the general Steiner tree in greedy strategy that achieves an approximation ratio of 1.4295. [ABSTRACT FROM AUTHOR]

We obtain approximation ratio 4 + 2 ℓ ≈ 4 + 4 lg ⁡ k lg ⁡ n − lg ⁡ k for the (undirected) k -Connected Subgraph problem, where ℓ = ⌊ lg ⁡ n − lg ⁡ k + 1 2 lg ⁡ k + 1 ⌋ is the largest integer such that 2 ℓ − 1 k 2 ℓ + 1 ≤ n. For large values of n this improves the ratio 6 of Cheriyan and Végh [4] when n ≥ k 3 (the case ℓ = 1). Our result implies an fpt-approximation ratio 4 + ϵ that matches (up to the "+ ϵ " term) the best known ratio 4 for k = 6 , 7 for both the general and the easier augmentation versions of the problem. Similar results are shown for the problem of covering an arbitrary symmetric crossing supermodular biset function. [ABSTRACT FROM AUTHOR]

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]

We study clustering problems such as k -Median, k -Means, and Facility Location in graphs of low highway dimension, which is a graph parameter modeling transportation networks. It was previously shown that approximation schemes for these problems exist, which either run in quasi-polynomial time (assuming constant highway dimension) (Feldmann et al., 2018) [8] or run in FPT time (parameterized by the number of clusters k , the highway dimension, and the approximation factor) (Becker et al., 2018; Braverman et al., 2021) [9,10]. In this paper we show that a polynomial-time approximation scheme (PTAS) exists (assuming constant highway dimension). We also show that the considered problems are NP-hard on graphs of highway dimension 1. [ABSTRACT FROM AUTHOR]

• The placement of data and the scheduling of request are studied in edge caching. • Network unreliability and limited storage and bandwidth resources are considered. • Two algorithms with different computation complexity and cache efficiency are developed. • The experiments are conducted to evaluate the performance of proposed caching strategies. Edge caching is a prevailing media delivery technology where data is hosted at the edge nodes with computing and storage capability in close proximity to users, in order to expand the backhaul network capacity and enhance users' quality of experience (QoE). The existing work in this area often neglects the fact that large-scale distributed cache networks are not particularly reliable and many edge nodes are prone to failure. In this paper we investigate and develop a novel, cooperative caching mechanism for content placement and request routing. We aim to minimize the content access delay and achieve the optimization in polynomial time, taking into account failures in an unreliable network environment with limited edge storage and bandwidth. We introduce two optimization algorithms: 1) a primal-dual algorithm that is based on the Lagrangian dual decomposition and subgradient method, and 2) a greedy-based approximation algorithm with a proven approximation ratio. Numerical results show that the proposed algorithms outperform other comparative approaches in synthetic and real network environments, and the approximation algorithm is particularly suitable for networking scenarios with sparse node connectivity and resources in short supply. [ABSTRACT FROM AUTHOR]

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in contrast to practice where data is inherently dynamic. A temporal graph has an edge set that changes over time. We present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and integers k and Δ, we ask for a coloring sequence with at most k colors for each vertex such that in every time window of Δ consecutive time steps, in which an edge is present, this edge is properly colored at least once. We thoroughly investigate the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. [ABSTRACT FROM AUTHOR]

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes spread are dynamic in nature, and can be modelled with temporal graphs. Here, we study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path. We introduce a natural edge-deletion problem for temporal graphs and provide positive and negative results on its computational complexity and approximability. [ABSTRACT FROM AUTHOR]

In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G , the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum number of internal vertices. We present an approximation algorithm with performance ratio 4 3 , which improves upon the best known performance ratio 3 2. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree. We can also give an example to show that the performance ratio 4 3 is actually tight for this algorithm. Finally, we show that MIST is Max-SNP-hard. [ABSTRACT FROM AUTHOR]

The modularity is the best known and widely used quality function for community detection in graphs. We investigate the approximability of the modularity maximization problem and some related problems. We first design a polynomial-time 0.4209-additive approximation algorithm for the modularity maximization problem, which improves the current best additive approximation error of 0.4672. Our theoretical analysis also demonstrates that the proposed algorithm obtains a nearly-optimal solution for any instance with a high modularity value. We next design a polynomial-time 0.1660-additive approximation algorithm for the maximum modularity cut problem. Finally, we extend our algorithm to some related problems. [ABSTRACT FROM AUTHOR]

Maximum parsimony distance is a measure used to quantify the dissimilarity of two unrooted phylogenetic trees. It is NP-hard to compute, and very few positive algorithmic results are known due to its complex combinatorial structure. Here we address this shortcoming by showing that the problem is fixed parameter tractable. We do this by establishing a linear kernel i.e., that after applying certain reduction rules the resulting instance has size that is bounded by a linear function of the distance. As powerful corollaries to this result we prove that the problem permits a polynomial-time constant-factor approximation algorithm; that the treewidth of a natural auxiliary graph structure encountered in phylogenetics is bounded by a function of the distance; and that the distance is within a constant factor of the size of a maximum agreement forest of the two trees, a well studied object in phylogenetics. [ABSTRACT FROM AUTHOR]

We consider Internet of Things (IoT) sensors deployed inside an area to be monitored. Drones can be used to collect the data from the sensors, but they are constrained in energy and storage. Therefore, all drones need to select a subset of sensors whose data are the most relevant to be acquired, modeled by assigning a reward. We present an optimization problem called Multiple-drone Data-collection Maximization Problem (MDMP) whose objective is to plan a set of drones' missions aimed at maximizing the overall reward from the collected data, and such that each individual drone's mission energy cost and total collected data are within the energy and storage limits, respectively. We optimally solve MDMP by proposing an Integer Linear Programming based algorithm. Since MDMP is NP -hard, we devise suboptimal algorithms for single- and multiple-drone scenarios. Finally, we thoroughly evaluate our algorithms on the basis of random generated synthetic data. [ABSTRACT FROM AUTHOR]

A garden is populated by n bamboos, each with its own daily growth rate. The Bamboo Garden Trimming Problem (BGT) is to design for a robotic gardener a perpetual schedule of cutting bamboos to keep the elevation of the garden as low as possible. The frequency of cutting is constrained by the time needed to move from one bamboo to the next, which is one day in Discrete BGT and is defined by the distance between the two bamboos in Continuous BGT. The bamboo garden is a metaphor for a collection of machines which have to be serviced, with different frequencies, by a robot which can service only one machine at a time. For Discrete BGT, we show tighter approximation algorithms, with one of them settling a long-standing conjecture about the related Pinwheel problem. For Continuous BGT, we propose approximation algorithms which achieve logarithmic approximation ratios. [ABSTRACT FROM AUTHOR]

Given a graph G with vertex set V , a set S ⊆ V is a secure dominating set of G if S is a dominating set of G and if for every vertex u ∈ V ∖ S , there exists a vertex v ∈ S adjacent to u such that (S ∪ { u }) ∖ { v } is a dominating set of G.The minimum secure dominating set (or, for short, MSDS) problem asks to find an MSDS in a given graph. In this paper, we first show that the decision version of the MSDS problem is NP-complete in unit disk graphs, even in grid graphs. Secondly, we give an O (n + m) time t -approximation algorithm for the MSDS problem in several geometric intersection graphs which are K 1 , t -free for some integer t ≥ 3. Finally, we propose a PTAS for the MSDS problem in unit disk graphs. [ABSTRACT FROM AUTHOR]

Coflow is a network abstraction used to represent communication patterns in data centers. The coflow scheduling problem encountered in large data centers is a challenging NP -hard problem. Many previous studies on coflow scheduling mainly focus on the single-core model. However, with the growth of data centers, this single-core model is no longer sufficient. This paper addresses the coflow scheduling problem within heterogeneous parallel networks, which feature an architecture consisting of multiple network cores running in parallel. In this paper, two polynomial-time approximation algorithms are developed for the flow-level scheduling problem and the coflow-level scheduling problem in heterogeneous parallel networks, respectively. For the flow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O (log ⁡ m / log ⁡ log ⁡ m) when all coflows are released at arbitrary times, where m represents the number of network cores. On the other hand, in the coflow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O (m (log ⁡ m / log ⁡ log ⁡ m) 2) when all coflows are released at arbitrary times. Moreover, we propose a heuristic algorithm for the flow-level scheduling problem. Simulation results using synthetic traffic traces validate the performance of our algorithms and show improvements over the previous algorithm. • Algorithm achieves O (log ⁡ m / log ⁡ log ⁡ m) approximation ratio for flow-level scheduling, where m is network cores. • For coflow-level scheduling, algorithm achieves O (m (log ⁡ m / log ⁡ log ⁡ m) 2) approximation ratio. • Moreover, this paper proposes a heuristic algorithm for the flow-level scheduling problem. [ABSTRACT FROM AUTHOR]

Fog computing is an emerging paradigm that brings computing capabilities closer to distributed IoT devices, which provides networking services between end devices and traditional cloud data centers. One important mission is to further reduce the monetary cost of fog resources while meeting the ever-growing demands of multiple users. In this paper, we focus on minimizing the total cost for multiple mobile users to provide an efficient resource provisioning scheme in fog computing. The total cost includes two aspects: the replication cost and the transmission cost. We consider three cases for the resource provision problem by focusing on different cost models. First, one simple case where users can only upload one replication is discussed, and an optimal solution is proposed by converting the original problem into a bipartite graph matching. Then we consider a more complicated case in which each user can upload multiple replications on fog nodes in the resource provisioning. Specifically, two models are discussed: the 0–1 transmission cost model and the different transmission cost model. For the 0–1 transmission cost model, each user can upload multiple replications with a constant transmission cost, and one optimal greedy solution is proposed. For the different transmission cost model, the transmission cost is related to the distance of each pair of fog nodes. This problem is proven to be NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. Extensive simulations also prove the efficiency of our schemes. • We consider the resource provision problem for users with cost minimization and model the identified problem by considering two types of cost: replication cost and transmission cost. We first discuss a simple case, and one optimal solution is proposed. We then consider a more complicated case in which each user can upload multiple replications on fog nodes in the provisioning process. Two models are discussed: the 0–1 transmission cost model and the different transmission cost model. • We propose an optimal solution for the 0–1 transmission cost model. Then we prove that the problem under the different transmission cost model is NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. • Various simulations were conducted to compare our joint optimization methods with several state-of-the-art ones based on two real datasets: the Mobike dataset and the Microsoft GPS trajectory dataset. The results are shown from different perspectives to provide conclusions. [ABSTRACT FROM AUTHOR]

Translocation has been long learned as a basic operation to rearrange the structure of a genome. Translocation sorting asks to find a shortest sequence of translocations that transforms one genome into another, which has attracted attention of many scientists in algorithm design. Signed translocation sorting can be solved in polynomial time. Unsigned translocation sorting turns out to be NP-Hard and Max-SNP-Hard. The best known approximation algorithm by now for unsigned translocation sorting can achieve a performance ratio 1.408. In this paper, we propose a new approximation algorithm for unsigned translocation sorting which can achieve a asymptotic performance ratio 1.375. [ABSTRACT FROM AUTHOR]

A graph G = (V , E) is δ -hyperbolic if for any four vertices u , v , w , x , the two larger of the three distance sums d (u , v) + d (w , x) , d (u , w) + d (v , x) , d (u , x) + d (v , w) differ by at most 2 δ ≥ 0. This paper describes the eccentricity terrain of a δ -hyperbolic graph. The eccentricity function e G (v) = max ⁡ { d (v , u) : u ∈ V } partitions vertices of G into eccentricity layers C k (G) = { v ∈ V : e G (v) = r a d (G) + k } , k ∈ N , where r a d (G) = min ⁡ { e G (v) : v ∈ V } is the radius of G. The paper studies the eccentricity layers of vertices along shortest paths, identifying such terrain features as hills, plains, valleys, terraces, and plateaus. It introduces the notion of β -pseudoconvexity, which implies Gromov's ϵ -quasiconvexity, and illustrates the abundance of pseudoconvex sets in δ -hyperbolic graphs. It shows that all sets C ≤ k (G) = { v ∈ V : e G (v) ≤ r a d (G) + k } , k ∈ N , are (2 δ − 1) -pseudoconvex. Several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities. [ABSTRACT FROM AUTHOR]

Truth Discovery is an important learning problem arising in data analytics related fields. It concerns about finding the most trustworthy information from a dataset acquired from a number of unreliable sources. The problem has been extensively studied and a number of techniques have already been proposed. However, all of them are of heuristic nature and do not have any quality guarantee. In this paper, we formulate the problem as a high dimensional geometric optimization problem, called Entropy based Geometric Variance. Relying on a number of novel geometric techniques, we further discover new insights to this problem. We show, for the first time, that the truth discovery problem can be solved with guaranteed quality of solution. Particularly, it is possible to achieve a (1 + ϵ) -approximation within nearly linear time under some reasonable assumptions. We expect that our algorithm will be useful for other data related applications. [ABSTRACT FROM AUTHOR]

We present the first study of non-deterministic weighted automata under probabilistic semantics. In this semantics words are random events, generated by a Markov chain, and functions computed by weighted automata are random variables. We consider the probabilistic questions of computing the expected value and the cumulative distribution for such random variables. The exact answers to the probabilistic questions for non-deterministic automata can be irrational and are uncomputable in general. To overcome this limitation, we propose approximation algorithms for the probabilistic questions, which work in exponential time in the size of the automaton and polynomial time in the size of the Markov chain and the given precision. We apply this result to show that non-deterministic automata can be effectively determinised with respect to the standard deviation metric. [ABSTRACT FROM AUTHOR]

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions. [ABSTRACT FROM AUTHOR]

We investigate the toroidal expanse of an embedded graph G , that is, the size of the largest toroidal grid contained in G as a minor. In the course of this work we introduce a new embedding density parameter, the stretch of an embedded graph G , and use it to bound the toroidal expanse from above and from below within a constant factor depending only on the genus and the maximum degree. We also show that these parameters are tightly related to the planar crossing number of G. As a consequence of our bounds, we derive an efficient constant factor approximation algorithm for the toroidal expanse and for the crossing number of a surface-embedded graph with bounded maximum degree. [ABSTRACT FROM AUTHOR]

Approximation algorithms for scheduling parallel machines have been studied for decades, leading to significant progress in terms of their approximation guarantees. The algorithms that provide near optimal performance are not feasible to use in practice due to their huge execution time requirements, thus underscoring the importance of developing efficient parallel approximation algorithms with near-optimal performance guarantees that are suitable for execution on current parallel systems, such as multi-core systems. We present the design and analysis of a parallel approximation algorithm for the problem of scheduling jobs on parallel identical machines to minimize makespan. The design of the parallel approximation algorithm is based on the best existing polynomial-time approximation scheme (PTAS) for the problem. To the best of our knowledge, this is the first practical parallel approximation algorithm for the minimum makespan scheduling problem that maintains the approximation guarantees of the sequential PTAS and it is specifically designed for execution on shared-memory parallel machines. We implement and run the algorithm on a large multi-core system and perform an extensive experimental analysis on data generated from realistic probability distributions. The results show that our proposed parallel approximation algorithm achieves significant speedup with respect to both the sequential PTAS and the CPLEX-based solver that solves the mixed integer program formulation of the problem. • A parallel approximation algorithm for scheduling parallel identical machines is proposed. • The proposed algorithm has the same approximation guarantees as the sequential PTAS. • The proposed algorithm is suitable for implementation on multi-core systems. [ABSTRACT FROM AUTHOR]

We combine two fundamental optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency and minimally resolved supertree into a new problem, which we call q-maximum rooted triplets consistency (q -MAXRTC). It takes as input a set R of rooted, binary phylogenetic trees with three leaves each and asks for a phylogenetic tree with exactly q internal nodes that contains the largest possible number of trees from R. We prove that q -MAXRTC is NP-hard to approximate within a constant, develop polynomial-time approximation algorithms for different values of q , and show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much branching information. To demonstrate the algorithmic advantage of using trees with few internal nodes, we also propose a new algorithm for computing the rooted triplet distance that is faster than the existing algorithms when restricted to such trees. [ABSTRACT FROM AUTHOR]

Abstract It is well-known that every non-negative univariate real polynomial can be written as the sum of two polynomial squares with real coefficients. When one allows a (non-negatively) weighted sum of finitely many squares instead of a sum of two squares, then one can choose all coefficients in the representation to lie in the field generated by the coefficients of the polynomial. In particular, this allows for an effective treatment of polynomials with rational coefficients. In this article, we describe, analyze and compare, from both the theoretical and practical points of view, two algorithms computing such a weighted sum of squares decomposition for univariate polynomials with rational coefficients. The first algorithm, due to the third author, relies on real root isolation, quadratic approximations of positive polynomials and square-free decomposition, but its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm. They are exponential in the degree of the input univariate polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using quantifier elimination and root isolation bounds. The second algorithm, due to Chevillard, Harrison, Joldes and Lauter, relies on complex root isolation and square-free decomposition, and was introduced for certifying positiveness of polynomials in the context of computer arithmetic. Again, its complexity was not analyzed. We provide bit complexity estimates, both on the runtime and the output size of this algorithm, which are polynomial in the degree of the input polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using Vieta's formula and root isolation bounds. Finally, we report on our implementations of both algorithms and compare them in practice on several application benchmarks. While the second algorithm is, as expected from the complexity result, more efficient on most of examples, we exhibit families of non-negative polynomials for which the first algorithm is better. [ABSTRACT FROM AUTHOR]

Abstract In sum coloring, it is required to find a proper coloring of the vertices of a graph using positive integers, such that the sum of colors of the vertices is minimized. First Fit is the natural coloring algorithm that processes vertices one by one (in some order), and colors the current vertex with the minimum color that was not used for any of its already considered neighbors. Here, we study the approximation ratio of First Fit for sum coloring for the class of claw-free graphs, its most natural subclasses, and its generalizations, and get tight bounds for it. Highlights • A thorough study of the approximation ratio for the natural algorithm First Fit. • A study of sum coloring of graphs, of vertices or edges. • A tight analysis of (k + 1)-claw free graphs, with new types of examples. • A tight analysis for important subclasses of via linear programs. • A tight analysis for edge coloring and a tight analysis for unit interval graphs. [ABSTRACT FROM AUTHOR]

Abstract An HV-graph is a planar graph with vertex-degree at most four such that each edge is labeled either H (horizontal) or V (vertical). The HV-planarity testing problem asks whether an HV-graph admits an HV-drawing , that is, a planar drawing such that each edge with label H is drawn as a horizontal segment and each edge with label V is drawn as a vertical segment. We prove that the HV-planarity testing problem is NP-complete even for graphs with vertex-degree at most three, which answers an open question posed by both Manuch et al. [30] and Durocher et al. [17]. On the positive side, we prove that the HV-planarity testing problem can be solved in polynomial-time for series-parallel graphs. This result significantly extends a previous result by Durocher et al. about HV-planarity testing of biconnected outerplanar graphs of maximum vertex-degree three. Highlights • HV-planarity testing is NP-complete, even for graphs with vertex-degree at most 3. • Polynomial-time HV-planarity testing for 2-connected series-parallel graphs. • Polynomial-time HV-planarity testing for partial 2-trees. [ABSTRACT FROM AUTHOR]

Abstract Let R be a finite set of terminals in a convex metric space (M , d). We give approximation algorithms for problems of finding a minimum size set S ⊆ M of additional points such that the unit-disc graph G [ R ∪ S ] of R ∪ S satisfies some connectivity properties. Let Δ be the maximum number of independent points in a unit ball. For the Steiner Tree with Minimum Number of Steiner Points problem we obtain approximation ratio 1 + ln ⁡ (Δ − 1) + ϵ , which in R 2 reduces to 1 + ln ⁡ 4 + ϵ < 2.3863 + ϵ ; this improves the ratios ⌊ (Δ + 1) / 2 ⌋ + 1 + ϵ of [19] and 2.5 + ϵ of [7] , respectively. For the Steiner Forest with Minimum Number of Steiner Points problem we give a simple Δ-approximation algorithm, improving the ratio 2 (Δ − 1) of [21]. We also simplify the Δ-approximation of [4] , when G [ R ∪ S ] should be 2-connected. Highlights • We consider connectivity problems on unit-disc graphs in a convex metric space. • Let Δ be the maximum number of independent points in a unit ball. • For Steiner Tree with Minimum Number of Steiner Points we improve the ratio (Δ + 1) / 2 to 1 + ln ⁡ (Δ − 1). • For Steiner Forest with Minimum Number of Steiner Points we improve the ratio 2 (Δ − 1) to Δ. [ABSTRACT FROM AUTHOR]

We study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Γ consisting of finitary functions on a fixed finite domain. Ene et al. have shown that, under a mild technical condition, the basic LP relaxation is optimal for constant-factor approximation for VCSP ( Γ ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we give new natural algebraic conditions for the finiteness of the integrality gap for the basic LP relaxation of VCSP ( Γ ) and show how this leads to efficient constant-factor approximation algorithms for several examples that cover all previously known cases that are NP-hard to solve to optimality but admit constant-factor approximation. Finally, we show that the absence of another algebraic condition leads to NP-hardness of constant-factor approximation. Thus, our results indicate where the boundary of constant-factor approximability for VCSPs lies. [ABSTRACT FROM AUTHOR]

Abstract We propose a novel weakly supervised localization method based on Fisher-embedding of low-level features (CNN, SIFT), and model sparsity at the component level. Fisher-embedding provides an interesting alternative to raw low-level features, since it allows fast and accurate scoring of image subwindows with a model trained on entire images. Model sparsity reduces overfitting and enables fast evaluation. We also propose two new techniques for improving performance when our method is combined with nonlinear normalizations of the aggregated Fisher representation of the image. These techniques are (i) intra-component metric normalization and (ii) first-order approximation to the score of a normalized image representation. We evaluate our weakly supervised localization method on real traffic scenes acquired from driver's perspective. The method dramatically improves the localization AP over the dense non-normalized Fisher vector baseline (16 percentage points for zebra crossings, 21 percentage points for traffic signs) and leads to a huge gain in execution speed (91 × for zebra crossings, 74 × for traffic signs). Graphical abstract Highlights • We propose weakly-supervised localization based on patch-level Fisher embedding. • A sliding window localization model is trained on entire images. • Component-level sparsity enables fast evaluation and reduces overfitting. • Approximated patch scoring allows the use of non-linear normalizations. • We present road-mapping experiments on two kinds of local features (SIFT, CNN). [ABSTRACT FROM AUTHOR]

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of study on this problem, focusing on exact and approximation algorithms. It is thus natural to consider whether these algorithms can be further improved in terms of running times. We provide strong lower bounds on the running times of exact and approximation schemes for the classical scheduling problem based on Exponential Time Hypothesis, showing that the best known approximation and exact algorithms are almost the best possible in terms of the running time. [ABSTRACT FROM AUTHOR]