Search

For a graph G = (V , E) without an isolated edge, a set D ⊆ E is an edge total dominating set of G if every edge e ∈ E is adjacent to at least one edge of D. The Minimum Edge Total Dominating Set problem is to compute a minimum cardinality edge total dominating set of G. It is known that the decision version of the problem is NP-complete for bipartite graphs, chordal graphs, and planar graphs. On the positive side, the problem is efficiently solvable for trees. In this paper, we further study the complexity of this problem in other graph classes. We design a linear-time algorithm to compute a minimum cardinality edge total dominating set in chain graphs, a subclass of bipartite graphs. We also propose linear-time algorithms for two subclasses of chordal graphs, namely, split graphs and proper interval graphs with no cut vertices. In addition, we show that the problem is APX-complete for graphs with maximum degree 3 and propose an approximation algorithm for the problem in k -regular graphs, where k ≥ 4. We discuss the complexity difference between the Minimum Edge Dominating Set problem and Minimum Edge Total Dominating Set problem which seem to be closely related. [ABSTRACT FROM AUTHOR]

Aiming at the problems in the existing white-feather broiler sound signal classification research, such as not considering the information and requirements in the real engineering application scenarios, not finding new applicable sound features, not providing the basis for the selection of classification learners, and the problems in the existing white-feather broiler sound signal filtering research, such as not carrying out in-depth research, not considering the signal characteristics, not analyzing the filtering effects in detail. Therefore, in this paper, the authors cleverly combined four methods of signal filtering, signal classification, machine learning, and sparse representation to propose a filtering and classification method for white-feather broiler sound signals based on sparse representation. Specifically, in terms of signal filtering, the signal characteristics of the white-feather broiler sound signal was carefully analyzed, a combination of noise reduction processing and signal reconstruction was newly proposed, and three classic and effective approximation algorithms were adopted, then the optimal filtering method of "using OMPA for noise reduction processing, and using 50-atom OMPA for signal reconstruction" was obtained. In terms of signal classification, in addition to the time-frequency domain and Mel-Frequency Cepstral Coefficients (abbr. MFCCs), time-frequency parameter features from sparse representations were newly extracted, and a total of 60-dimensional sound features were calculated on the frame signals, thus the data set was created. Feature engineering was performed on the data set, finally, the high-quality data set was obtained. Several common machine learning classification algorithms were used to train classification learners on the data set, and random forest with better performance was selected for parameter optimization. The parameter-optimized classification learner achieved the highest average prediction accuracy of 94.09%. Majority voting was newly proposed to process the prediction results to get the required signal classification result. On this basis, a new definition of classification accuracy suitable for white-feather broiler sound signals was newly proposed. Test results in real engineering application scenarios show that, the classification accuracy achieved by the proposed method on unknown white-feather broiler sound signals is about 88.89%. Compared with the existing research, the optimal filtering method considers the signal characteristics for the first time and achieves good filtering effects. The trained classification learner obtains excellent prediction effects and achieves good classification effects on several real sound types. This study is an important supplement to existing research on animal sound signal processing and classification, and provides important reference for the subsequent white-feather broiler health monitoring research. • Skillfully combine four methods to construct a signal processing and classification scheme. • Perform signal filtering based on sparse representation for the first time. • Use sparse representation to extract new time-frequency parameter features for the first time. • Obtain the optimal classification learner for white-feather broiler sound signal classification. • Newly propose the definition of classification accuracy for engineering application requirements. [ABSTRACT FROM AUTHOR]

In this work, we investigate the problem of maximizing nonmonotone DR-submodular function (possibly negative) subject to cardinality constraints on an integer lattice space. We propose a M -Threshold Decrease Algorithm that uses a compensation constant M from a special decomposition h (x) = f (x) − g (x) , which achieves a 1 − e − δ − ϵ approximation guarantee. To ensure that the algorithm ends in finite time, the supremum of δ is δ (ϵ) = ϵ max s ∈ Ω ⁡ h (χ s | 0) 2 k max s ∈ Ω ⁡ g (χ s | 0) + ϵ max s ∈ Ω ⁡ h (χ s | 0). If max s ∈ Ω ⁡ h (χ s | 0) > 2 k max s ∈ Ω ⁡ g (χ s | 0) , there exists ϵ ⁎ = arg ⁡ max ϵ ∈ (0 , 1) ⁡ 1 − e − δ (ϵ) − ϵ such that 1 − e − δ (ϵ ⁎) − ϵ ⁎ > 0. This implies that there is a valid δ such that 1 − e − δ − ϵ > 0. To accelerate the algorithm, we employ a random subset to replace the ground set and propose a Random M -Threshold Decrease Algorithm, where δ (ϵ) = ϵ r max s ∈ Ω ⁡ h (χ s | 0) 2 n k max s ∈ Ω ⁡ g (χ s | 0) + [ k (n − r) + ϵ r ] max s ∈ Ω ⁡ h (χ s | 0) with r being the size of the random subset and n being the size of the ground set. Furthermore, we demonstrate that, based on the DR-ratio γ d and the DS decomposition, the M -Threshold Decrease Algorithm is also suitable for solving the monotone non-DR-submodular maximization problem, achieving a 1 − e − γ d δ − O (ϵ) approximation guarantee. Because γ d is a challenging metric to calculate, we refine the M -Threshold Decrease Algorithm, which can return an estimate of γ d. To the best of our knowledge, this is the first time that a single factor approximation ratio has been proposed for the nonmonotone DR-submodular maximization problem (possibly negative) subject to cardinality constraints. • This paper adopts the decomposition structure to compensate the non-monotonicity and non-negativity for DR-submodular maximization. • Using a compensation constant M , we design a 1 − e − δ − ϵ approximation algorithm, namely M -Threshold Decrease Algorithm. • Based on the DR-ratio γ d , our algorithm is a 1 − e − δ γ d − O (ϵ) approximation algorithm for monotone non-DR-submodular maximization. [ABSTRACT FROM AUTHOR]

