Search

We study the scheduling problem with calibrations. We are given a set of n jobs that need to be scheduled on a set of m machines. However, a machine can schedule jobs only if a calibration has been performed beforehand and the machine is considered as valid during a fixed time period of T , after which it must be recalibrated before running more jobs. In this paper, we investigate the batch calibrations; calibrations occur in batch and at the same moment. It is then not possible to perform any calibrations during a period of T. We consider different cost function depending on the number of machines we calibrate at a given time, i.e., the cost function is denoted as f (x) where x is the number of calibrations in the batch. Moreover, jobs have release time, deadline, and unit processing time. The objective is to schedule all jobs with the minimum cost of calibrations. We give a dynamic program to solve the case with an arbitrary cost function. Then, we propose several faster approximation algorithms for different cost functions: an optimal algorithm when f (x) = b , a 3-approximation algorithm when f (x) = x and a (m + b) / (b + 1) -approximation algorithm when f (x) = x + b. The running time of these algorithms are O (n 2). [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]

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

• 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]

This paper studies the problem of scheduling n two-stage jobs on m multiple two-stage flowshops, with the objective of minimizing the makespan. The problem is NP-hard even when m is a fixed constant, and becomes strongly NP-hard when m is part of the input. A 2.6-approximation algorithm along with its analysis is presented for an arbitrary m ≥ 2. This is the first approximation algorithm for multiple flowshops when the number m of flowshops is part of the input. The fact that m is part of the input and the time complexity O (n log ⁡ n) of the algorithm demonstrate that the problem, which plays an important role in the current research in cloud computing and data centers, can be solved efficiently with a reasonable level of satisfaction. • The paper is motivated by current research in data centers and cloud computing, and addresses an important optimization problem in the area. • The paper gives the first approximation algorithm for scheduling two-stage jobs on m multiple two-stage flowshops, where m is part of the input. • The paper introduces a technique of the "cutting job" so that the completion time of a flowshop can be expressed precisely in terms of the cutting job. • The 2.6-approximation algorithm in the current paper, which runs in time O (n log ⁡ n) for an arbitrary m , provides an efficient solution in practice. [ABSTRACT FROM AUTHOR]

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

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]

Diffusion on complex networks is often modeled as a stochastic process. Yet, recent work on strategic diffusion emphasizes the decision power of agents [1] and treats diffusion as a strategic problem. Here we study the computational aspects of strategic diffusion, i.e. , finding the optimal sequence of nodes to activate a network in the minimum time. We prove that finding an optimal solution to this problem is NP-complete in a general case. To overcome this computational difficulty, we present an algorithm to compute an optimal solution based on a dynamic programming technique. We also show that the problem is fixed parameter-tractable when parametrized by the product of the treewidth and maximum degree. We analyze the possibility of developing an efficient approximation algorithm and show that two heuristic algorithms proposed so far cannot have better than a logarithmic approximation guarantee. Finally, we prove that the problem does not admit better than a logarithmic approximation, unless P=NP. [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]

A widely studied model of influence diffusion in social networks represents the network as a graph G = (V , E) , with an integer influence threshold t (v) for each node, and the diffusion process as follows: Initially the members of a chosen set S ⊆ V are influenced and, during each subsequent round, the set of influenced nodes is augmented by including every new node v that has at least t (v) previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using incentives to reduce the thresholds of some nodes. The goal is to minimize the total amount of the incentive required to ensure that the information diffusion process terminates within a given number of rounds λ. The problem is hard to approximate in general networks. We present optimal polynomial-time algorithms for paths, cycles, trees, and complete networks for any λ. For the special case λ = 1 , we present a polynomial-time algorithm with a logarithmic approximation guarantee for any network. [ABSTRACT FROM AUTHOR]

We give a distributed (1 + ϵ) -approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O (1 ϵ log ⁎ ⁡ n) rounds. If nodes are aware of their interval representations, then the algorithm can be adapted to the CONGEST model using the same number of rounds. Prior to this work, only constant factor approximations using O (log ⁎ ⁡ n) rounds were known [1]. Linial's ring coloring lower bound implies that the dependency on log ⁎ ⁡ n cannot be improved. We further prove that the dependency on 1 ϵ is also optimal. To obtain our CONGEST model algorithm, we develop a color rotation technique that may be of independent interest. We demonstrate that color rotations can also be applied to obtain a (1 + ϵ) -approximate multicoloring of directed trees in O (1 ϵ log ⁎ ⁡ n) rounds. [ABSTRACT FROM AUTHOR]

We study a new model of verification of boolean predicates over distributed networks. Given a network configuration, the proof-labeling scheme (PLS) model defines a distributed proof in the form of a label that is given to each node, and all nodes locally verify that the network configuration satisfies the desired boolean predicate by exchanging labels with their neighbors. The proof size of the scheme is defined to be the maximum size of a label. In this work, we extend this model by defining the approximate proof-labeling scheme (APLS) model. In this new model, the predicates for verification are of the form ψ ≤ φ , where ψ , φ : F → N for a family of configurations F. Informally, the predicates considered in this model are a comparison between two values of the configuration. As in the PLS model, nodes exchange labels in order to locally verify the predicate, and all must accept if the network satisfies the predicate. The soundness condition is relaxed with an approximation ration α , so that only if ψ > α φ some node must reject. We focus on two verification problems: upper and lower bounds on the diameter of the graph, and the maximality of a given matching. For these problems, we present the first results that apply to all graph structures. In our new APLS model, we show that the proof size can be much smaller than the proof size of the same predicate in the PLS model. Moreover, we prove that there is a tradeoff between the approximation ratio and the proof size. Finally, we present the first general result for maximum cardinality matching in the PLS model. [ABSTRACT FROM AUTHOR]

