Search

We study the computational complexity of (deterministic or randomized) algorithms based on point samples for approximating or integrating functions that can be well approximated by neural networks. Such algorithms (most prominently stochastic gradient descent and its variants) are used extensively in the field of deep learning. One of the most important problems in this field concerns the question of whether it is possible to realize theoretically provable neural network approximation rates by such algorithms. We answer this question in the negative by proving hardness results for the problems of approximation and integration on a novel class of neural network approximation spaces. In particular, our results confirm a conjectured and empirically observed theory-to-practice gap in deep learning. We complement our hardness results by showing that error bounds of a comparable order of convergence are (at least theoretically) achievable. [ABSTRACT FROM AUTHOR]

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]

This paper constructs an interval partition linearization algorithm for solving minimax linear fractional programming (MLFP) problem. In this algorithm, MLFP is converted and decomposed into a series of linear programs by dividing the outer 1-dimensional space of the equivalent problem (EP) into polynomially countable intervals. To improve the computational efficiency of the algorithm, two new acceleration techniques are introduced, in which the regions in outer space where the optimal solution of EP does not exist are largely deleted. In addition, the global convergence of the proposed algorithm is summarized, and its computational complexity is illustrated to reveal that it is a fully polynomial time approximation scheme. Finally, the numerical results demonstrate that the proposed algorithm is feasible and effective. [ABSTRACT FROM AUTHOR]