This paper considers a novel multi-agent linear stochastic approximation algorithm driven by Markovian noise and general consensus-type interaction, in which each agent evolves according to its local stochastic approximation process which depends on the information from its neighbors. The interconnection structure among the agents is described by a time-varying directed graph. While the convergence of consensus-based stochastic approximation algorithms when the interconnection among the agents is described by doubly stochastic matrices (at least in expectation) has been studied, less is known about the case when the interconnection matrix is simply stochastic. For any uniformly strongly connected graph sequences whose associated interaction matrices are stochastic, the paper derives finite-time bounds on the mean-square error, defined as the deviation of the output of the algorithm from the unique equilibrium point of the associated ordinary differential equation. For the case of interconnection matrices being stochastic, the equilibrium point can be any unspecified convex combination of the local equilibria of all the agents in the absence of communication. Both the cases with constant and time-varying step-sizes are considered. In the case when the convex combination is required to be a straight average and interaction between any pair of neighboring agents may be uni-directional, so that doubly stochastic matrices cannot be implemented in a distributed manner, the paper proposes a push-sum-type distributed stochastic approximation algorithm and provides its finite-time bound for the time-varying step-size case by leveraging the analysis for the consensus-type algorithm with stochastic matrices and developing novel properties of the push-sum algorithm. Distributed temporal difference learning is discussed as an illustrative application. [ABSTRACT FROM AUTHOR]

This paper considers the approximation of the infinite-horizon value function of the continuous-time switched linear quadratic regulator (LQR) problem. We propose a two successive approximation approach to achieving arbitrarily high accuracy. The infinite-horizon value function is first approximated by a finite-horizon value function, and the resulting truncation error is shown to converge to zero exponentially as the length of the control horizon increases. Then, the finite-horizon value function is approximated through a uniform discretization of the switched linear system, and the approximation error is proven to be proportional to the discretization step. These theoretical results facilitate the development of an efficient approximation algorithm, which further results in a near-optimal control policy. Compared with the existing methods, our algorithm obviates numerical issues induced by singular optimal control. Two numerical examples are presented to illustrate the effectiveness of our algorithm. [ABSTRACT FROM AUTHOR]

Learning-based image inpainting methods have made remarkable progress in recent years. Nevertheless, these methods still suffer from issues such as blurring, artifacts, and inconsistent contents. The use of vanilla convolution kernels, which have limited perceptual fields and spatially invariant kernel coefficients, is one of the main causes for these problems. In contrast, the multi-headed attention in the transformer can effectively model non-local relations among input features by generating adaptive attention scores. Therefore, this paper explores the feasibility of employing the transformer model for the image inpainting task. However, the multi-headed attention transformer blocks pose a significant challenge due to their overwhelming computational cost. To address this issue, we propose a novel U-Net style transformer-based network for the inpainting task, called the sparse self-attention transformer (Spa-former). The Spa-former retains the long-range modeling capacity of transformer blocks while reducing the computational burden. It incorporates a new channel attention approximation algorithm that reduces attention calculation to linear complexity. Additionally, it replaces the canonical softmax function with the ReLU function to generate a sparse attention map that effectively excludes irrelevant features. As a result, the Spa-former achieves effective long-range feature modeling with fewer parameters and lower computational resources. Our empirical results on challenging benchmarks demonstrate the superior performance of our proposed Spa-former over state-of-the-art approaches. • To accommodate the long-range modeling capacity of transformer blocks while reducing the computational burden, we introduce a novel U-Net style transformer-based network, called sparse self-attention transformer (Spa-former), to approach the inpainting task. • A transformer block to consider channel attention is adopted to model the global pixel relationships. • We adopt the ReLU function as the activation function to obtain a sparse attention/feature map, where coefficients with low/no correlation are removed from the attention map. • Experiments on challenging benchmarks demonstrate the superior performance of our Spa-former over state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

This paper considers the high-dimensional table compression problem on balanced k -partite graph. The objective is to choose half of the vertices from each of the k -partite to maximize the total weight of edges connecting the chosen vertices. Our main contribution is a 0.8785-approximation algorithm for the high-dimensional table compression problem by introducing the α - i n d e p e n d e n t solutions through Lasserre semidefinite programming. This new algorithm improved two previous low-dimensional results, namely the 0.8731-approximation algorithm of Wu et al. for the one-dimensional case and the 0.6708-approximation of Xu and Du for the two-dimensional case. [Display omitted] • Present a 0.8785-approximation algorithm for high-dimensional table compression problem. • Obtain a group of independent optimal solutions through Lasserre hierarchy semidefinite programming. • The integer solutions to the original problem are obtained through deformed random hyperplane recognition. [ABSTRACT FROM AUTHOR]

Considering the dynamic and stochasticity of demand for emergency medical service, this paper proposes two multi-period distributionally robust optimization models with first-order moment and Wasserstein ambiguity sets. To handle non-independent and non-identically distributed demand, we construct two different multi-period models and reformulate the two models into mixed-integer second-order cone programming (MISOCP) based on first-order moment and Wasserstein ambiguity sets. Taking into account the problem size increase caused by multiple periods, we develop a lifted polyhedral approximation algorithm to handle large-scale MISOCP. The numerical experiments demonstrate that our algorithm can significantly improve the solution efficiency compared to benchmarks including the outer approximation algorithm and Gurobi solver. Finally, based on real-world data from Montgomery County, Pennsylvania, we perform sensitivity analysis and compare different models. The results indicate that by comprehensively accounting for the dynamic and stochasticity of demand, managers can significantly mitigate cost while maintaining a heightened reliability level. • Emergency medical service system location with joint chance constraints. • Joint chance constraints with Wasserstein ambiguity sets. • Inter-period independent and inter-period correlated multi-period EMS model. • An efficient lifted polyhedral approximation algorithm based on second-order cone polyhedron approximation. [ABSTRACT FROM AUTHOR]

The Gromov-Hausdorff distance (d G H) proves to be a useful distance measure between shapes. In order to approximate d G H for X , Y ⊂ R d , we look into its relationship with d H , i s o , the infimum Hausdorff distance under Euclidean isometries. As already known for dimension d ≥ 2 , d H , i s o cannot be bounded above by a constant factor times d G H. For d = 1 , however, we prove that d H , i s o ≤ 5 4 d G H. We also show that the bound is tight. In effect, for X , Y ⊂ R with at most n points, this gives rise to an O (n log ⁡ n) -time algorithm to approximate d G H (X , Y) with an approximation factor of (1 + 1 4). [ABSTRACT FROM AUTHOR]

