Search

In the 70 s, Berge introduced 1-extendable graphs (also called B-graphs), which are graphs where every vertex belongs to a maximum independent set. Motivated by an application in the design of wireless networks, we study the computational complexity of 1-extendability, the problem of deciding whether a graph is 1-extendable. We show that, in general, 1-extendability cannot be solved in 2 o (n) time assuming the Exponential Time Hypothesis, where n is the number of vertices of the input graph, and that it remains NP-hard in subcubic planar graphs and in unit disk graphs (which is a natural model for wireless networks). Although 1-extendability seems to be very close to the problem of finding an independent set of maximum size (a.k.a.Maximum Independent Set), we show that, interestingly, there exist 1-extendable graphs for which Maximum Independent Set is NP-hard. Finally, we investigate a parameterized version of 1-extendability. [ABSTRACT FROM AUTHOR]

We study algorithmic Bayesian persuasion problems in which the principal (a.k.a. the sender) has to persuade multiple agents (a.k.a. receivers) by using public communication channels. Specifically, our model follows the multi-receiver model with no inter-agent externalities introduced by Arieli and Babichenko (J Econ Theory 182:185–217, 2019). It is known that the problem of computing a sender-optimal public persuasive signaling scheme is not approximable even in simple settings. Therefore, prior works usually focus on determining restricted classes of the problem for which efficient approximation is possible. Typically, positive results in this space amounts to finding bi-criteria approximation algorithms yielding an almost optimal and almost persuasive solution in polynomial time. In this paper, we take a different perspective and study the persuasion problem in the general setting where the space of the states of nature, the action space of the receivers, and the utility function of the sender can be arbitrary. We fully characterize the computational complexity of computing a bi-criteria approximation of an optimal public signaling scheme in such settings. In particular, we show that, assuming the Exponential Time Hypothesis, solving this problem requires at least a quasi-polynomial number of steps even in instances with simple utility functions and binary action spaces such as an election with the k-voting rule. In doing so, we prove that a relaxed version of the Maximum Feasible Subsystem of Linear Inequalities problem requires at least quasi-polynomial time to be solved. Finally, we close the gap by providing a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, under mild assumptions, yields a QPTAS. [ABSTRACT FROM AUTHOR]

We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min–avg minimizes the average tour cost and min–max minimizes the maximum tour cost over all days. For min–max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min–avg we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open. [ABSTRACT FROM AUTHOR]

The minimum hitting set of bundles problem (Mhsb) is a natural generalization of the minimum hitting set problem, where instead of hitting single elements, bundles of elements are hit. More specifically, we are given a ground set of elements and a family of sets. Every set in this family contains bundles of elements, which are subsets of the ground set. The task is to find a collection of elements of minimum size such that at least one bundle of every set in the family is hit. Motivated by several applications, we consider Mhsb restricted to interval and 2-dimensional interval bundles. We study the computational complexity and give polynomial-time algorithms for several classes of instances with these special structured bundles. [ABSTRACT FROM AUTHOR]

Scaffolding is the final step in assembling Next Generation Sequencing data, in which pre-assembled contiguous regions ("contigs") are oriented and ordered using information that links them (for example, mapping of paired-end reads). As the genome of some species is highly repetitive, we allow placing some contigs multiple times, thereby generalizing established computational models for this problem. We study the subsequent problems induced by the translation of solutions of the model back to actual sequences, proposing models and analyzing the complexity of the resulting computational problems. We find both polynomial-time and NP -hard special cases like planarity or bounded degree. Finally, we propose two polynomial-time approximation algorithms according to cut/weight score. [ABSTRACT FROM AUTHOR]

We introduce a variant of the well-known minimum-cost circulation problem in directed networks, where vertex demand values are taken from the integers modulo λ , for some integer λ ≥ 2 . More formally, given a directed network G = (V , E) , each of whose edges is associated with a weight and each of whose vertices is associated with a demand taken over the integers modulo λ , the objective is to compute a flow of minimum weight that satisfies all the vertex demands modulo λ . This problem is motivated by a problem of computing a periodic schedule for traffic lights in an urban transportation network that minimizes the total delay time of vehicles. We show that this modular circulation problem is solvable in polynomial time when λ = 2 and that the problem is NP-hard when λ = 3 . We also present a polynomial time algorithm that achieves a 4 (λ - 1) -approximation. [ABSTRACT FROM AUTHOR]