We study the minimum connected sensor cover problem (MIN - CSC) and the budgeted connected sensor cover (Budgeted - CSC) problem, both motivated by important applications (e.g., reduce the communication cost among sensors) in wireless sensor networks. In both problems, we are given a set of sensors and a set of target points in the Euclidean plane. In MIN - CSC , our goal is to find a set of sensors of minimum cardinality, such that all target points are covered, and all sensors can communicate with each other (i.e., the communication graph is connected). We obtain a constant factor approximation algorithm, assuming that the ratio between the sensor radius and communication radius is bounded. In Budgeted - CSC problem, our goal is to choose a set of B sensors, such that the number of targets covered by the chosen sensors is maximized and the communication graph is connected. We also obtain a constant approximation under the same assumption. [ABSTRACT FROM AUTHOR]

Consider a scenario in which a set of n agents hold items, where each item can be of one out of m possible types (colors). The agents are connected by an arbitrary network and have to distributively find a repartition of the colors such that the amount of colors for each agent is as balanced as possible: in the particular case where m is a multiple of n , each agent must have exactly m / n colors. More formally, the goal is to let the agents agree on an assignment of colors to agents such that the following two conditions hold: (i) each color is assigned to exactly one agent; (ii) each agent has at least ⌊ m / n ⌋ and at most ⌈ m / n ⌉ colors. Among all possible such repartitions, we seek for the one that minimizes the number of "changes" (measured in terms of misplaced items) with respect to the initial configuration. In other words, our aim is to design a distributed algorithm that finds a balanced coloring of minimum cost, where the cost of a coloring is the number of items that need to be relocated. This kind of questions, usually modeled as generalized bipartite matching problems , have been studied in the distributed setting only on clusters of commodity nodes with the aim of copying with real-world massive instances, which may involve millions of agents and colors. Here we propose the first distributed algorithm designed to run on an arbitrary network with the agents as nodes. Our algorithm turns out to be efficient in terms of both time and message complexity for a large class of graphs. Our results can be outlined as follows. We prove a lower bound Ω (m / n ⋅ D 2) on message complexity, where D is the diameter of the graph, that holds for any approximation algorithm whose solution has cost at most 2 (α − 2) / α times the cost of any optimal solution, for every constant α > 2. We give a distributed deterministic algorithm with time complexity O (max ⁡ { n 2 , D log ⁡ q }) and message complexity O (n log ⁡ n ⋅ (log ⁡ q + m log ⁡ m)) , where q is the maximum number of items of a given color held by any agent. We show that the cost of our solution for arbitrary graphs is at most (2 + δ) times the optimal cost, for any δ > 0. We finally observe that, for large diameter graphs (i.e. , D = Ω (n ϵ) , ϵ > 0), we get matching lower and upper bounds on message complexity for the vast majority of instances of potential interest, that is, instances with polynomial number of colors and (up to) super-exponential number of items. [ABSTRACT FROM AUTHOR]

A k -dominating set in a graph G = (V , E) is a set U ⊆ V such that every vertex of G is either in U or has at least k neighbors in U. In this paper we give simple distributed approximation algorithms in the standard Local model of computations for the minimum k -dominating set problem for k ≥ 2 in graphs with no K 3 , h -minor for some h ∈ Z + and graphs with no K 4 , 4 -minor. In particular, this gives fast distributed approximations for graphs of bounded genus and linklessly embeddable graphs. The algorithms give a constant approximation ratio and run in a constant number of rounds. In addition, we will give a (1 + ϵ) -approximation for an arbitrary fixed ϵ > 0 which runs in O (log ⁎ ⁡ n) rounds where n is the order of a graph. [ABSTRACT FROM AUTHOR]