• Optimal anechoic coating based on metagratings. • Meta-absorbers in low-frequency and broadband via subwavelength thicknesses. • Enhanced multiple scattering effects in tandem metagratings. • The theoretical model modulates local resonance coupling of multi-layer meta-units. The anechoic coating capable of absorbing sound energy in low frequency and broadband is essential to conceal underwater vehicles. In this work, metagrating has been demonstrated as a tunable quasi-perfect absorber in low frequency, which is constructed with the single layer viscoelastic medium embedded with the periodic cylindrical cavities and the steel plate. Upon effective medium approximation and genetic algorithm optimization, such tunable absorbers could be put forward via deep subwavelength thicknesses. Broadband underwater absorption would be further approached in the multi-layer metagratings while the longitudinal waves convert into shear waves efficiently via the local resonance coupling and multiple scattering effects. Distinct from previous studies that limit the configuration of anechoic coatings to a given law and inefficiently alter numerous geometric parameters for optimal acoustic performance, the metagrating comprising multi-layer voids with random periods is adopted to precisely modulate the surface impedance in the target spectrum, leading to quasi-perfect absorption performance in broadband. Our results will contribute to designing lightweight underwater absorbers to improve the stealth performance of vehicles. [Display omitted] [ABSTRACT FROM AUTHOR]

• A new multi-objective optimization model is developed for ship schedule recovery. • Vessel speed reduction incentive programs and emission control areas are explicitly modeled. • Diverse schedule recovery options are considered within the designed modeling framework. • A customized algorithm is developed to solve the proposed multi-objective optimization model. • Detailed sensitivity analyses are performed to further examine various recovery options. Liner shipping networks often experience disruptions, and shipping lines must implement certain recovery measures. However, environmental concerns have to be considered as well. The implementation of vessel speed reduction incentive programs (VSRIPs) provides monetary incentives to shipping lines for sailing speed compliance in the vicinity of certain ports but, in the meantime, increases delays, since the speed-up option could not be used to the same extent. There is a scarcity of research that focuses on effectively addressing the competing objectives that arise during ship schedule recovery and incorporates emission reduction policies at ports. This study introduces a new multi-objective approach for ship schedule recovery, considering the presence of VSRIPs, emission control regulations, and a variety of recovery options. A customized algorithm inspired by the principles of dynamic secant approximation and the ε-constraint algorithm is developed and validated through extensive computational experiments. Detailed sensitivity analyses provide thorough managerial insights as well. [ABSTRACT FROM AUTHOR]

This paper addresses a family of geometric half-plane retrieval queries of points in the plane in the presence of geometric uncertainty. The problems include exact and uncertain point sets and half-plane queries defined by an exact or uncertain line whose location uncertainties are independent or dependent and are defined by k real-valued parameters. Point coordinate uncertainties are modeled with the Linear Parametric Geometric Uncertainty Model (LPGUM), an expressive and computationally efficient worst-case, first order linear approximation of geometric uncertainty that supports parametric dependencies between point locations. We present an efficient O (k 2) time and space algorithm for computing the envelope of the LPGUM line that defines the half-plane query. For an exact line and an LPGUM n points set, we present an O (log ⁡ n k + m k) time query and O (n k) space algorithm, where m is the number of LPGUM points on or above the half-plane line. For a LPGUM line and an exact points set, we present a O (k 2 + (k log ⁡ n log ⁡ log ⁡ n) ε + m) time and O ( n 2 log ⁡ n + k ε) space approximation algorithm, where 0 < ε ≤ 1 is the desired approximation error. For a LPGUM line and an LPGUM points set, we present two O (k 2 + (k log ⁡ n k log ⁡ log ⁡ n k) ε + m k) and O (m k 2 + (k log ⁡ n k log ⁡ log ⁡ n k) ε) time query and O ( (n k) 2 log ⁡ n k + k ε) space approximation algorithms for the independent and dependent case, respectively. [ABSTRACT FROM AUTHOR]

As a special case of Social Influence Maximization (SIM) problems, the top k-influencers problem aims to identify the top k actors, called members of the seed set, in a network whose endorsement of a given action causes it to be chosen by the largest possible set of the network's members, whose cardinality is called the influence spread (IS). Greedy framework algorithms like StaticGreedyCELF deliver a ground-truth solution with a proven approximation. This manuscript aims to investigate solutions for SIM with advantages comparable to or superior to those of CELF's solutions, such as the lower propagation time and variance of the IS. Novel models to discover alternatives to the CELF's solution in the forms of the Risk-Averse (RAIM), Risk-Least (RLIM), Time-Least (TLIM), and Risk-Blind Influence Maximization (RBIM) models among solutions non-dominated by the CELF's solution are proposed. A Genetic Algorithm Framework for Influence Maximization (GAFIM) is outlined, the only framework in the literature capable of achieving near-optimal solutions for the RAIM, RLIM, TLIM, and RBIM models under the famous diffusion models. A novel parameter tuning strategy offers GAFIM a class of optimal states rather than a single ideal state, allowing better exploration in each proposed model under each diffusion model. Notable findings from the research summary include (a) uncertainty in discovering an alternative under all conditions; (b) the favorable effect of expanding the seed set; (c) challenges in dominating CELF with RBIM; (d) a homogeneous variance distribution with no greater influence depth among alternatives; and (e) the positive side effects of models. • Proposing novel models to find alternatives to the ground truth solution as non-dominated solutions with extra advantages. • Developing GAFIM as the first algorithmic framework to reach near-optimal solutions for models under all famous diffusion models. • Introducing a parameter tuning strategy offering a class of optimal states rather than a single ideal state for better exploration. • Inferring significant order among models rather than performing simple comparisons by fitting the Bradley–Terry model. • Arriving at new insights into the characteristics and patterns of alternative solutions for influence maximization. [ABSTRACT FROM AUTHOR]