We study classical deadline-based preemptive scheduling of jobs in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each job is specified by a release time, a deadline and a processing volume, and has to be scheduled on a single, speed-scalable processor that is supplied with a sleep state. In the sleep state, the processor consumes no energy, but a constant wake-up cost is required to transition back to the active state. In contrast to speed scaling alone, the addition of a sleep state makes it sometimes beneficial to accelerate the processing of jobs in order to transition the processor to the sleep state for longer amounts of time and incur further energy savings. The goal is to output a feasible schedule that minimizes the energy consumption. Since the introduction of the problem by Irani et al. (ACM Trans Algorithms 3(4), 2007), its exact computational complexity has been repeatedly posed as an open question (see e.g. Albers and Antoniadis in ACM Trans Algorithms 10(2):9, 2014; Baptiste et al. in ACM Trans Algorithms 8(3):26, 2012; Irani and Pruhs in SIGACT News 36(2):63–76, 2005). The currently best known upper and lower bounds are a 4 / 3-approximation algorithm and NP-hardness due to Albers and Antoniadis (2014) and Kumar and Shannigrahi (CoRR, 2013. arXiv:1304.7373), respectively. We close the aforementioned gap between the upper and lower bound on the computational complexity of speed scaling with sleep state by presenting a fully polynomial-time approximation scheme for the problem. The scheme is based on a transformation to a non-preemptive variant of the problem, and a discretization that exploits a carefully defined lexicographical ordering among schedules. [ABSTRACT FROM AUTHOR]

We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense. [ABSTRACT FROM AUTHOR]

We study the problem of assigning transmission ranges to radio stations in the plane such that any pair of stations can communicate within a bounded number of hops h and the cost of the network is minimized. We consider two settings of the problem: collinear station locations and arbitrary locations. For the case of collinear stations, we introduce the pioneer polynomial-time exact algorithm for any α≥1 and constant h, and thus conclude that the 1D version of the problem, where h is a constant, is in P. Furthermore, we provide a 3 / 2-approximation algorithm for the case where h is an arbitrary number and α=1, improving the previously best known approximation ratio of 2. For the case of stations placed arbitrarily in the plane and α=1, we first present a (1.5+ε)-approximation algorithm for a case where a deviation of one hop (h+1 hops in total) is acceptable. Then, we show a (3+ε)-approximation algorithm that complies with the exact hop bound. To achieve that, we introduce the following two auxiliary problems, which are of independent interest. The first is the bounded-hop multi-sink range problem, for which we present a PTAS which can be applied to compute a (1+ε)-approximation for the bounded diameter minimum spanning tree, for any ε>0. The second auxiliary problem is the bounded-hop dual-sink pruning problem, for which we show a polynomial-time algorithm. To conclude, we consider the initial bounded-hop all-to-all range assignment problem and show that a combined application of the aforementioned problems yields the (3+ε)-approximation ratio for this problem, which improves the previously best known approximation ratio of 4(9h-2)/(2h-1). [ABSTRACT FROM AUTHOR]

Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios, however, the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality k without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to k. Further, we derive some polynomial-time solvable cases for k=2 with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of k. [ABSTRACT FROM AUTHOR]

In Part I, we study a special case of the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum of Squares) system. In the special case, we forbid so-called stems; these are a particular type of subtree configuration. For stemless TAP, we prove that the integrality ratio of an SDP relaxation (the Lasserre tightening of an LP relaxation) is ≤32+ϵ, where ϵ>0 can be any small constant. We obtain this result by designing a polynomial-time algorithm for stemless TAP that achieves an approximation guarantee of 32+ϵ relative to the SDP relaxation. The algorithm is combinatorial and does not solve the SDP relaxation, but our analysis relies on the SDP relaxation. We generalize the combinatorial analysis of integral solutions from the previous literature to fractional solutions by identifying some properties of fractional solutions of the Lasserre system via the decomposition result of Karlin et al. (Integer programming and combinatoral optimization (IPCO), Lecture Notes in Computer Science, vol 6655. Springer, Berlin/Heidelberg, pp 301–314, 2011). Also, we present an example of stemless TAP such that the approximation guarantee of 32 is tight for the algorithm. In Part II of this paper, we extend the methods of Part I to prove the same results relative to the same SDP relaxation for TAP. [ABSTRACT FROM AUTHOR]