Let there be a set J of n jobs and a set M of m parallel machines, where each job J j takes p i , j ∈ Z + time units on machine M i and assume p i , j = ∞ implies job J j cannot be scheduled on machine M i. In makespan minimization on unrelated parallel machines (R | | C m a x), the goal is to schedule each job non-preemptively on a machine so as to minimize the makespan. A job-intersection graph G J = (J , E J) is an unweighted undirected graph where there is an edge { J j , J j ′ } ∈ E J if there is a machine M i such that both p i , j ≠ ∞ and p i , j ′ ≠ ∞. In this paper we consider two variants of R | | C m a x where there are a small number of eligible jobs per machine. First, we prove that there are no approximation algorithms with approximation ratios less than 3/2 for R | | C m a x when restricted to instances with job-intersection graphs belonging to some graph classes such as diamondless graphs and planar graphs, unless P = NP. Second, we match this lower bound by presenting a 3/2-approximation algorithm for R | | C m a x restricted to instances with diamondless job-intersection graphs, and furthermore show that when G J is triangle free R | | C m a x is solvable in polynomial time. For R | | C m a x restricted to instances when every machine can process at most ℓ jobs, we give an approximation algorithm with approximation ratios 3/2 and 5/3 for ℓ = 3 and ℓ = 4 respectively, a polynomial-time algorithm when ℓ = 2 , and prove that it is NP -hard to approximate the optimum solution within a factor less than 3/2 when ℓ ≥ 3. In the special case where every p i , j ∈ { p j , ∞ } , called the restricted assignment problem, and there are only two job lengths p j ∈ { α , β } we present a (2 − 1 / (ℓ − 1)) -approximation algorithm when ℓ ≥ 3. In addition, we give a 2-approximation algorithm for the so-called unrelated graph balancing problem for ℓ = 3 in the case where J is partitioned into b sets called bags, and no two jobs from the same bag can be scheduled on the same machine. [ABSTRACT FROM AUTHOR]

We consider the problem of approximating the smallest 2-vertex connected spanning subgraph (2VCSS) of a 2-vertex connected directed graph, and provide new efficient algorithms. We provide two linear-time algorithms, the first based on a linear-time test for 2-vertex connectivity and divergent spanning trees, and the second based on low-high orders, that correspondingly give 3- and 2-approximations. Then we show that these linear-time algorithms can be combined with an algorithm of Cheriyan and Thurimella that achieves a 3/2-approximation. The combined algorithms preserve the 3/2 approximation guarantee of the Cheriyan-Thurimella algorithm and improve its running time from O (m 2) to O (m n + n 2) , for a digraph with n vertices and m edges. Finally, we present an experimental evaluation of the above algorithms for a variety of input data. The experimental results show that our linear-time algorithms perform very well in practice. Furthermore, the experiments show that the combined algorithms not only improve the running time of the Cheriyan-Thurimella algorithm, but it may also compute a better solution. [ABSTRACT FROM AUTHOR]

• This relationship between the multiple two-stage flowshops problem and the classical MAKESPAN problem is studied. • If the MAKESPAN problem has an α -approximation algorithm, then the problem has a 2 α -approximation algorithm. • Two restricted cases of the problem, which are of practical importance, have an (α + 1 / 2)-approximation algorithm. • The approximation ratios 2.6 for the problem and 11/6 for two restricted cases are improved to 2 + ϵ and 1.5 + ϵ respectively. This paper considers the problem of scheduling n two-stage jobs on m two-stage flowshops so as to minimize the makespan. By studying the relationship between the problem and the classical makespan problem, we prove that if there is an α -approximation algorithm for the makespan problem, then for the general case of the problem, we can construct a 2 α -approximation algorithm, and for two restricted cases which are of practical importance, we can construct an (α + 1 / 2) -approximation algorithm. As a result, by employing the polynomial-time approximation scheme for the makespan problem, we get a (2 + ϵ) -approximation algorithm for the general case and a (1.5 + ϵ) -approximation algorithm for the two restricted cases, which significantly improve the previous approximation ratios 2.6 and 11/6 respectively. [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]

Let G = (V , E , w) be a Δ β -metric graph with a distance function w (⋅ , ⋅) on V such that w (v , v) = 0 , w (u , v) = w (v , u) , and w (u , v) ≤ β ⋅ (w (u , x) + w (x , v)) for all u , v , x ∈ V. Given a positive integer p , let H be a spanning subgraph of G satisfying the conditions that vertices (hubs) in C ⊂ V form a clique of size at most p in H , vertices (non-hubs) in V ∖ C form an independent set in H , and each non-hub v ∈ V ∖ C is adjacent to exactly one hub in C. Define d H (u , v) = w (u , f (u)) + w (f (u) , f (v)) + w (v , f (v)) where f (u) and f (v) are hubs adjacent to u and v in H respectively. Notice that if u is a hub in H then w (u , f (u)) = 0. Let r (H) = ∑ u , v ∈ V d H (u , v) be the routing cost of H. The Single Allocation at most p -Hub Center Routing problem is to find a spanning subgraph H of G such that r (H) is minimized. In this paper, we show that the Single Allocation at most p -Hub Center Routing problem is NP-hard in Δ β -metric graphs for any β > 1 / 2. Moreover, we give 2 β -approximation algorithms running in time O (n 2) for any β > 1 / 2 where n is the number of vertices in the input graph. Finally, we show that the approximation ratio of our algorithms is at least Ω (β) , and we examine the structure of any potential o (β) -approximation algorithm. [ABSTRACT FROM AUTHOR]