• Improved approximation algorithm for Budgeted Connected Dominating Set. • Optimal approximation algorithm for Budgeted Star Dominating Set. • Optimal approximation algorithm for Budgeted Edge-Vertex Domination. We consider the Budgeted version of the classical Connected Dominating Set problem (BCDS). Given a graph G and a budget k , we seek a connected subset of at most k vertices maximizing the number of dominated vertices in G. We improve over the previous (1 − e − 1) / 13 state of the art [Khuller, Purohit, and Sarpatwar, SODA 2014 by introducing a new method for performing tree decompositions in the analysis of the algorithm. This new approach provides a (1 − e − 1) / 12 approximation guarantee. By generalizing the analysis, we are able to obtain a further improvement to (1 − e − 7 / 8) / 11. On the other hand, we prove a (1 − e − 1 + ϵ) inapproximability bound, for any ϵ > 0 , holding also if the subset is required to have a star as a subgraph. In the latter case, we design another algorithm with a matching (1 − e − 1) approximation guarantee. Also, we examine the edge-vertex domination variant, where an edge dominates its endpoints and all vertices neighboring them. In Budgeted Edge-Vertex Domination (BEVD), we seek a (not necessarily connected) subset of k edges maximizing the number of dominated vertices in G. We prove a (1 − e − 1) -approximation and a (1 − e − 1 + ϵ) -inapproximability by reductions to/from the maximum coverage problem. Finally, we study the "dual" Partial Edge-Vertex Domination (PEVD) problem, and we present a log-approximation by a reduction to the partial cover problem. [ABSTRACT FROM AUTHOR]

• Consider the problem of finding low-rank approximations for norm in presence of ℓ p outliers in the dataset, where p ≥ 2. • Technique is sampling based and suggests additive and multiplicative approximation guarantees for the problem. • We extend our results to M-estimator loss functions and affine subspace approximation in presence of outliers. The subspace approximation problem with outliers, for given n points in d dimensions x 1 , x 2 , ... , x n ∈ R d , an integer 1 ≤ k ≤ d , and an outlier parameter 0 ≤ α ≤ 1 , is to find a k -dimensional linear subspace of R d that minimizes the sum of squared distances to its nearest (1 − α) n points. More generally, the ℓ p subspace approximation problem with outliers minimizes the sum of p -th powers of distances instead of the sum of squared distances. Even the case of p = 2 or robust PCA is non-trivial, and previous work requires additional assumptions on the input or generative models for it. Any multiplicative approximation algorithm for the subspace approximation problem with outliers must solve the robust subspace recovery problem, a special case in which the (1 − α) n inliers in the optimal solution are promised to lie exactly on a k -dimensional linear subspace. However, robust subspace recovery is Small Set Expansion (SSE)-hard, and known algorithmic results for robust subspace recovery require strong assumptions on the input, e.g., any d outliers must be linearly independent. In this paper, we show how to extend dimension reduction techniques and bi-criteria approximations based on sampling and coresets to the problem of subspace approximation with outliers. To get around the SSE-hardness of robust subspace recovery, we assume that the squared distance error of the optimal k -dimensional subspace summed over the optimal (1 − α) n inliers is at least δ times its squared-error summed over all n points, for some 0 < δ ≤ 1 − α. Under this assumption, we give an efficient algorithm to find a weak coreset or a subset of poly (k / ϵ) log ⁡ (1 / δ) log ⁡ log ⁡ (1 / δ) points whose span contains a k -dimensional subspace that gives a multiplicative (1 + ϵ) -approximation to the optimal solution. Our technique is based on the squared-length sampling algorithm suggested for low-rank approximation problems in the seminal work of Frieze, Kannan, and Vempala [12]. The running time of our algorithm is linear in n and d. Interestingly, our results hold even when the fraction of outliers α is large, as long as the obvious condition 0 < δ ≤ 1 − α is satisfied. We show similar results for subspace approximation with ℓ p error or more general M-estimator loss functions, and also give an additive approximation for the affine subspace approximation problem. [ABSTRACT FROM AUTHOR]

• We study a generalized version of the load balancing problem on unrelated machines with cost constraints. • We develop a bi-criteria approximation scheme for this problem. • We generalize known results for special cases (identical machines or a constant number of machines with cost constraints). • Our approach can be used to find approximation schemes for a wider class of load balancing problems with linear constraints. We study a generalized version of the load balancing problem on unrelated machines with cost constraints: Given a set of m machines (of certain types) and a set of n jobs, each job j processed on machine i requires p i , j time units and incurs a cost c i , j , and the goal is to find a schedule of jobs to machines, which is defined as an ordered partition of n jobs into m disjoint subsets, in such a way that some objective function of the vector of the completion times of the machines is optimized, subject to the constraint that the total costs by the schedule must be within a given budget B. Motivated by recent results from the literature, our focus is on the case when the number of machine types is a fixed constant and we develop a bi-criteria approximation scheme for the studied problem. Our result generalizes several known results for certain special cases, such as the case with identical machines, or the case with a constant number of machines with cost constraints. Building on the elegant technique recently proposed by Jansen and Maack [1] , we construct a more general approach that can be used to derive approximation schemes for a wider class of load balancing problems with linear constraints. [ABSTRACT FROM AUTHOR]

In this paper, we present an O (n 2) time algorithm to find a largest area triangle contained inside a terrain with n vertices. We also present an O (n log ⁡ n) time 1 2 -factor approximation algorithm and an O (1 ε n log 2 ⁡ n) time (1 − ε) -factor approximation scheme for the same. [ABSTRACT FROM AUTHOR]

We are given a graph G = (V ∪ T , E) , with V ∪ T the set of vertices where T is a set of terminals and E the set of edges. The multi-terminal vertex separator problem consists in finding a subset of vertices S ⊆ V of minimum size intersecting all paths between every pair of terminals. In this paper we present three extended linear integer programming formulations for the multi-terminal vertex separator problem and we develop Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present the pricing problem, the branching scheme and the computation of the dual bound used during the column generation phase. Computational results are reported comparing the performance of the formulations on a set of instances. [ABSTRACT FROM AUTHOR]

Submodular maximization is well studied in the fields of data mining and machine learning. We study the submodular maximization subject to a cardinality constraint k for large scale scenarios applications under two combined settings. One is that all elements arrive in a streaming fashion, and the other is that some elements may be invalid at last. For this problem, which is called streaming robust submodular maximization (SRSM) problem, we explore an approximation algorithm, returning a subset S from the ground set V with a limit size, such that it represents V and is robust to a broken set E well. Our algorithm only makes one pass over data, and achieves a constant-factor 0.1224 approximation guarantee, independent of the cardinality constraint parameter k. Based on the algorithm for SRSM problem, we continue to discuss this problem over sliding windows, in which we are asked to obtain a proper set that only considers the last W elements, and derive an algorithm with a constant (0. 0612 − ϵ) -approximation guarantee. At last we also propose numerical experiments on some applications to well demonstrate our algorithm for SRSM problem over sliding windows. [ABSTRACT FROM AUTHOR]

• We give the definition of MM problems in models, and prove the NP-hardness and #P-hardness of the problems. • An approximation algorithm is designed for the MM problem in each model. • We conduct extensive experiments based on the real-word databases to validate our algorithms. • The experiments results show the effectiveness of our algorithms. Influence maximization (IM) is a widely studied problem in social networks, which aims at finding a seed set with limited size that can maximize the expected number of influenced users. However, existing studies haven't considered the matching relationship, which refers to such scenarios that influenced users seek matched partners among the influenced users, such as time matching with friends to watch movie, or matching for opposite sex in the blind date. In this paper, we investigate different matching scenarios and propose online-matching (offline-matching), in which the matching and influence propagation are simultaneous (asynchronous). For the matching result, we introduce two matched types ' s - m a t c h e d ', i.e., i → j and ' d - m a t c h e d ', i.e., i ↔ j. Then, we formulate the matching influence maximization (MM) problem to optimize a limited seed set that maximizes the expected number of matched users. We prove that the MM problem is NP-hard and the computation of the matching influence is #P-hard. Next, we analyze the submodularity of the matching influence. To address the problem, we propose efficient methods OPMM (SAMM) to solve the MM in online-matching (offline-matching) with (1 − 1 / e − ϵ) -approximation (β (1 − 1 / e − ϵ) -approximation) guarantee. Experiments on the real-world datasets show our algorithms outperform state of the art algorithms in terms of more accurate matching propagation results. [ABSTRACT FROM AUTHOR]

• We give the definition of problems PIO and PID, and prove the NP-hardness of the two problems. • We propose two approximation algorithms for PIO and PID. • We conduct extensive simulations to validate our algorithms. The results show the effectiveness of our algorithms. Supply energy to battery-powered sensor devices by deploying wireless chargers is a promising way to prolong the operation time of wireless sensor networks, and has attracted much attention recently. Existing works focus on maximizing the total received charging power of the network. However, this may face the unbalanced energy allocation problem, which is not beneficial to prolong the operation time of wireless sensor networks. In this paper, we consider the individual energy requirement of each sensor node, and study the problem of minimum charger placement. That is, we focus on finding a strategy for placing wireless chargers from a given candidate location set, such that each sensor node's energy requirement can be met, meanwhile the total number of used chargers can be minimized. We deal with the problem under both omnidirectional and directional charging models, and prove its NP-hardness. For the omnidirectional charging case, we present two approximation algorithms which are based on greedy scheme and relax rounding scheme, respectively. We prove that both of the two algorithms have performance guarantees. For the directional charging case, we first extract the candidate orientation set for each candidate location to reduce the search space from infinite to a limited set, and then propose a greedy algorithm that also has a proved performance guarantee. Finally, we validate the performance of our algorithms by performing extensive numerical simulations. Simulation results show the effectiveness of our proposed algorithms. [ABSTRACT FROM AUTHOR]

• Show that every interval graph G has an equitable tree- k -coloring for any integer k ≥ ⌈ Δ (G) + 1 / 2 ⌉. • Design linear algorithm for proper interval graphs. • Prove the NP-hardness of the problems. • Design a quadratic 2-approximation algorithm for the equitable tree coloring problem in chordal graphs. • Prove that the problem has no α -approximation algorithm for any α < 3 2. An equitable tree- k -coloring of a graph is a vertex k -coloring such that each color class induces a forest and the size of any two color classes differs by at most one. In this work, we show that every interval graph G has an equitable tree- k -coloring for any integer k ≥ ⌈ (Δ (G) + 1) / 2 ⌉ , solving a conjecture of Wu, Zhang and Li (2013) for interval graphs, and furthermore, give a linear-time algorithm for determining whether a proper interval graph admits an equitable tree- k -coloring for a given integer k. For disjoint union of split graphs, or K 1 , r -free interval graphs with r ≥ 4 , we prove that it is W 1 -hard to decide whether there is an equitable tree- k -coloring when parameterized by number of colors, or by treewidth, number of colors and maximum degree, respectively. On the positive side, we propose a quadratic 2-approximation algorithm for the equitable tree-coloring problem in chordal graphs. Moreover, it is proved that there is no α -approximation algorithm for any α < 3 2. [ABSTRACT FROM AUTHOR]

We consider the dispersed p → -neighbor k -supplier problem. In the classical k -supplier problem, we have to select k suppliers in a metric space such that the maximum distance between a customer and its closest supplier is minimized. Here, we generalize this problem to the case where each customer possibly needs service from more than one supplier. Moreover, the selected suppliers should not be too close to each other, i.e., they need to be dispersed. For the classical k -supplier problem, and its special case the k -center problem, there is a 3- and a 2-approximation respectively. We show that these guarantees can also be given in the case when customers need service from multiple suppliers, without imposing dispersion constraints. If we generalize the problem to the dispersed case, without imposing neighboring constraints, we get inapproximability results depending on the measure of dispersion. We also show (almost) matching upper bounds. Finally, we show that adding both the neighbor requirement and the dispersion requirement leads to an inapproximable problem. [ABSTRACT FROM AUTHOR]

In the Multi-Spreader Crane Scheduling Problem (MSCSP), containers with identical dimensions but variable weights are arranged along a grid. A multi-spreader crane is used to lift all the containers. The crane has m > 1 modes. When it is in the p th mode, the crane can remove p adjacent containers along the same row at the same time as long as the total weight of the containers does not exceed the loading capacity κ p. Such a lift takes h p minutes. It also takes c p , q minutes for the crane to switch from mode p to q when p ≠ q. The goal is to find a crane lift sequence so that the total time it takes to lift all the containers is minimized. This paper investigates the computational complexity of MSCSP. First, we establish a connection between greedy crane lift sequences and supersequences. We then prove that MSCSP is NP-hard when the crane has three or more modes by a reduction from a version of the Shortest Common Supersequence problem. Lastly, we investigate two problems that arise naturally when heuristics are used to solve MSCSP. We show that one can be solved using dynamic programming while the other remains computationally hard. We also provide an approximation algorithm that behaves nicely when the changeover times are not much larger than the lifting times of the crane. [ABSTRACT FROM AUTHOR]

The general position-dependent scheduling problems are studied in this paper. A 2-approximation algorithm is proposed for the learning scheduling problem on a single machine with release time to minimize the makespan. To minimize the total completion time on a single machine with release time and learning effect, we design a 2-approximation algorithm and a P T A S. Moreover, for the deteriorating scheduling problem to minimize the makespan on parallel machines, a 2-approximation algorithm is provided. [ABSTRACT FROM AUTHOR]

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

The problem of detecting communities is one of the essential problems in the study of social networks. To devise the algorithms of community detection, one should first define high-quality communities. In fact, there are no agreed methods to measure the quality of the community. In this paper, we consider a novel objective function of this problem. Our goal is to maximize not only the average of the sum of edge weights within communities (i.e., average-case) but also the sum of edge weights within the minimum community (i.e., worst-case). To balance both the average-case and worst-case problems, we introduce a parameter into our objective function and call it the mixed-cased community detection problem. For the worst-case, we devise several approximation algorithms, such as the Greedy, Semi-Sandwich Approximation, and Local Search algorithms. For the average-case, an efficient Terminal-based algorithm is proposed. We prove that the best solution between the average-case and worst-case problems still can provide an approximate guarantee for any mixed-case community detection problem. Moreover, we devise a heuristic algorithm for our problem. Finally, we conduct the experiments in three networks. The experimental results indicate that our proposed methods can form a high-quality community partition. • A novel objective function of community detection problem is proposed. • The Greedy, Semi-Sandwich Approximation and Local Search algorithms are devised to solve the worst-case problem. • An efficient Terminal-based algorithm is proposed to solve the average-case problem. • An algorithm with the approximate guarantee is proposed for any mixed-case problem. • The experimental results indicate that our proposed methods can form a high-quality community partition. [ABSTRACT FROM AUTHOR]

Given a vertex-colored arc-weighted directed acyclic graph G , the Maximum Colorful Subtree problem (or MCS) aims at finding an arborescence of maximum weight in G , in which no color appears more than once. The problem was originally introduced in [1] in the context of de novo identification of metabolites by tandem mass spectrometry. However, a thorough analysis of the initial motivation shows that the formal definition of MCS should be amended, since the input graph G actually possesses extra properties, which have been unexploited so far. This leads us to describe in this paper a more precise model that we call Maximum Colorful Arborescence (MCA), which we extensively study in terms of algorithmic complexity. In particular, we show that exploiting the implied Color Hierarchy Graph of the input graph G can lead to exact polynomial algorithms and approximation algorithms. We also develop Fixed-Parameter Tractable (FPT) algorithms for the problem parameterized by the "dual parameter" ℓ C , defined as the minimum number of vertices of G which are not kept in the solution. [ABSTRACT FROM AUTHOR]

Unmanned Aerial Vehicles (UAVs) are expected to be important components in the upcoming wireless communication field, which are increasingly used as data collectors to gather sensory data from Wireless Sensor Networks (WSNs) due to their high mobility, flexible deployment. Since the storage capacity and lifetime of sensors are increasing with the development of science and technology, sensors can store more and more sensing data about the monitoring area. However, due to the energy limitation of UAVs and a large amount of data carried by sensors, we can not collect all data from WSN within the limited time. Therefore, in this paper, we investigate two problems: (1) without the energy limitation of UAV, how to optimize the trajectory of UAV to minimize the sum of traveling time and data transmission time of UAV while guaranteeing the amount of data collected from each sensor reaches to a certain proportion of the original data, which is called the Minimizing Transportation and Communication Latency (MTCL) problem; (2) given the limited budget of UAV, how to find the optimal trajectory of UAV to maximize the minimum ratio of the collected data to the stored data among all sensors, which is called the Maximizing Data Collection Proportion (MDCP) problem. We first prove that both the problems are NP-Complete. Then we study a special case of the MTCL problem, which is called the MTCL-disjoint problem, in which any pair of data collection areas are disjoint, and we propose an approximation algorithm to solve the MTCL-disjoint problem. Based on the MTCL-disjoint problem, we propose an approximation algorithm for the general MTCL problem. Afterward, an approximation algorithm for the MDCP problem is proposed on the basis of the algorithm for the MTCL problem. Finally, we present numerical results in different scenarios to assess the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the two-stage submodular maximization problem, where there is a collection F = { f 1 ,... , f m } of m submodular functions which are defined on the same element ground set Ω. The goal is to select a subset S ⊆ Ω of size at most ℓ such that 1 m ∑ f ∈ F max T ⊆ S , T ∈ I ⁡ f (T) is maximized, where I denotes a specifically-defined independence system. We consider the two-stage submodular maximization with a P -matroid constraint and present a (1 / (P + 1)) (1 − 1 / e (P + 1)) -approximation algorithm. Furthermore, we extend the algorithm to the two-stage submodular maximization with a more generalized P -exchange system constraint and show the approximation ratio can be maintained with slightly modifications of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we study the edge metric dimension problem (EMDP). We establish a potential function and give a corresponding greedy algorithm with approximation ratio 1 + ln ⁡ n + ln ⁡ (log 2 ⁡ n) , where n is the number of vertices in the graph G. [ABSTRACT FROM AUTHOR]

In this paper, we first consider a dynamic k -level facility location problem, which is a generalization of the k -level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for this problem which finds a constant factor approximate solution. Then, we investigative the dynamic k -level facility location problem with submodular penalties and outliers, which extend the existing problem on two fronts, namely from static to dynamic and from without penalties (outliers) to penalties (outliers) allowed. Based on primal-dual technique and the triangle inequality property, we also give two constant factor approximation algorithms for the dynamic problem with submodular penalties and outliers, respectively. [ABSTRACT FROM AUTHOR]

Genomic Scaffold Filling problem forms an important class of problems, and has been paid lots of attention in the literature. In this paper, we study one of the Genomic Scaffold Filling problems, called One-sided-GSF-max-BC problem. In this paper, we give a new approximation algorithm for the problem. For any given instance of the One-sided-GSF-max-BC problem, auxiliary graphs are constructed based on the given instance and the relation between maximum matching in auxiliary graphs and optimal solution is studied, which results in an approximation algorithm with ratio 2.57. [ABSTRACT FROM AUTHOR]

• A bicriteria approximation algorithm for Max k -Uncut with ratio at least 1/2. • A bicriteria approximation algorithm for Densest k -Subgraph with ratio at least 1/4. • A new perspective to the Densest k -Subgraph problem. The Max k -Uncut problem arose from the study of homophily of large-scale networks. Given an n -vertex undirected graph G = (V , E) with nonnegative weights defined on edges and a positive integer k , the Max k -Uncut problem asks to find a partition { V 1 , V 2 , ⋯ , V k } of V such that the total weight of edges that are not cut is maximized. This problem is the complement of the classic Min k -Cut problem, and was proved to have surprisingly rich connection to the Densest k -Subgraph problem. In this paper, we give an approximation algorithm for Max k -Uncut using a non-uniform approach combining LP-rounding and the greedy strategy. The algorithm partitions the vertices of G into at least (1 − 1 e) k parts in expectation, and achieves a good expected approximation ratio 1 2 (1 + (n − k n) 2). [ABSTRACT FROM AUTHOR]

• We present the first linear-time approximation algorithm for non-monotone adaptive submodular maximization. • Our results do not rely on pointwise submodularity. • We present a faster algorithm for the monotone case. • We propose an enhanced algorithm for the montone case subject to a partition matroid constraint. • We develop a linear-time algorithm for maximizing fully adaptive submodular functions subject to a parition matroid constraint. In this paper, we study the non-monotone adaptive submodular maximization problem subject to a cardinality constraint. We first revisit the adaptive random greedy algorithm proposed in [13] , where they show that this algorithm achieves a 1 / e approximation ratio if the objective function is adaptive submodular and pointwise submodular. It is not clear whether the same guarantee holds under adaptive submodularity (without resorting to pointwise submodularity) or not. Our first contribution is to show that the adaptive random greedy algorithm achieves a 1 / e approximation ratio under adaptive submodularity. One limitation of the adaptive random greedy algorithm is that it requires O (n × k) value oracle queries, where n is the size of the ground set and k is the cardinality constraint. Our second contribution is to develop the first linear-time algorithm for the non-monotone adaptive submodular maximization problem. Our algorithm achieves a 1 / e − ϵ approximation ratio (this bound is improved to 1 − 1 / e − ϵ for monotone case), using only O (n ϵ − 2 log ⁡ ϵ − 1) value oracle queries. Notably, O (n ϵ − 2 log ⁡ ϵ − 1) is independent of the cardinality constraint. For the monotone case, we propose a faster algorithm that achieves a 1 − 1 / e − ϵ approximation ratio in expectation with O (n log ⁡ 1 ϵ) value oracle queries. We also generalize our study by considering a partition matroid constraint, and develop a linear-time algorithm for monotone and fully adaptive submodular functions. [ABSTRACT FROM AUTHOR]

This paper addresses the robustness of large-scale closed-loop structured systems in the sense of arbitrary pole placement when subject to failure of feedback links. Given a structured system with input, output, and feedback matrices, we first aim to verify whether the closed-loop structured system is robust to the simultaneous failure of any subset of feedback links of cardinality at most γ. Subsequently, we address the associated design problem in which given a structured system with input and output matrices, we need to design a sparsest feedback matrix that ensures the robustness of the resulting closed-loop structured system to simultaneous failure of at most any γ feedback links. We first prove that the verification problem is NP-complete even for irreducible systems and the design problem is NP-hard even for so-called structurally cyclic systems. We also show that the design problem is inapproximable to factor (1 − o (1)) log n , where n denotes the system dimension. Then we propose algorithms to solve both the problems: a pseudo-polynomial algorithm to address the verification problem of irreducible systems and a polynomial-time O (log n)-optimal approximation algorithm to solve the design problem for a special feedback structure, so-called back-edge feedback structure. [ABSTRACT FROM AUTHOR]

We study the worst-case behavior of Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, we revisit a randomized approach of Boppana that forms a simple 1-round distributed algorithm, as well as a streaming algorithm and a preemptive online algorithm. We show that it gives a tight (Δ + 1) / 2 -approximation in unweighted graphs of maximum degree Δ, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a (Δ + 1) -approximation, but a simple modification results in an asymptotic expected 0.529 (Δ + 1) -approximation. [ABSTRACT FROM AUTHOR]

The positive influence dominating set(PIDS) problem is a well-known APX-hard problem and there exists a greedy approximation algorithm with an approximation ratio of H (δ). However, the PIDS which is formed by this algorithm is not connected. This paper proposes an algorithm with an approximation ratio of H (12) to find the connected PIDS in a cubic graph. Furthermore, this paper also proposes an algorithm with an approximation ratio of H (9) to find the partial positive influence dominating set(PPIDS). Both of these two algorithms have a time complexity of O (n 3). In addition, we prove that for every node in the PIDS(or PPIDS) which is formed by our algorithms, there exists at least one node in the PIDS(or PPIDS) that is its two-hop neighbor. We also proved that in a cubic graph, the subgraph induced by PIDS is connected. These conclusions are also true in k-regular graphs. [ABSTRACT FROM AUTHOR]

For a given b ∈ N n and a hypergraph H = (V , E) with maximum degree Δ, the b -set multicover problem which we are concerned with in this paper may be stated as follows: find a minimum cardinality subset C ⊆ E such that no vertex v i ∈ V is contained in less than b i hyperedges of C. Peleg, Schechtman, and Wool (1997) conjectured that for any fixed Δ and b = min i ⁡ b i , the problem cannot be approximated with a ratio strictly smaller than δ : = Δ − b + 1 , unless P = NP. In this paper, we show that the conjecture of Peleg et al. is not true on ℓ -uniform hypergraphs by presenting a polynomial-time approximation algorithm based on a matching/covering duality for hypergraphs due to Ray-Chaudhuri (1960), which we convert into an approximative form. The given algorithm yields a ratio smaller than (1 − b (ℓ + 1) Δ) Δ b. Moreover, we prove that the lower bound conjectured by Peleg et al. holds for regular hypergraphs under the unique games conjecture. [ABSTRACT FROM AUTHOR]

In this article, we study a variant of the minimum dominating set problem known as the minimum liar's dominating set (MLDS) problem. We prove that the MLDS problem is NP-hard in unit disk graphs. We point out that the approximation guarantee of 11 2 for the approximation algorithm for unit disk graphs proposed by Banerjee and Bhore (2019) [11] is not correct and we propose a simple O (n + m) time 7.31-factor approximation algorithm, where n and m are the number of vertices and edges, respectively, in the given unit disk graph. Finally, we prove that the MLDS problem admits a polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

Vertex deletion problems on graphs involve finding a set of minimum number of vertices whose deletion results in a graph with some specific property. In a recent study on vertex deletion problems on split graphs, it was shown that transforming a split graph to a block graph or a threshold graph using minimum number of vertex deletions is NP -hard. We call the decision version of these problems as Split to Block Vertex Deletion (SBVD) and Split to Threshold Vertex Deletion (STVD), respectively. In this paper, we study the parameterized complexity of these problems with the number of vertex deletions, k , as a parameter. These problems are implicit 4- Hitting Set and thus admit an algorithm with running time O ⋆ (3.0755 k) , a kernel with O (k 3) vertices, and a 4-approximation algorithm. In this paper, we exploit the structural properties of the concerned graph classes and obtain a kernel for SBVD with O (k 2) vertices and FPT algorithms for SBVD and STVD with running times O ⋆ (2.3028 k) and O ⋆ (2.7913 k) , respectively. We further give improved approximation algorithms for SBVD and STVD. [ABSTRACT FROM AUTHOR]

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

In this paper, we consider the k -prize-collecting multicut on a tree (k -PCM(T)) problem. In this problem, we are given an undirected tree T = (V , E) , a set of m distinct pairs of vertices P = { (s 1 , t 1) , ... , (s m , t m) } and a parameter k with k ≤ m. Every edge in E has a nonnegative cost c e. Every pair (s i , t i) in P has a nonnegative penalty cost π i. Our goal is to find a multicut M that separates at least k pairs in P such that the total cost, including the edge cost of the multicut M and the penalty cost of the pairs not separated by M , is minimized. This problem generalizes the well-known multicut on a tree problem. Our main work is to present a (4 + ε) -approximation algorithm for the k -PCM(T) problem via the methods of primal-dual and Lagrangean relaxation, where ε is any fixed positive number. [ABSTRACT FROM AUTHOR]

The minimum tracking set problem is an optimization problem that deals with monitoring communication paths that can be used for exchanging point-to-point messages using as few tracking devices as possible. More precisely, a tracking set of a given graph G and a set of source-destination pairs of vertices is a subset T of vertices of G such that the vertices in T traversed by any source-destination shortest path P uniquely identify P. The minimum tracking set problem has been introduced in Banik et al., CIAC (2017) [1] for the case of a single source-destination pair. There, the authors show that the problem is APX-hard and that it can be 2-approximated for the class of planar graphs, even though no hardness result is known for this case. In this paper we focus on the case of multiple source-destination pairs and we present the first O ˜ (n) -approximation algorithm for general graphs. Moreover, we prove that the problem remains NP-hard even for cubic planar graphs and all pairs S × D , where S and D are the sets of sources and destinations, respectively. Finally, for the case of a single source-destination pair, we design an (exact) FPT algorithm w.r.t. the maximum number of vertices at the same distance from the source. [ABSTRACT FROM AUTHOR]

In this paper we consider two problems concerning string factorisation. Specifically given a string w and an integer k find a factorisation of w where each factor has length bounded by k and has the minimum (the F-Min-D problem) or the maximum (the F-Max-D problem) number of different factors. The F-Min-D has been proved to be NP-hard even if k = 2 in [9] and for this case we provide a 3/2-approximation algorithm. The F-Max-D problem, up to our knowledge has not been considered in the literature. We show that this problem is NP-hard for any k ≥ 3. In view of this we propose a 2-approximation algorithm (for any k) and an FPT algorithm w.r.t. parameter max ⁡ { k , | Σ | }. [ABSTRACT FROM AUTHOR]

The problem of constrained clustering has attracted significant attention in the past decades. In this paper, we study the balanced k -center, k -median, and k -means clustering problems where the size of each cluster is constrained by the given lower and upper bounds. The problems are motivated by the applications in processing large-scale data in high dimension. Existing methods often need to compute complicated matchings (or min cost flows) to satisfy the balance constraint, and thus suffer from high complexities especially in high dimension. We develop an effective framework for the three balanced clustering problems to address this issue, and our method is based on a novel spatial partition idea in geometry. For the balanced k -center clustering, we provide a 4-approximation algorithm that improves the existing approximation factors; for the balanced k -median and k -means clusterings, our algorithms yield constant and (1 + ϵ) -approximation factors with any ϵ > 0. More importantly, our algorithms achieve linear or nearly linear running times when k is a constant, and significantly improve the existing ones. Our results can be easily extended to metric balanced clusterings and the running times are sub-linear in terms of the complexity of n -point metric. [ABSTRACT FROM AUTHOR]

In this paper, we consider Euclidean versions of the 2-tuple dominating set problem and the liar's dominating set problem. For a given set P = { p 1 , p 2 , ... , p n } of n points in R 2 , the objective of the Euclidean 2-tuple dominating set problem is to find a minimum size set D ⊆ P such that | N p i ∩ D | ≥ 2 for each p i ∈ P , where N p i = { p j ∈ P ∣ δ (p i , p j) ≤ 1 } and δ (p i , p j) is the Euclidean distance between p i and p j. The objective of the Euclidean liar's dominating set problem is to find a set D (⊆ P) of minimum size satisfying the following two conditions: (i) D is a 2-tuple dominating set of P , and (ii) for every distinct pair of points p i and p j in P , | (N p i ∪ N p j ) ∩ D | ≥ 3. We first propose a simple O (n log n) time 63 2 -factor approximation algorithm for the Euclidean liar's dominating set problem. Next, we propose approximation algorithms to improve the approximation factor to 732 α for 3 ≤ α ≤ 183 , and 846 α for 3 ≤ α ≤ 282. The running time of both the algorithms is O (n α + 1 Δ) , where Δ = max { | N p | : p ∈ P }. Finally, we propose a PTAS for the Euclidean 2-tuple dominating set problem. [ABSTRACT FROM AUTHOR]

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