Let $$P$$ and $$Q$$ be two simple polygons in the plane of total complexity n, each of which can be decomposed into at most k convex parts. We present a $$(1-\varepsilon )$$ -approximation algorithm, for finding the translation of $$Q$$ , which maximizes its area of overlap with $$P$$ . Our algorithm runs in $$O\left( {c n}\right) $$ time, where c is a constant that depends only on k and $$\varepsilon $$ . This suggests that for polygons that are 'close' to being convex, the problem can be solved (approximately), in near linear time. [ABSTRACT FROM AUTHOR]

We consider a local service-requirement assignment problem named capacitated domination from an algorithmic point of view. In this problem, we are given a graph with three parameters defined on each vertex, which are the cost, the capacity, and the demand, of a vertex, respectively. A vertex can be chosen multiple times in order to generate sufficient capacity for the demands of the vertices in its closed neighborhood. The objective of this problem is to compute a demand assignment of minimum cost such that the demand of each vertex is fully-served by some of its closed neighbors without exceeding the amount of capacity they provide. In this paper, we provide complexity results as well as several approximation algorithms to compose a comprehensive study for this problem. First, we provide logarithmic approximations for general graphs which are asymptotically optimal. From the perspective of parameterized complexity, we show that this problem is W[1]-hard with respect to treewidth and solution size. Moreover, we show that this problem is fixed-parameter tractable with respect to treewidth and the maximum capacity of the vertices. The latter result implies a pseudo-polynomial time approximation scheme for planar graphs under a standard framework. In order to drop the pseudo-polynomial factor, we develop a constant-factor approximation for planar graphs, based on a new perspective which we call general ladders on the hierarchical structure of outer-planar graphs. We believe that the approach we use can be applicable to other capacitated covering problems. [ABSTRACT FROM AUTHOR]

Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithm design. While each of them being very active in its own, there is an increasing attention to the connection between these different frameworks. In particular, whether Independent Set would be better approximable once endowed with subexponential-time or FPT-time is a central question. In this article, we provide new insights to this question using two complementary approaches; the former makes a strong link between the linear PCP conjecture and inapproximability; the latter builds a class of equivalent problems under approximation in subexponential time. [ABSTRACT FROM AUTHOR]

In a communication network one often needs to combine several communication requests into a path in a physical layer of the network. In these cases the cost is measured in terms of the total length of these paths or the total hardware cost of maintaining these paths. In this paper we consider a problem belonging to this general family of optimization problems. We consider the problem of minimizing the number of regenerators in optical networks with traffic grooming. In this problem we are given a network with an underlying topology of a graph G, a set of requests that correspond to paths in G and two positive integers g and d. There is a need to put a regenerator every d edges of every path, because of a degradation in the quality of the signal. Each regenerator can be shared by at most g paths, g being the grooming factor. On the one hand, we show that even in the case of d=1 the problem is APX- hard, i.e. a polynomial time approximation scheme for it does not exist (unless P=NP). On the other hand, we solve such a problem for general G and any d and g, by providing an O(log g)-approximation algorithm and thus extending previous results holding only for specific topologies and specific values of d or g. [ABSTRACT FROM AUTHOR]

We show that vertex guarding a monotone polygon is NP-hard and construct a constant factor approximation algorithm for interior guarding monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is OPT for a rectilinear polygon, our algorithm produces a guard set of size O( OPT). [ABSTRACT FROM AUTHOR]