A group of mobile robots (beachcombers) have to search collectively every point of a given domain. At any given moment, each robot can be in walking mode or in searching mode. It is assumed that each robot's maximum allowed searching speed is strictly smaller than its maximum allowed walking speed. A point of the domain is searched if at least one of the robots visits it in searching mode. The Beachcombers' Problem consists in developing efficient schedules (algorithms) for the robots which collectively search all the points of the given domain as fast as possible. We consider searching schedules in the following one-dimensional geometric domains: the cycle of a known circumference L , the finite straight line segment of a known length L , and the semi-infinite line [ 0 , + ∞). We first consider the online Beachcombers' Problem (i.e. the scenario when the robots do not know in advance the length of the segment to be searched), where the robots are initially collocated at the origin of a semi-infinite line. It is sought to design a schedule A with maximum speed S , defined as S = inf ℓ ⁡ ℓ t A (ℓ) , where t A (ℓ) denotes the time when the search of the segment [ 0 , ℓ ] is completed under A. We consider a discrete and a continuous version of the problem, depending on whether the infimum is taken over ℓ ∈ N ⁎ or ℓ ≥ 1. We prove that the LeapFrog algorithm, which was proposed in Czyzowicz et al. (2015) [12] , is in fact optimal in the discrete case. This settles in the affirmative a conjecture from that paper. We also show how to extend this result to the more general continuous online setting. For the offline version of the Beachcombers' Problem (i.e. the scenario when the robots know in advance the length of the segment to be searched), we consider the t-source Beachcombers' Problem (i.e. all robots start from a fixed number t ≥ 1 of starting positions) on the cycle and on the finite segment. For the t-source Beachcombers' Problem on the cycle, we show that the structure of the optimal solutions is identical to the structure of the optimal solutions to the 2 t -source Beachcombers' Problem on a finite segment. In consequence, by using results from Czyzowicz et al. (2014) [13] , we prove that the 1-source Beachcombers' Problem on the cycle is NP-hard, and we derive approximation algorithms for the problem. For the t-source variant of the Beachcombers' Problem on the cycle and on the finite segment, we also derive efficient approximation algorithms. One important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to change direction of movement and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in Czyzowicz et al. (2014) [13] , in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. We manage to prove that changes of direction do not help the robots achieve optimality. [ABSTRACT FROM AUTHOR]

We study open-shop scheduling for unit jobs under precedence constraints, where if one job precedes another job then it has to be finished before the other job can start to be processed. For the three-machine open-shop to minimize the makespan, we first present a simple 5/3-approximation algorithm based on a partition of the job set into agreeable layers using the natural layered representation of the precedence graph, which is directed acyclic. We then show a greedy algorithm to reduce the number of singleton-job layers, resulting in an improved partition, which leads to a 4/3-approximation algorithm. Both approximation algorithms apply to the general m -machine open-shops too. [ABSTRACT FROM AUTHOR]

Given an undirected complete graph G = (V , E) with nonnegative edge weight function obeying the triangle inequality, a set { C 1 , C 2 , ... , C k } of cycles is called a cycle cover if V ⊆ ⋃ i = 1 k V (C i) , where V (C i) represents the set of vertices in C i , and its cost is given by the maximum weight of the cycles. The Minimum Cycle Cover Problem (MCCP) aims to find a cycle cover of cost at most λ with the minimum number of cycles. We propose new LP relaxations for MCCP as well as its variants, called the Minimum Path Cover Problem (MPCP) and the Minimum Tree Cover Problem, where the cycles are replaced by paths or trees. Moreover, we give new LP relaxations for a special case of the rooted version of MCCP/MPCP. We show that these LP relaxations have significantly better integrality gaps than the previous relaxations. [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]

This paper presents a bicriteria approximation algorithm for the minimum submodular cost partial set multi-cover problem (SCPSMC), the goal of which is to find a minimum cost sub-collection of sets to fully cover q percentage of total profit of all elements, where the cost on sub-collections is a submodular function, and an element e with covering requirement r e is fully covered if it belongs to at least r e picked sets. Assuming that the maximum covering requirement r max = max e ∈ E ⁡ r e is a constant and the cost function is nonnegative and submodular, we give a deterministic (b / q ε , (1 − ε)) -bicriteria algorithm for SCPSMC, the output of which fully covers at least (1 − ε) q -percentage of the total profit and the performance ratio is b / q ε , where b = max e ⁡ ( f e r e ) and f e is the number of sets containing element e. [ABSTRACT FROM AUTHOR]

Inspired by scaffold filling, a recent approach for genome reconstruction from incomplete data, we consider a variant of the well-known longest common subsequence problem for the comparison of two sequences. The new problem, called Longest Filled Common Subsequence, aims to compare a complete sequence with an incomplete one, i.e. with some missing elements. Longest Filled Common Subsequence (LFCS), given a complete sequence A , an incomplete sequence B , and a multiset M of symbols missing in B , asks for a sequence B ⁎ obtained by inserting the symbols of M into B so that B ⁎ induces a common subsequence with A of maximum length. We investigate the computational and approximation complexity of the problem and we show that it is NP-hard and APX-hard when A contains at most two occurrences of each symbol, and we give a polynomial time algorithm when the input sequences are over a constant-size alphabet. We give a 3 5 − approximation algorithm for the Longest Filled Common Subsequence problem. Finally, we present a fixed-parameter algorithm for the problem, when it is parameterized by the number of symbols inserted in B that "match" symbols of A. [ABSTRACT FROM AUTHOR]