We study several two-machine shop scheduling problems, namely flow shop, job shop and open shop scheduling problems under linear constraints. In these problems, the processing times of two stages of jobs are also decision variables and satisfy a system of linear constraints. The goal of each problem is to determine the processing time of each job, and to schedule the jobs to the shop machine such that the makespan, i.e., the completion time of all jobs, is minimized. These problems can find application in various areas, such as industrial production, advertising and automotive maintenance. We study the computational complexity and propose polynomial-time optimal or approximation algorithms for them. In particular, we show that although a two-machine flow shop scheduling problem and a two-machine job shop scheduling problem without recirculation can be solved in polynomial time, the problems where processing times satisfy linear constraints are generally NP-hard in the strong sense. Then, we design algorithms for various settings of these problems. We design polynomial-time algorithms for them when there are a fixed number of constraints. For the general case, we first propose a simple 2-approximation algorithm, and then design a polynomial-time approximation schemes. In contrast to the previous two problems, we show that the two-machine open shop scheduling problem under linear constraints can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of computational complexity. Notice that every n-vertex sum graph can be represented by a sorted list of n positive integers where edge queries can be answered in O (log n) time. Therefore, upper-bounding the numbers used as vertex labels also upper-bounds the space complexity of storing the graph in the database. We show that every n-vertex, m-edge, d-degenerate graph can be made a sum graph by adding at most m isolated vertices to it, such that the largest numbers used as vertex labels grows as O (n 2 d) . This enables us to store the graph using O (m log n) bits of memory. For sparse graphs (graphs with O (n) edges), this matches the trivial lower bound of Ω (n log n) . As planar graphs and forests have constant degeneracy, our result implies an upper bound of O (n 2) on their label numbers. The previously best known upper bound on the numbers needed for labelling general graphs with the minimum number of isolated vertices was O (4 n) , due to Kratochvíl, Miller & Nguyen (2001). Furthermore, their proof was existential, whereas our labelling can be constructed in polynomial time. [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 consider a two-machine flow shop scheduling problem in which the processing time of each operation is inversely proportional to the power of the amount of resources consumed by it. The objective is to minimize the sum of the makespan and the total resource consumption cost. We show that the problem is NP-hard, and its constrained version remains so. Then, we develop 1.25- and 2-approximation algorithms for the problem and its constrained version, respectively. [ABSTRACT FROM AUTHOR]

Gaussian processes (GPs) are popular models for functions, time series, and spatial fields, but direct application of GPs is computationally infeasible for large datasets. We propose a multi-scale Vecchia (MSV) approximation of GPs for modeling and analysis of multi-scale phenomena, which are ubiquitous in geophysical and other applications. In the MSV approach, increasingly large sets of variables capture increasingly small scales of spatial variation, to obtain an accurate approximation of the spatial dependence from very large to very fine scales. For a given set of observations, the MSV approach decomposes the data into different scales, which can be visualized to obtain insights into the underlying processes. We explore properties of the MSV approximation and propose an algorithm for automatic choice of the tuning parameters. We provide comparisons to existing approaches based on simulated data and using satellite measurements of land-surface temperature. [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]

Sparse tensor best rank-1 approximation (BR1Approx), which is a sparsity generalization of the dense tensor BR1Approx, and is a higher-order extension of the sparse matrix BR1Approx, is one of the most important problems in sparse tensor decomposition and related problems arising from statistics and machine learning. By exploiting the multilinearity as well as the sparsity structure of the problem, four polynomial-time approximation algorithms are proposed, which are easily implemented, of low computational complexity, and can serve as initial procedures for iterative algorithms. In addition, theoretically guaranteed approximation lower bounds are derived for all the algorithms. We provide numerical experiments on synthetic and real data to illustrate the efficiency and effectiveness of the proposed algorithms; in particular, serving as initialization procedures, the approximation algorithms can help in improving the solution quality of iterative algorithms while reducing the computational time. [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]

Classical Rough Set Theory (RST) is a prominent tool to deal with uncertainty of categorical data. However, in a case where values of attributes maintain preference order over each other, RST does not consider it. Dominance-based Rough Set Approach (DRSA), a generalization of RST, studies the dominance aspect of attributes and defines the dominance relation. The lower and upper approximations form the basis of most algorithms based on RST. However, determining DRSA approximations is computationally expensive so that the algorithms using approximations may suffer serious performance bottleneck when dealing with datasets of larger sizes. In this paper, we proposed a heuristic approach to compute lower and upper approximations based on DRSA, in time efficient manner. The proposed algorithm directly calculates approximations without going through the heavy computations of dominance positive or negative cones. We introduce heuristic rules to calculate approximations without considering the intersection and subset relations. By using the properties and logical structure of approximations, our mathematical implications select an object for all relevant approximation sets. The proposed approach was compared with the conventional method using eleven benchmark datasets from UCI. The results showed that the proposed rules significantly reduce the execution time by avoiding the redundant computations, which ultimately affect the structural complexity and memory requirements. The average reduction in execution time was found to be 83%. The proposed approach also reduces the structural complexity and memory consumption by 89.69%. [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 study a single-machine lot-sizing problem, where n types of products need to be scheduled on the machine. Each product is associated with a constant demand rate, maximum production rate and inventory costs per time unit. Every time when the machine switches production between products, sequencing costs are incurred. These sequencing costs depend both on the product the machine just produced and on the product the machine is about to produce. The goal is to find a cyclic schedule minimizing total average costs, subject to the condition that all demands are satisfied. We establish the complexity of the problem, and we prove a number of structural properties largely characterizing optimal solutions. Moreover, we present two algorithms approximating the optimal schedules by augmenting the problem input. Due to the high-multiplicity setting, even trivial cases of the corresponding conventional counterparts become highly non-trivial with respect to the output sizes and computational complexity, even without sequencing costs. In particular, the length of an optimal solution can be exponential in the input size of the problem. Nevertheless, our approximation algorithms produce schedules of a polynomial length and with a good quality compared to the optimal schedules of exponential length. [ABSTRACT FROM AUTHOR]

The transportation problem is a fundamental problem in operations research, where items need to be transported from supply nodes (each with a given supply) to demand nodes (each with a given demand) in the cheapest possible way. Here, we are interested in a generalization of the transportation problem where, each supply node has a (possibly empty) set of conflicting pairs of demand nodes, and each demand node a (possibly empty) set of conflicting pairs of supply nodes. Each supply node may only send supply to at most one demand node of each conflicting pair. Likewise, each demand node may only receive supply from at most one supply node of each conflicting pair. We call the resulting problem the transportation problem with conflicts (TPC). We show that the complexity of TPC depends upon the structure of the so-called conflict graph that follows from the conflicting pairs. More concrete, we show that for many graph-classes the corresponding TPC remains NP-hard, and for some special cases we derive constant factor approximation algorithms. [ABSTRACT FROM AUTHOR]

The problem of attaining energy efficiency in distributed systems is of importance, but a general, non-domain-specific theory of energy-minimal scheduling is far from developed. In this paper, we classify the problems of energy-minimal scheduling and present theoretical foundations of the same. We derive results concerning energy-minimal scheduling of independent jobs in a distributed system with functionally similar machines with different working and idle power ratings. The machines considered in our system can have identical as well as different speeds. If the jobs can be divided into arbitrary parts, we show that the minimum-energy schedule can be generated in linear time and give exact scheduling algorithms. For the cases where jobs are non-divisible, we prove that the scheduling problems are NP-hard and also give approximation algorithms for the same along with their bounds. [ABSTRACT FROM AUTHOR]

A central problem in graph mining is finding dense subgraphs, with several applications in different fields, a notable example being identifying communities. While a lot of effort has been put in the problem of finding a single dense subgraph, only recently the focus has been shifted to the problem of finding a set of densest subgraphs. An approach introduced to find possible overlapping subgraphs is the Top-k-Overlapping Densest Subgraphs problem. Given an integer k ≥ 1 and a parameter λ > 0 , the goal of this problem is to find a set of k dense subgraphs that may share some vertices. The objective function to be maximized takes into account the density of the subgraphs, the parameter λ and the distance between each pair of subgraphs in the solution. The Top-k-Overlapping Densest Subgraphs problem has been shown to admit a 1 10 -factor approximation algorithm. Furthermore, the computational complexity of the problem has been left open. In this paper, we present contributions concerning the approximability and the computational complexity of the problem. For the approximability, we present approximation algorithms that improve the approximation factor to 1 2 , when k is smaller than the number of vertices in the graph, and to 2 3 , when k is a constant. For the computational complexity, we show that the problem is NP-hard even when k = 3 . [ABSTRACT FROM AUTHOR]

We introduce the Chinese deliveryman problem where the goal of the deliveryman is to visit every house in his neighborhood such that the average time of arrival is minimized. We show that, in contrast to the well-known Chinese postman problem, the Chinese deliveryman problem is APX-hard in general and NP-hard for planar graphs. We give a simple 2 -approximation for undirected graphs and a 4 / 3-approximation for 2-edge connected graphs. We observe that there is a PTAS for planar graphs and that depth first search is optimal for trees. [ABSTRACT FROM AUTHOR]

Aiming at the dynamic uncertainty and prediction accuracy of security situation prediction in complex cloud network environment, a prediction model of cloud security situation based on evolutionary functional network is proposed. Firstly, the evolutionary functional network model is constructed by combining the evolutionary algorithm with the functional network, which solves the problem of basis function selection and basis function coefficient correction of the prediction model. Secondly, the stochastic approximation algorithm is used to process and comprehend the cloud security situation elements, and the computational complexity of the prediction model is reduced by the dimensionality reduction method. Finally, by constructing the credibility matrix of the uncertain influence relationship of security situation elements, we use the multivariate non-linear regression algorithm to predict the cloud security situation. The simulation results show that compared with BP model and RAN-RBF model, the prediction accuracy of the proposed model is improved by 8.2% and 6.9% respectively, and the convergence efficiency is improved by 12.3% and 10.8% respectively. [ABSTRACT FROM AUTHOR]

Kriging or Gaussian Process Regression is applied in many fields as a non-linear regression model as well as a surrogate model in the field of evolutionary computation. However, the computational and space complexity of Kriging, that is cubic and quadratic in the number of data points respectively, becomes a major bottleneck with more and more data available nowadays. In this paper, we propose a general methodology for the complexity reduction, called cluster Kriging, where the whole data set is partitioned into smaller clusters and multiple Kriging models are built on top of them. In addition, four Kriging approximation algorithms are proposed as candidate algorithms within the new framework. Each of these algorithms can be applied to much larger data sets while maintaining the advantages and power of Kriging. The proposed algorithms are explained in detail and compared empirically against a broad set of existing state-of-the-art Kriging approximation methods on a well-defined testing framework. According to the empirical study, the proposed algorithms consistently outperform the existing algorithms. Moreover, some practical suggestions are provided for using the proposed algorithms. [ABSTRACT FROM AUTHOR]

We study Parallel Task Scheduling Pm|sizej|Cmax with a constant number of machines. This problem is known to be strongly NP-complete for each m ≥ 5, while it is solvable in pseudo-polynomial time for each m ≤ 3. We give a positive answer to the long-standing open question whether this problem is strongly NP-complete for m = 4. As a second result, we improve the lower bound of 12 11 for approximating pseudo-polynomial Strip Packing to 5 4 . Since the best known approximation algorithm for this problem has a ratio of 5 4 + ε , this result almost closes the gap between approximation ratio and inapproximability result. Both results are proved by a reduction from the strongly NP-complete problem 3-Partition. [ABSTRACT FROM AUTHOR]

Self-reconfigurable modular robots (SRM-robots) can autonomously change their shape according to different tasks and work environments, and have received considerable attention recently. Many reshaping/reconfiguration algorithms have been proposed. In this paper, we present a theoretical analysis of computational complexity on a reshape planning for a kind of lattice-type 3D SRM-robots, whose modules are of cubic shape and can move by rotating on the surfaces of other modules. Different from previous NP-completeness study on general chain-type robots (i.e. the motion of any chains and the location of modules can be arbitrary), we consider more practical constraints on modules' shape (i.e. cubic shape), position (lying in 2D/3D grids) and motion (using orthogonal rotations) in this paper. We formulate the reshape planning problem of SRM-robots with these practical constraints by a (p, q) optimization problem, where p and q characterize two widely used metrics, i.e. the number of disconnecting/reconnecting operations and the number of reshaping steps. Proofs are presented, showing that this optimization problem is NP-complete. Therefore, instead of finding global optimization results, most likely approximation solution can be obtained for the problem instead of seeking polynomial algorithm. We also present the upper and lower bounds for the 2-tuple (p, q), which is useful for evaluating the approximation algorithms in future research. [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]

In this paper, a class of single machine scheduling problems is considered. It is assumed that job processing times and due dates can be uncertain and they are specified in the form of discrete scenario set. A probability distribution in the scenario set is known. In order to choose a schedule, some risk criteria such as the value at risk and conditional value at risk are used. Various positive and negative complexity results are provided for basic single machine scheduling problems. In this paper, new complexity results are shown and some known complexity results are strengthened. [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]

In this paper, we study unbounded parallel-batch scheduling with drop-line tasks to minimize a regular objective function, where by "drop-line tasks" we mean that the completion time of each task (job) is equal to the sum of the starting time of the batch containing the task and the processing time of the task. In the problems considered in this paper, we assume that the tasks have individual release dates and the general regular objective function to be minimized is either of the sum-form or of the max-form. We then study the computational complexity of these problems on an unbounded parallel-batch processor. We show that (i) the problems are binary NP-hard and are solvable in pseudo-polynomial times, and (ii) when the number of processing times or release dates is a constant, the problems are solvable in polynomial times. We also point out some consequences of approximation algorithms. [ABSTRACT FROM AUTHOR]

We study two variants of the Balanced Tree Partition (BTP for short) problem, whose goal is to find the minimum number of edges such that a partition of vertices into sets of equal size can be obtained after deleting those edges. We consider the BTP problem over trees with virtual nodes, which is motivated by the real applications in storing tree structured data distributively. Different from the traditional BTP problem, after deleting an edge from the tree, two virtual nodes must be added to provide the ability to recover the edge when computing, which will increase the size of some set in the partition and the set may become too large and need further splitting. Depending on whether or not to consider the partition set number k to be a parameter, to investigate the balanced tree partition methods over trees with virtual nodes, we formally defined two specific problems, k -VBTP and VBTP. The computational complexity and inapproximability of k -VBTP are analyzed, for the VBTP problem, a polynomial time algorithm is designed to find the optimal solution based on dynamic programming. Finally, the connections between k -VBTP and VBTP are built, and based the algorithm for VBTP, we design a heuristic algorithm for k -VBTP with performance guarantee. [ABSTRACT FROM AUTHOR]

We study the complexity of motivating time-inconsistent agents to complete long term projects in a graph-based planning model proposed by Kleinberg and Oren (2014). Given a task graph G with n nodes, our objective is to guide an agent towards a target node t under certain budget constraints. The crux is that the agent may change its strategy over time due to its present-bias. We consider two strategies to guide the agent. First, a single reward is placed at t and arbitrary edges can be removed from G. Secondly, rewards can be placed at arbitrary nodes of G but no edges must be deleted. In both cases we show that it is NP-complete to decide if a given budget is sufficient to keep the agent motivated. For the first setting, we give complementing upper and lower bounds on the approximability of the minimum required budget. In particular, we devise a (1 + n) -approximation algorithm and prove NP-hardness for ratios greater than n / 3 . We also argue that the second setting does not permit any efficient approximation unless P = NP. [ABSTRACT FROM AUTHOR]

We investigate the problem of equilibrium computation for "large" n-player games. Large games have a Lipschitz-type property that no single player's utility is greatly affected by any other individual player's actions. In this paper, we mostly focus on the case where any change of strategy by a player causes other players' payoffs to change by at most 1n. We study algorithms having query access to the game's payoff function, aiming to find ε-Nash equilibria. We seek algorithms that obtain ε as small as possible, in time polynomial in n. Our main result is a randomised algorithm that achieves ε approaching 18 for 2-strategy games in a completely uncoupled setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players' payoffs/actions. O(log n) rounds/queries are required. We also show how to obtain a slight improvement over 18, by introducing a small amount of communication between the players. Finally, we give extension of our results to large games with more than two strategies per player, and alternative largeness parameters. [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]

In retail, assortment planning refers to selecting a subset of products to offer that maximizes profit. Assortments can be planned for a single store or a retailer with multiple chain stores where demand varies between stores. In this paper, we assume that a retailer with a multitude of stores wants to specify her offered assortment. To suit all local preferences, regionalization and store-level assortment optimization are widely used in practice and lead to competitive advantages. When selecting regionalized assortments, a trade-off between expensive, customized assortments in every store and inexpensive, identical assortments in all stores that neglect demand variation is preferable. We formulate a stylized model for the regionalized assortment planning problem (APP) with capacity constraints and given demand. In our approach, a common assortment that is supplemented by regionalized products is selected. While products in the common assortment are offered in all stores, products in the local assortments are customized and vary from store to store. The model is both applicable for optimizing a total assortment as well as a particular category of an assortment. Concerning the computational complexity, we show that the APP is strongly NP-hard. We formulate the APP as an integer program and provide algorithms and methods for obtaining approximate solutions and solving large-scale instances. Moreover, we extend our model to include substitution effects. Lastly, we perform computational experiments to analyze the benefits of regionalized assortment planning depending on the variation in customer demands between stores. [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]

A novel adaptive step-size matching pursuit algorithm (AStMP) is proposed. AStMP reduces the computational cost and increases the accuracy of reconstructing practical signals (i) whose sparsity K is unknown and/or (ii) may be corrupted by noise. AStMP accurately estimates K by combining the sparsity estimate of sparsity adaptive subspace pursuit (SASP) with the adaptively changing stepsize at each stage of sparsity adaptive matching pursuit (SAMP). Thus, AStMP can quickly achieve accurate estimation of the sparsity level and the true support set of the target signals. Meanwhile, a preselection is employed to reduce the computational complexity of each stage. When K is greater than half the number of measurements M, the probability of exact recovery is improved by analyzing the support set. Since the stepsize changes adaptively, AStMP can be applied in both the noiseless and noisy cases when the signal is not strictly sparse, allowing for exact or approximate signal recovery. Experimental results demonstrate that the AStMP is effective in fast and exact reconstruction and has good performance. [ABSTRACT FROM AUTHOR]

The Gromov-Hausdorff distance of two compact metric spaces is a measure for how far the spaces are from being isometric and has been extensively studied in the field of metric geometry. In recent years, a lot of attention has been devoted to computational aspects of the Gromov-Hausdorff distance. One of the most prominent applications is the problem of shape matching, where the goal is to decide whether two shapes given as polygonal meshes are equivalent under certain invariances. Therefore, many methods have been proposed which heuristically estimate the Gromov-Hausdorff distance of metric spaces induced by the shapes. However, the computational complexity of computing the Gromov-Hausdorff distance has not yet been thoroughly investigated. We show that-under standard complexity theoretic assumptions-determining the Gromov-Hausdorff distance of two finite metric spaces cannot be approximated within any reasonable bound in polynomial time. Furthermore, we discover attributes of metric spaces which have a major impact on the complexity of an instance. This enables us to develop an approximation algorithm which is fixed parameter tractable with respect to corresponding parameters. [ABSTRACT FROM AUTHOR]

We consider scheduling of unit-length jobs with release times and deadlines, where the objective is to minimize the number of gaps in the schedule. Polynomial-time algorithms for this problem are known, yet they are rather inefficient, with the best algorithm running in time $$O(n^4)$$ and requiring $$O(n^3)$$ memory. We present a greedy algorithm that approximates the optimum solution within a factor of 2 and show that our analysis is tight. Our algorithm runs in time $$O(n^2 \log n)$$ and needs only O( n) memory. In fact, the running time is $$O(n (g^*+1)\log n)$$ , where $$g^*$$ is the minimum number of gaps. [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 study a variant of an abstract scheduling problem inspired by the management of reclaimers in the stockyard of a coal export terminal. We prove NP-completeness of the problem and formulate it as a mixed-integer program. We show that for a given reclaiming sequence, the problem can be solved in pseudo-polynomial time. In addition, we provide simple, constant-factor approximation algorithms as well as exact branch-and-bound algorithms. An extensive computational study analyzes the performance of the algorithms. [ABSTRACT FROM AUTHOR]

Network infections that are already in progress cause challenges to those officers trying to preserve those nodes not yet infected. Static solutions can take advantage of global knowledge of the network to produce quick and approximate answers for those members who should be vaccinated. In dynamic situations however, small changes can severely alter those static solutions making them irrelevant. Yet in dynamic situations it can not be known with certainty which small changes will affect the solution and those that will not. Computational resources are wasted recalculating a global solution for the entire network, when a local recalculation may be enough. This paper presents a dynamic node vaccination solution that seeks to take advantage of these local recalculations. [ABSTRACT FROM AUTHOR]

We consider the m-Cycle Cover Problem of covering a complete undirected graph by m vertex-nonadjacent cycles of extremal total edge weight. The so-called TSP approach to the construction of an approximation algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the Euclidean Max m-Cycle Cover Problem with deterministic instances (edge weights) in a multidimensional Euclidean space and the Random Min m-Cycle Cover Problem with random instances UNI(0,1) are analyzed. It is shown that both algorithms have time complexity O( n ) and are asymptotically optimal for the number of covering cycles m = o( n) and $$m \leqslant \frac{{n^{1/3} }} {{\ln n}}$$ , respectively. [ABSTRACT FROM AUTHOR]

We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor approximation algorithm. [ABSTRACT FROM AUTHOR]

A square matrix V is called rigid if every matrix $${V^\prime}$$ obtained by altering a small number of entries of V has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major implications in computational complexity theory. One approach to establishing rigidity of a matrix V is to come up with a property that is satisfied by any collection of vectors arising from a low-dimensional space, but is not satisfied by the rows of V even after alterations. In this paper, we propose such a candidate property that has the potential of establishing rigidity of combinatorial design matrices over the field $${\mathbb{F}_2.}$$ Stated informally, we conjecture that under a suitable embedding of $${\mathbb{F}_2^n}$$ into $${\mathbb{R}^n,}$$ vectors arising from a low-dimensional $${\mathbb{F}_2}$$ -linear space always have somewhat small Kolmogorov width, i.e., admit a non-trivial simultaneous approximation by a low-dimensional Euclidean space. This implies rigidity of combinatorial designs, as their rows do not admit such an approximation even after alterations. Our main technical contribution is a collection of results establishing weaker forms and special cases of the conjecture above. [ABSTRACT FROM AUTHOR]

In this paper, we give an overview of the main results obtained on the complexity of scheduling under the non-idling constraint, i.e, when the jobs assigned to each machine must be processed with no intermediate delay. That constraint is met in practice when the cost of intermediate idle time is too high due to the idle time itself and/or the machine restarting. The non idling constraint is a strong constraint that often needs a new solving approach and most results about classical scheduling problems do not easily extend to the non-idling variant of the problem. In this survey, we mainly consider the non-idling variants of the basic scheduling problems. So, we first present basic properties, complexity results and some algorithms concerning the one-machine non-idling scheduling problem. Then we consider the m-machine non idling scheduling problem. We show that a few basic problems may be solved by rather easy extensions of the algorithm solving their classical counterpart. However, the complexity status of the non idling version of quite easy polynomial basic problems remains an open question. We finally consider a more constrained version of non-idling, called the 'homogeneously non idling' constraint, where for any subset of machines, the union of their busy intervals must make an interval and we present the structural property that leads to a polynomial algorithm for unit time jobs and a weak precedence. We conclude by giving some research directions that seem quite interesting to study both for theoretical and practical issues. [ABSTRACT FROM AUTHOR]

In this paper we present a novel method for clustering words in micro-blogs, based on the similarity of the related temporal series. Our technique, named SAX*, uses the Symbolic Aggregate ApproXimation algorithm to discretize the temporal series of terms into a small set of levels, leading to a string for each. We then define a subset of 'interesting' strings, i.e. those representing patterns of collective attention. Sliding temporal windows are used to detect co-occurring clusters of tokens with the same or similar string. To assess the performance of the method we first tune the model parameters on a 2-month 1 % Twitter stream, during which a number of world-wide events of differing type and duration (sports, politics, disasters, health, and celebrities) occurred. Then, we evaluate the quality of all discovered events in a 1-year stream, 'googling' with the most frequent cluster n-grams and manually assessing how many clusters correspond to published news in the same temporal slot. Finally, we perform a complexity evaluation and we compare SAX* with three alternative methods for event discovery. Our evaluation shows that SAX* is at least one order of magnitude less complex than other temporal and non-temporal approaches to micro-blog clustering. [ABSTRACT FROM AUTHOR]

The strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given sizes (cardinalities) minimizing the sum (over both clusters) of the intracluster sums of squared distances from the elements of the clusters to their centers is considered. It is assumed that the center of one of the sought clusters is specified at the desired (arbitrary) point of space (without loss of generality, at the origin), while the center of the other one is unknown and determined as the mean value over all elements of this cluster. It is shown that unless P = NP, there is no fully polynomial-time approximation scheme for this problem, and such a scheme is substantiated in the case of a fixed space dimension. [ABSTRACT FROM AUTHOR]

We consider the minimum affine separating committee (MASC) combinatorial optimization problem, which is related to ensemble machine learning techniques on the class of linear weak classifiers combined by the rule of simple majority. Actually, the MASC problem is a mathematical formalization of the famous Vapnik-Chervonenkis principle of structural risk minimization in the mentioned class of classifiers. According to this principle, it is required to construct a best performance ensemble classifier belonging to a family of the least possible VC-dimension. It is known that the MASC problem is NP-hard and remains intractable in spaces of any fixed dimension $$n>1$$ even under an additional constraint on the separated sets to be in general position. This special case of the MASC problem called MASC-GP(n) is the main subject of interest of the present paper. To design polynomial-time approximation algorithms for a class of combinatorial optimization problems containing the MASC problem, we propose a new framework, adjusting the well-known Multiple Weights Update method. Following this approach, we construct polynomial-time approximation algorithms with state-of-the-art approximation guarantee for the MASC-GP(n) problem. The results obtained provide a theoretical framework for learning a high-performance ensembles of affine classifiers. [ABSTRACT FROM AUTHOR]

Convoy movement planning problems arise in a number of important logistical contexts, including military planning, railroad optimization and automated guided vehicle routing. In the convoy movement problem (CMP), a set of convoys, with specified origins and destinations, are to be routed with the objective of minimizing either makespan or total flow time, while observing a number of side constraints. This paper characterizes the computational complexity of several restricted classes of CMPs. The principal objective is to identify the most parsimonious set of problem features that make the CMP intractable. A polynomial-time algorithm is provided for the single criterion two-convoy movement problem. The performance of a simple prioritization-idling approximation algorithm is also analyzed for the K-convoy movement problem. Error bounds are developed for the makespan and flow time objectives. [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]