We consider devices equipped with multiple wired or wireless interfaces. By switching of various interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider two basic networking problems in the field of multi-interface networks. The first one, known as the Coverage problem, requires to establish the connections defined by a network. The second one, known as Connectivity problem, requires to guarantee a connecting path between any pair of nodes of a network. Both are subject to the constraint of keeping as low as possible the maximum cost set of active interfaces at each single node. We study the problems of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges in the first case, or to ensure connectivity in the second case. We prove that the Coverage problem is NP-hard for any fixed Δ≥5 and k≥16, with Δ being the maximum degree, and k being the number of different interfaces among the network. We also show that, unless P= NP, the problem cannot be approximated within a factor of ηln Δ, for a certain constant η. We then provide a general approximation algorithm which guarantees a factor of O((1+ b)ln Δ), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented. Concerning the Connectivity problem, we prove that it is NP-hard for any fixed Δ≥3 and k≥10. Also for this problem, the inapproximability result holds, that is, unless P= NP, the problem cannot be approximated within a factor of ηln Δ, for a certain constant η. We then provide approximation and exact algorithms for the general problem and for special cases, respectively. [ABSTRACT FROM AUTHOR]

Given a range space $(X,\mathcal{R})$, where $\mathcal{R}\subset2^{X}$, the hitting set problem is to find a smallest-cardinality subset H⊆ X that intersects each set in $\mathcal{R}$. We present near-linear-time approximation algorithms for the hitting set problem in the following geometric settings: (i) $\mathcal{R}$ is a set of planar regions with small union complexity. (ii) $\mathcal{R}$ is a set of axis-parallel d-dimensional boxes in ℝ. In both cases X is either the entire ℝ, or a finite set of points in ℝ. The approximation factors yielded by the algorithm are small; they are either the same as, or within very small factors off the best factors known to be computable in polynomial time. [ABSTRACT FROM AUTHOR]

We are given a trajectory $\mathcal{T}$ and an area $\mathcal{A}$ . $\mathcal{T}$ might intersect $\mathcal{A}$ several times, and our aim is to detect whether $\mathcal{T}$ visits $\mathcal{A}$ with some regularity, e.g. what is the longest time span that a GPS-GSM equipped elephant visited a specific lake on a daily (weekly or yearly) basis, where the elephant has to visit the lake most of the days (weeks or years), but not necessarily on every day (week or year). During the modelling of such applications, we encountered an elementary problem on bitstrings, that we call LDS (LongestDenseSubstring). The bits of the bitstring correspond to a sequence of regular time points, in which a bit is set to 1 if and only if the trajectory $\mathcal {T}$ intersects the area $\mathcal{A}$ at the corresponding time point. For the LDS problem, we are given a string s as input and want to output a longest substring of s, such that the ratio of 1's in the substring is at least a certain threshold. In our model, LDS is a core problem for many applications that aim at detecting regularity of $\mathcal{T}$ intersecting $\mathcal{A}$ . We propose an optimal algorithm to solve LDS, and also for related problems that are closer to applications, we provide efficient algorithms for detecting regularity. [ABSTRACT FROM AUTHOR]

We study the problem of non-preemptively scheduling n independent sequential jobs on a system of m identical parallel machines in the presence of reservations, where m is constant. This setting is practically relevant because for various reasons, some machines may not be available during specified time intervals. The objective is to minimize the makespan Cmax, which is the maximum completion time. The general case of the problem is inapproximable unless $\mathsf {P}=\mathsf {NP}$ ; hence, we study a suitable strongly $\mathsf {NP}$ -hard restriction, namely the case where at least one machine is always available. For this setting we contribute approximation schemes, complemented by inapproximability results. The approach is based on algorithms for multiple subset sum problems; our technique yields a PTAS which is best possible in the sense that an FPTAS is ruled out unless $\mathsf {P}=\mathsf {NP}$ . The PTAS presented here is the first one for the problem under consideration; so far, not even for well-known special cases approximation schemes have been proposed. Furthermore we derive a low cost algorithm with a constant approximation ratio and discuss FPTASes for special cases as well as the complexity of the problem if m is part of the input. [ABSTRACT FROM AUTHOR]

We study bottleneck labeled optimization problems arising in the context of graph theory. This long-established model partitions the set of edges into classes, each of which is identified by a unique color. The generic objective is to construct a subgraph of prescribed structure (such as an s- t path, a spanning tree, or a perfect matching) while trying to minimize the maximum (or, alternatively, maximize the minimum) number of edges picked from any given color. [ABSTRACT FROM AUTHOR]