Given an undirected graph with edge costs, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider two network design problems under the power minimization criteria. In both problems we are given a graph G = (V , E) with edge costs and a set T ⊆ V of terminals. The goal is to find a minimum power edge subset F ⊆ E such that the graph H = (V , F) satisfies some prescribed requirements. In the Min-Power Edge-Cover problem, H should contain an edge incident to every terminal. Using the Iterative Randomized Rounding (IRR) method, we give an algorithm with expected approximation ratio 1.41; the ratio is reduced to 73 / 60 < 1.217 when T is an independent set in G. In the case of unit costs we also achieve ratio 73/60, and in addition give a simple efficient combinatorial algorithm with ratio 5/4. For all these NP-hard problems the previous best known ratio was 3/2. In the related Min-Power Terminal Backup problem, H should contain a path from every t ∈ T to some node in T ∖ { t }. We obtain ratio 3/2 for this NP-hard problem, improving the trivial ratio of 2. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new online scheduling framework for minimizing total weighted completion time in a general setting. The framework is inspired by the work of Hall et al. (1997) [11] and Garg et al. (2007) [9] , who show how to convert an offline approximation to an online scheme. Our framework uses two offline approximation algorithms—one for the simpler problem of scheduling without release times, and another for the minimum unscheduled weight problem —to create an online algorithm with provably good competitive ratios. We illustrate multiple applications of this method that yield improved competitive ratios. Our framework gives algorithms with the best or only-known competitive ratios for the concurrent open shop, coflow, and concurrent cluster models. We also introduce a randomized variant of our framework based on the ideas of Chakrabarti et al. (1996) [3] and use it to achieve improved competitive ratios for these same problems. [ABSTRACT FROM AUTHOR]

Graph burning is one model for the spread of memes and contagion in social networks. The corresponding graph parameter is the burning number of a graph G , written b (G) , which measures the speed of the social contagion. While it is conjectured that the burning number of a connected graph of order n is at most ⌈ n ⌉ , this remains open in general and in many graph families. We prove the conjectured bound for spider graphs, which are trees with exactly one vertex of degree at least 3. To prove our result for spiders, we develop new bounds on the burning number for path-forests, which in turn leads to a 3 2 -approximation algorithm for computing the burning number of path-forests. [ABSTRACT FROM AUTHOR]

• The minimum cycle cover problem. • A simplified approach of analysis. • An O (n 2) time 24/5-approximation algorithm. • A new O (n 3) time 14/3-approximation algorithm. • An improved O (n 5) time 32/7-approximation algorithm. Given an undirected weighted graph G = (V , E) with nonnegative weight function obeying the triangle inequality, a set { C 1 , C 2 , ... , C k } of cycles is called a cycle cover if V ⊆ ⋃ i = 1 k V (C i) and its cost is given by the maximum weight of the cycles. The Minimum Cycle Cover Problem aims to find a cycle cover of cost at most λ with the minimum number of cycles. An O (n 2) 24/5-approximation algorithm and an O (n 5) 14/3-approximation algorithm are given by Yu and Liu (Improved approximation algorithms for some min-max cycle cover problems. Theoretical Computer Science 654 (2016) 45–58). However, the original proofs for approximation ratios are incomplete. In this paper we first present a corrected simplified analysis on the 24/5-approximation algorithm. Based on the simplified approach of analysis and some new observations, we present a new 14/3-approximation algorithm that runs in O (n 3) and give an improved 32/7-approximation algorithm that runs in O (n 5). [ABSTRACT FROM AUTHOR]

We consider a new Steiner tree problem, called vertex-cover-weighted Steiner tree problem. This problem defines the weight of a Steiner tree as the minimum weight of vertex covers in the tree, and seeks a minimum-weight Steiner tree in a given vertex-weighted undirected graph. The problem admits an O (log ⁡ n) -approximation algorithm in general graphs with n vertices, and this approximation factor is tight up to a constant because it is NP-hard to achieve an o (log ⁡ n) -approximation for the vertex-cover-weighted Steiner tree problem in general graphs even if the given vertex weights are uniform and a spanning tree is required. In this paper, we present constant-factor approximation algorithms for the problem in unit disk graphs and in graphs excluding a fixed minor. For the latter graph class, our algorithm can be also applied for the Steiner tree activation problem. [ABSTRACT FROM AUTHOR]

Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W (1 + τ) where τ is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Ω (W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct , the slack model enables a further asymptotic improvement. The main focus of the paper is on the widely studied Basic-Summing problem of computing the sum of the last W integers from { 0 , 1 ... , R } in a stream. While it is known that Ω (W log ⁡ R) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant τ. Specifically, for τ = Θ (1) , we present a space lower bound of Ω (log ⁡ (R W)) bits. Additionally, we show an Ω (log ⁡ (W / ϵ)) lower bound for RWϵ additive approximations and a Ω (log ⁡ (W / ϵ) + log ⁡ log ⁡ R) bits lower bound for (1 + ϵ) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [17] for (1 + ϵ) -multiplicative approximation that requires O (ϵ − 1 log ⁡ (R W) log ⁡ log ⁡ (R W)) space and performs updates in O (log ⁡ (R W)) worst case time. Finally, we show asymptotic improvements for the Count-Distinct , General-Summing , and Maximum problems. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new family of graphs which is a subclass of chordal graphs as well as a superclass of interval graphs and study it. Myung [8] proposed an algorithm for the minimum clique partitioning problem with constrained bounds in weighted interval graphs. We extend the family of interval graphs to the family of so called "interval-like graphs" to which Myung's algorithm is applicable and show that bull-free chordal graphs and diamond-free chordal graphs are interval-like graphs. [ABSTRACT FROM AUTHOR]

We study the well-known two-dimensional Strip Packing problem. Given a set of rectangular axis-parallel items and a strip of width W with infinite height, the objective is to find a packing of all items into the strip, which minimizes the packing height. Lately, it has been shown that the lower bound of 3/2 of the absolute approximation ratio can be beaten when we allow a pseudo-polynomial running-time of type (n W) f (1 / ε). If W is polynomially bounded by the number of items, this is a polynomial running-time. The currently best pseudo-polynomial approximation algorithm by Nadiradze and Wiese achieves an approximation ratio of 1.4 + ε. We present a pseudo-polynomial algorithm with improved approximation ratio 4 / 3 + ε. Furthermore, the presented algorithm has a significantly smaller running-time as the 1.4 + ε approximation algorithm. [ABSTRACT FROM AUTHOR]

Motivated by applications in optical networks and job scheduling, we consider the interval coloring problem in a setting where an increasing cost is associated with using a higher color index. The cost of a coloring at any point of the line is the cost of the maximum color index used at that point, and the cost of the overall coloring is the integral of the cost over all points on the line. A coloring of minimum cost is called a minimum skyline coloring. We prove that the problem of computing a minimum skyline coloring is NP-hard and initiate the study of the online setting, where intervals arrive one by one. We give an asymptotically optimal online algorithm for the case of linear color costs and present further results for some variations and generalizations of the problem. Furthermore, we consider the variant of the minimum skyline coloring problem where the intervals are already partitioned into color classes and we only need permute the colors so as to minimize the cost of the coloring. We show that this problem variant is NP-hard and present a 2-approximation algorithm for it. [ABSTRACT FROM AUTHOR]

Given a ground set U with a non-negative weight w i for each i ∈ U , a positive integer k and a collection of sets S , which is partitioned into a family of disjoint groups G , the goal of the Maximum Coverage problem with Group budget constraints (MCG) is to select k sets from S , such that the total weight of the union of the k sets is maximized and at most one set is selected from each group G ∈ G. We first present an approximation algorithm with a factor 1 − 1 e and an exponential time via randomized linear programming rounding technique. Then we improve the time complexity of the algorithm to O ((m + n) 3.5 L + k 3.5 q 7 L) for | S | = m , | U | = n , and L being the length of the input, by the key idea of modeling the selection of groups as computing a constrained flow in a corresponding auxiliary graph. The algorithm is later shown can be extended to solve two generalizations of MCG. Last but not the least, we present another algorithm with a time complexity O ((m + n) 3.5 L + k δ 10.5 L) and a slightly increased approximation ratio 1 − e 1 δ − 1 mainly based on the idea of partition, where δ ≥ 2 is a parameter tuning which can balance the time complexity and the ratio. [ABSTRACT FROM AUTHOR]

In this paper, we study the k -forest problem in the model of resource augmentation. In the k -forest problem, given an edge-weighted graph G (V , E) , a parameter k , and a set of m demand pairs ⊆ V × V , the objective is to construct a minimum-cost subgraph that connects at least k demands. The problem is hard to approximate—the best-known approximation ratio is O (min ⁡ { | V | , k }). Furthermore, k -forest is as hard to approximate as the notoriously-hard densest k -subgraph problem. While the k -forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor. First, we restate the problem in terms of the number of demands that are not connected. In particular, the objective of the k -forest problem can be viewed as to remove at most m − k demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way. Specifically, we present a polynomial-time algorithm for the k -forest problem that, for every ε > 0 , removes at most m − k demands and has cost no more than O (1 / ε 2) times the cost of an optimal algorithm that removes at most (1 − ε) (m − k) demands. [ABSTRACT FROM AUTHOR]

We study scheduling on multiple two-stage flowshops in which each job has to pass through an R -operation and a T -operation. Motivated by the current research in data centers, we consider two restricted versions of the problem in which the jobs are inclined: one restricts that for each job, the R -operation consumes no less time than the T -operation, while the other assumes that the T -operation consumes no less time than the R -operation for each job. For the first case, we present an online 2-competitive algorithm and an offline 11/6-approximation algorithm. For the second case, we give an online 5/2-competitive algorithm, and prove, for the offline setting, that the problem can be reduced to the problem in the first case. • This paper studies the problem of scheduling two-stage jobs on m multiple two-stage flowshops to minimize the makespan, where m is part of the input. • Motivated by practical applications in data centers, we study two restricted versions of the problem where both versions are strongly NP-hard. • For the case where each job has its R -time no smaller than its T -time, we present a 2-competitive algorithm and an 11/6-approximation algorithm. • For the case where each job has its T -time no smaller than its R -time, we give a 5/2-competitive algorithm and an 11/6-approximation algorithm. • To the best of our knowledge, this paper is the first that studies the scheduling problem on m two-stage flowshops where m is part of the input. [ABSTRACT FROM AUTHOR]

Korman et al. [18] studied the following geometric covering problem: given a set S of n line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment s covers a cell f if s is incident to f. The problem was shown to be NP -hard, even if the line segments in S are axis-parallel, and it remains NP -hard when the goal is to cover the "rectangular" cells (i.e., cells that are defined by exactly four axis-parallel line segments). In this paper, we consider the approximability of the problem. We first give a PTAS for the problem when the line segments in S are in any orientation, but we can only select the covering line segments from one orientation. Then, we show that when the goal is to cover the rectangular cells using line segments from both horizontal and vertical line segments, then the problem is APX -hard. We also consider the parameterized complexity of the problem and prove that the problem is FPT when parameterized by the size of an optimal solution. Our FPT algorithm works when the line segments in S have two orientations and the goal is to cover all cells, complementing that of Korman et al. [18] in which the goal is to cover the "rectangular" cells. [ABSTRACT FROM AUTHOR]

We study the minimal decomposition of octilinear polygons with holes into octilinear triangles and rectangles. This new problem is relevant in the context of modern electronic CAD systems, where the generation and propagation of electromagnetic noise into multi-layer PCBs has to be detected. It is a generalization of a problem deeply investigated: the minimal decomposition of rectilinear polygons into rectangles. We show that the new problem is NP-hard. We also show the NP-hardness of a related problem, that is the decomposition of an octilinear polygon with holes into octilinear convex polygons. For both problems, we propose efficient approximation algorithms. [ABSTRACT FROM AUTHOR]

We study two well-known planar visibility problems, namely visibility testing and visibility counting, in a model where there is uncertainty about the input data. The standard versions of these problems are defined as follows: we are given a set S of n segments in R 2 , and we would like to preprocess S so that we can quickly answer queries of the form: is the given query segment s ∈ S visible from the given query point q ∈ R 2 (for visibility testing) and how many segments in S are visible from the given query point q ∈ R 2 (for visibility counting). In our model of uncertainty, each segment may or may not exist, and if it does, it is located in one of finitely many possible locations, given by a discrete probability distribution. In this setting, the probabilistic visibility testing problem (PVTP, for short) is to compute the probability that a given segment s ∈ S is visible from a given query point q and the probabilistic visibility counting problem (PVCP, for short) is to compute the expected number of segments in S that are visible from a query point q. We first show that PVTP is # P -complete. In the special case where uncertainty is only about whether segments exist and not about their location, we show that PVTP is solvable in O (n log ⁡ n) time. Our algorithm for PVTP combined with linearity of expectation gives an O (n 2 log ⁡ n) time algorithm for PVCP. Using the algorithm for PVTP, together with a few old tricks, we can show that one can preprocess S in O (n 5 log ⁡ n) time into a data structure of size O (n 4) , so that each PVTP query for a fixed segment s can be answered in O (log ⁡ n) time. We also give a faster 2-approximation algorithm for this problem. At the end, we improve the approximation factor of the algorithm. [ABSTRACT FROM AUTHOR]

We consider the scheduling problem on n strategic unrelated machines when no payments are allowed, under the objective of minimizing the makespan. We adopt the model introduced in [Koutsoupias 2014] where a machine is bound by her declarations in the sense that if she is assigned a particular job then she will have to execute it for an amount of time at least equal to the one she reported, even if her private, true processing capabilities are actually faster. We provide a (non-truthful) randomized algorithm whose pure Price of Anarchy is arbitrarily close to 1 for the case of a single task and close to n if it is applied independently to schedule many tasks, which is asymptotically optimal for the natural class of anonymous, task-independent algorithms. Previous work considers the constraint of truthfulness and proves a tight approximation ratio of (n + 1) / 2 for one task which generalizes to n (n + 1) / 2 for many tasks. Furthermore, we revisit the truthfulness case and reduce the latter approximation ratio for many tasks down to n , asymptotically matching the best known lower bound. This is done via a detour to the relaxed, fractional version of the problem, for which we are also able to provide an optimal approximation ratio of 1. Finally, we mention that all our algorithms achieve optimal ratios of 1 for the social welfare objective. [ABSTRACT FROM AUTHOR]

We consider the partial vertex cover problem with hard capacity constraints (Partial VC-HC) on hypergraphs. In this problem we are given a hypergraph G = (V , E) with a maximum edge size f and a covering requirement R. Each edge is associated with a demand, and each vertex is associated with a capacity and an (integral) available multiplicity. The objective is to compute a minimum vertex multiset such that at least R units of demand from the edges are covered by the capacities of the vertices in the multiset and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an f -approximation for this problem, improving over a previous result of (2 f + 2) (1 + ϵ) by Cheung et al. to the tight extent possible. Our new ingredient of this work is a generalized analysis on the extreme points of the natural LP, developed from previous works, and a strengthened LP lower-bound obtained for the optimal solutions. [ABSTRACT FROM AUTHOR]

"How many guards are required to cover an art gallery?" asked Victor Klee in 1973, initiated a deep and interesting research area in computational geometry. This problem, referred to as the Art Gallery Problem , has been considered thoroughly in the literature. A recent version of this problem, introduced by Sadhu et al. in CCCG'10, is related to the connectivity of the guards. In this version, for a given set of initial guards inside a given simple polygon, the goal is to obtain a minimum set of new guards, such that the new guards alongside the initial ones have a connected visibility graph. The visibility graph of a set of points inside a simple polygon is a graph whose vertices correspond to the point set and each edge represents the visibility between its endpoints inside the simple polygon. They showed that when the new guards are restricted to the vertices of the polygon, the problem is NP-hard, and proposed an algorithm with logarithmic approximation factor. We show that this problem is NP-Hard in all cases, where the initial guards and the new ones are restricted to vertices, boundary or all points of the polygon. Moreover, we propose constant factor approximation algorithms for all these cases. [ABSTRACT FROM AUTHOR]

A solution extension problem consists in an instance and a partial feasible solution which is given in advance and the goal is to extend this partial solution to a feasible one. Many well-known problems like Coloring Extension Problems, Traveling Salesman Problem and Routing problems, have been studied in this framework. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP -hardness, parameterized complexity, positive and negative approximation results. • An extension variant of the weighted edge cover problem is studied. • The problem is NP -complete in complete graphs while polynomial solvable in bounded tree-width graphs. • For non-negative weights, the minimization version is in-approximable at all while the maximization version is in RAPX. • If weight function satisfies (extended) c -relaxed triangle inequalities, the minimization version is in RAPX. [ABSTRACT FROM AUTHOR]

The input of the universal facility location problem includes a set of clients and a set of facilities. Our goal is to find an assignment such that each client is assigned while the total connection and facility cost is minimized. Here the connection cost is proportional to the distance between each client and its assigned facility, thus metric. The facility cost is a nondecreasing function with respect to the total number of clients assigned to the facility. The universal facility location problem is NP-hard since it generalizes several classical facility location problems. Our work considers the universal facility location problem with linear penalties, a generalized version of the universal facility location problem. Here each client can be rejected for service with certain penalty cost. Thus we have to consider penalty cost other than total connection and facility cost in our objective function. Based on local search method, we present a (5.83 + ϵ) -approximation algorithm for this problem. [ABSTRACT FROM AUTHOR]

We study a graph class called conflict graph , which is a union of a finite number of given forests of complete multipartite graph. It is interesting that conflict graph can model many natural problems, such as in database application and others. We show that this property is non-trivial if limiting the number of forests of complete multipartite graph. Then study the problem of vertex cover on conflict graph in this paper. The results list as follows, if the number of forests of complete multipartite graph is fixed, conflict graph is non-trivial property, but finding 1.36-approximation algorithms is NP- hard. Also given 2 forests of complete multipartite graph and maximum degree less than 7, vertex cover problem of conflict graph is NP- complete. Moreover, it is shown to be NP- hard to find an algorithm for vertex cover of conflict graph within 41 40 − ε , for any ε > 0 , if there is no the degree restriction over the graph. At last, we design an approximation algorithm for the conflict graph consisting of r forests of complete multipartite graph and show that the approximation ratio can be bounded by 2 − 1 2 r and it's near optimal. [ABSTRACT FROM AUTHOR]

We formulate and study a fundamental search and detection problem, Schedule Optimization , motivated by a variety of real-world applications, ranging from monitoring content changes on the web, social networks, and user activities to detecting failure on large systems with many individual machines. We consider a large system consists of many nodes, where each node has its own rate of generating new events, or items. A monitoring application can probe a small number of nodes at each step, and our goal is to compute a probing schedule that minimizes the expected number of undiscovered items at the system, or equivalently, minimizes the expected time to discover a new item in the system. We study the Schedule Optimization problem both for deterministic and randomized memoryless algorithms. We provide lower bounds on the cost of an optimal schedule and construct close to optimal schedules with rigorous mathematical guarantees. [ABSTRACT FROM AUTHOR]

We present two results on slime mold computations. In wet-lab experiments by Nakagaki et al. (2000) [1] the slime mold Physarum polycephalum demonstrated its ability to solve shortest path problems. Biologists proposed a mathematical model, a system of differential equations, for the slime's adaption process (Tero et al., 2007) [3]. It was shown that the process convergences to the shortest path (Bonifaci et al., 2012) [5] for all graphs. We show that the dynamics actually converges for a much wider class of problems, namely undirected linear programs with a non-negative cost vector. Combinatorial optimization researchers took the dynamics describing slime behavior as an inspiration for an optimization method and showed that its discretization can ε -approximately solve linear programs with positive cost vector (Straszak and Vishnoi, 2016) [14]. Their analysis requires a feasible starting point, a step size depending linearly on ε , and a number of steps with quartic dependence on opt / (ε Φ) , where Φ is the difference between the smallest cost of a non-optimal basic feasible solution and the optimal cost (opt). We give a refined analysis showing that the dynamics initialized with any strongly dominating point converges to the set of optimal solutions. Moreover, we strengthen the convergence rate bounds and prove that the step size is independent of ε , and the number of steps depends logarithmically on 1 / ε and quadratically on opt / Φ. [ABSTRACT FROM AUTHOR]