Search

The influence maximization problem aims to find some seeds which can cause the maximum influence spread results in a social network. Most researches focus on the non-adaptive strategies, in which all seeds are selected at once. For the non-adaptive strategies, the seeds may influence other seeds in the influence spread process and make the waste of budget. This paper considers the adaptive strategies and studies the adaptive influence maximization and adaptive stochastic influence maximization in the general feedback model. These problems select seeds adaptively, and it completes each selection after the fixed observation time-step. In this paper, we utilize the adaptive greedy to solve these problems and propose a theoretical analysis by introducing a comparative factor. In addition, we present the feasible approximation algorithm using the reverse sampling technique. Finally, we carry out experiments on three networks to show the efficiency of adaptive strategies. • We study the adaptive influence maximization problem under a general model. • We propose a comparative factor and obtain the approximation ratio of an adaptive greedy algorithm. • We not only consider the problem with cardinality constraint but also the knapsack constraint. • We conduct several experiments on three real datasets to show the effectiveness of adaptive methods. [ABSTRACT FROM AUTHOR]

Given a metric graph G = (V , E , w) , a specific vertex c ∈ V , and an integer p , let T be a depth-2 spanning tree of G rooted at c such that c is adjacent to p vertices called hubs and each of the remaining vertices is adjacent to a hub. The Star p -Hub Routing Cost Problem is to find a spanning tree T of G satisfying the conditions stated above such that the sum of distances between all pairs of vertices in T is minimized. In this paper, we prove that the Star p -Hub Routing Cost Problem is NP-hard. A 3-approximation algorithm running in time O (n 2) is given for solving the same problem where n is the number of vertices in the input graph. Moreover, we give an example to show that the analysis of the approximation ratio cannot be better than 2 − ϵ for any ϵ > 0. [ABSTRACT FROM AUTHOR]

We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an O (log n) -approximation algorithm, based on the submodular goal-value approach of Deshpande, Hellerstein and Kletenik. Our second algorithm, which is simple, is based on the algorithm solving the SBFE problem for k -of- n functions, due to Salloum, Breuer, and Ben-Dov. It achieves a (B − 1) approximation factor, where B is the number of blocks of 0's and 1's in the standard vector representation of the symmetric Boolean function. As part of the design of the first algorithm, we prove that the goal value of any symmetric Boolean function is less than n (n + 1) / 2. Finally, we give an example showing that for symmetric Boolean functions, minimum expected verification cost and minimum expected evaluation cost are not necessarily equal. This contrasts with a previous result, given by Das, Jafarpour, Orlitsky, Pan and Suresh, which showed that equality holds in the unit-cost case. [ABSTRACT FROM AUTHOR]

Discrete random variables are essential ingredients in various artificial intelligence problems. These include the estimation of the probability of missing the deadline in a series-parallel schedule and the assignment of suppliers to tasks in a project in a manner that maximizes the probability of meeting the overall project deadline. The solving of such problems involves repetitive operations, such as summation, over random variables. However, these computations are NP-hard. Therefore, we explore techniques and methods for approximating random variables with a given support size and minimal Kolmogorov distance. We examine both the general problem of approximating a random variable and a one-sided version in which over-approximation is allowed but not under-approximation. We propose several algorithms and evaluate their performance through computational complexity analysis and empirical evaluation. All the presented algorithms are optimal in the sense that given an input random variable and a requested support size, they return a new approximated random variable with the requested support size and minimal Kolmogorov distance from the input random variable. Our approximation algorithms offer useful estimations of probabilities in situations where exact computations are not feasible due to NP-hardness complexity. [ABSTRACT FROM AUTHOR]

Surrogate-assisted evolutionary algorithms (SAEAs) are a promising approach for solving expensive multiobjective optimization problems, but they often cannot address high-dimensional problems. Although one common approach to overcoming this challenge is to construct reliable surrogates, their accuracy inevitably deteriorates in a high-dimensional search space. Thus, this paper presents a novel SAEA based on scalarization function approximation, which is designed to strengthen its robustness against this deterioration. The proposed algorithm constructs an approximation model for each scalarization function defined in a decomposition-based framework. Each decomposed problem is then solved using multiple independent models trained for its neighbor problems. The intent is to decrease the risk of search performance degradations caused by unreliable approximations and retain the redundancy of the surrogate-assisted search to hedge the risk of over-fitting. Furthermore, each approximation model is adapted to a promising region of its corresponding decomposed problem to reduce the complexity of model fitting given a limited number of training samples. Experimental results show that the proposed algorithm is competitive with state-of-the-art SAEAs adapted for high-dimensional problems. [ABSTRACT FROM AUTHOR]

k -Clustering partitions a set of n points in a metric space into at most k clusters in a way that makes the resulted clusters satisfy both the homogeneity and the separation criteria. The diameter of a cluster is the maximum distance between pairs of points in the cluster, and the split of a cluster is the minimum distance between points of the cluster and ones outside the cluster. In this paper, we propose a new criterion for measuring the goodness of clusters: The ratio of the minimum cluster split to the maximum cluster diameter (abbr. RSD). We study the following two optimization problems: Maximizing RSD without and with cardinality constraints, i.e., each cluster should consist of at least N points. For both problems with k ≥ 3 , it is NP-hard to achieve a factor of (1 2 + ϵ) approximation for any ϵ > 0. For k = 2 , we solve the two problems optimally; For k ≥ 3 , we present a 1 2 -approximation and a 1 4 -approximation algorithm for the two problems, respectively. [ABSTRACT FROM AUTHOR]

• Transform the max-bisection problem to a linearly constrained optimization problem. • Propose a deterministic annealing neural network algorithm by introducing a barrier function in square-root form. • Prove the existence of the integral minimum solution of the max-bisection problem in theory and the proof is simpler than other algorithms. • Experimental results show that the proposed method outperforms other methods. The max-bisection problem has extensive applications in network engineering, making it imperative to develop effective methods to solve this problem. However, the efficient computation on this problem remains challenging due to its NP-hard computational complexity. To address this question, in this paper, we transform the max-bisection problem to an artificial linearly constrained optimization problem and develop a modified deterministic annealing neural network algorithm by introducing a barrier function. The barrier parameter of this function acts as the temperature in the annealing process and decreases from a large positive number to zero. The initial value of the barrier parameter promises that the artificial problem is convex and can be easily solved at the beginning of the descending process. The solution to the original max-bisection problem is finally obtained through a descent algorithm, in which the bound limit of the solution is always satisfied as long as the iteration step length is less than one. We have proved the theoretical convergence of the proposed algorithm. Numerical results demonstrate that the proposed algorithm has several advantages over both the approximation algorithms and metaheuristic methods. [ABSTRACT FROM AUTHOR]

The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common one is the receiver-centric, in which the interference of a node p is defined as the number of other nodes whose transmission range covers p. In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized. For the one-dimensional case, we show how to solve the problem optimally in O (n 3) time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

The fair k -median problem is one of the important clustering problems. The current best approximation ratio is 4.675 for this problem with 1-fairness violation, which was proposed by Bercea et al. [APPROX-RANDOM'2019]. To our best knowledge, there is no available approximation algorithm for this problem without any fairness violation in doubling metrics. In this paper, we consider the fair k -median problem in doubling metrics and general metrics. We provide the first QPTAS for the fair k -median problem based on the hierarchical decomposition and dynamic programming process in doubling metrics. For applying a dynamic programming process to solve this problem, the distances from portals to facilities cannot be directly enumerated since each client may not be assigned to its closest open facility. To overcome the difficulties caused by the fairness constraints, we construct an auxiliary graph and use minimum weighted perfect matching to get the cost between the portals of each block and the ones in its children. In order to satisfy the fairness constraints, we bound the fairness constraints of each open facility in the leaves of the split-tree based on the relation between the subproblem and the subproblems of its children. To obtain the assignment of the given instance and remove the fairness violation, we construct a new b -value min-cost max-flow model based on the set of open facilities. For the fair k -median problem in general metrics, we present a polynomial-time approximation algorithm with ratio O (log ⁡ k). Our approximation algorithm for the fair k -median problem in doubling metrics is the first result for the corresponding problem without any fairness violation in doubling metrics. [ABSTRACT FROM AUTHOR]

We consider the problem of maximizing a monotone nondecreasing set function under multiple constraints, where the constraints are also characterized by monotone nondecreasing set functions. We propose two greedy algorithms to solve the problem with provable approximation guarantees. The first algorithm exploits the structure of a special class of the general problem instance to obtain a better time complexity. The second algorithm is suitable for the general problem. We characterize the approximation guarantees of the two algorithms, leveraging the notions of submodularity ratio and curvature introduced for set functions. We then discuss particular applications of the general problem formulation to problems that have been considered in the literature. We validate our theoretical results using numerical examples. [ABSTRACT FROM AUTHOR]

Highlights • An approaximation algorithm for the case with bounded number of divisible resources. • A 6 + 2 10 + ε -approximation algorithm for the case where u ij ∈ {0, u j }. • A polynomial-time approximation algorithm for the general case. Abstract Resource allocation is a classic problem in economics and computer science. The application scenarios of resource allocation include inheritance settlements, computation resource sharing and so on. This paper focuses on the max-min fair allocation of resources in which m resources need to be allocated to n agents while maximizing the minimum utility of any agent. When money transfer is not allowed, the existing work on max-min fair allocation only focuses on the fair allocation of indivisible resources. However, in real applications, the allocated resource set may simultaneously include indivisible resources and divisible resources, e.g., the allocated resources in distributed systems include the indivisible CPU resources, the divisible storage resource and the divisible bandwidth resource. The combination of indivisible resources and divisible resources creates a new challenge and requires us to consider how to coordinate the allocations of indivisible resources and divisible resources in the allocation process. Therefore, we investigate the combined max-min fair allocation problem in which the allocated resource set consists of both indivisible resources and divisible resources. We present a 6+2 10 + ε (ε > 0)-factor approximation algorithm for the restricted case where u ij ∈ {0, u j } (i.e., the utility of a resource j is either 0 or u j for each agent i) and the agent valuations for the divisible resources are in proximity to each other. Moreover, we propose an approximation algorithm for the general case based on the augmented flow idea. Experiments conducted on real data show that the average performance of the proposed approximation algorithm is better than 80% of the performance of the optimal algorithm, which requires exponential time in the worst case unless P = NP. To the best of our knowledge, the proposed algorithm is the first approximation algorithm for the general case of the combined max-min fair allocation problem when money transfer is not allowed. The proposed algorithm can be adopted to design more efficient expert systems that apply to resource allocation in distributed systems, inheritance settlements and so on. The adoption of the proposed algorithm contributes to promoting the broader application of expert systems in the fair allocation of computation resources and social resources. The experimental results show that the proposed algorithm can perform well in real applications. [ABSTRACT FROM AUTHOR]

Highlights • Most prediction problems of data networks are non-linear. • Shallow neural networks are fast. • Kernel approximation is a non-linear data transformation. • Shallow neural networks with kernel approximation are non-linear and fast models. • Proposed model is faster with prediction results comparable to deep models. Abstract Intrusion detection and network traffic classification are two of the main research applications of machine learning to highly demanding data networks e.g. IoT/sensors networks. These applications present new prediction challenges and strict requirements to the models applied for prediction. The models must be fast, accurate, flexible and capable of managing large datasets. They must be fast at the training, but mainly at the prediction phase, since inevitable environment changes require constant periodic training, and real-time prediction is mandatory. The models need to be accurate due to the consequences of prediction errors. They need also to be flexible and able to detect complex behaviors, usually encountered in non-linear models and, finally, training and prediction datasets are usually large due to traffic volumes. These requirements present conflicting solutions, between fast and simple shallow linear models and the slower and richer non-linear and deep learning models. Therefore, the perfect solution would be a mixture of both worlds. In this paper, we present such a solution made of a shallow neural network with linear activations plus a feature transformation based on kernel approximation algorithms which provide the necessary richness and non-linear behavior to the whole model. We have studied several kernel approximation algorithms: Nystrom, Random Fourier Features and Fastfood transformation and have applied them to three datasets related to intrusion detection and network traffic classification. This work presents the first application of a shallow linear model plus a kernel approximation to prediction problems with highly demanding network requirements. We show that the prediction performance obtained by these algorithms is positioned in the same range as the best non-linear classifiers, with a significant reduction in computational times, making them appropriate for new highly demanding networks. [ABSTRACT FROM AUTHOR]

Highlights • The algorithm is on average 20% more efficient (faster). • The algorithm has 511% (158%) (mean, median) faster convergence. • Probability bound is calculated. • The algorithm can potentially have many applications. Abstract It is well known that Minimum Feedback Arc Set is in a general case NP-complete. There are different kinds of exact, heuristic and approximation algorithms for solving this problem, but currently there is only one published Monte Carlo algorithm which solves Minimum Feedback Arc Set in polynomial time with arbitrary probability. To further advance the state of the art we have devised new and improved ant inspired Monte Carlo algorithm which on average has 20% faster empirical running time. Due to a learning mechanism the new algorithm also achieved 511% faster convergence in terms of median and 158% improvement in terms of arithmetic mean. This has been done while at the same time maintaining the ability of the algorithm to find optimal solution with arbitrary probability. In addition, the new and improved ant inspired algorithm has substantially improved convergence consistency. A tighter probability bound has also been calculated for the Monte Carlo algorithm. The aforementioned contributions have their significance in a design and implementation of expert and intelligent system. Considering a wide presence of MFAS in a variety of areas the obtained results are significant in other applications as well. [ABSTRACT FROM AUTHOR]

Abstract We study several variations of line segment covering problem with axis-parallel unit squares in the plane. Given a set S of n line segments, the objective is to find the minimum number of axis-parallel unit squares that cover at least one end-point of each segment. The variations depend on the orientation and length of the input segments. We prove some of these problems to be NP -complete, and give constant-factor approximation algorithms for those problems. For the general version of the problem, where the segments are of arbitrary length and orientation, and the squares are given as input, we propose a 16-approximation algorithm based on multilevel linear programming relaxation technique. More precisely, we reduce this problem to the problem of covering points in the plane by a given set of unit squares using linear programming relaxation technique. A linear programming-based 8-approximation algorithm for the later problem yields a 16-approximation result for the former problem. This technique may be of independent interest in solving some other problems. [ABSTRACT FROM AUTHOR]

Highlights • An EMS station location and sizing problem using distributionlly robust optimization is proposed. • Risk-averse features are considered both quantitatively and qualitatively. • The proposed approximation for joint chance constraints is less conservative compared with individual ones in a special case. • An outer approximation algorithm is developed to solve a standard SOCP in a special case. • More than one facilities are preferred to service a single demand site to ensure system reliability. Abstract An effective Emergency Medical Service (EMS) system can provide medical relief supplies for common emergencies (fire, accident, etc.) or large-scale disasters (earthquake, tsunami, bioterrorism attack, explosion, etc.) and decrease morbidity and mortality dramatically. This paper proposes a distributionally robust model for optimizing the location, number of ambulances and demand assignment in an EMS system by minimizing the expected total cost. The model guarantees that the probability of satisfying the maximum concurrent demand in the whole system is larger than a predetermined reliability level by introducing joint chance constraints and characterizes the expected total cost by moment uncertainty based on a data-driven approach. The model is approximated as a parametric second-order conic representable program. Furthermore, a special case of the model is considered and converted into a standard second-order cone program, which can be efficiently solved with a proposed outer approximation algorithm. Extensive numerical experiments are conducted to illustrate the benefit of the proposed approach. Moreover, a dataset from a real application is also used to demonstrate the application of the data-driven approach. [ABSTRACT FROM AUTHOR]

Highlights • A differential-relation-based rough set model on relational databases is proposed. • Using this model, the measures for differential dependencies (DDs) are expressed. • An efficient method to compute the approximate error measure of g 3 for DDs is developed. • The rough sets on the differential decision systems (DDSs) are introduced. • A bridge between DDs in databases and attribute dependencies in DDSs is formed. Abstract Data dependencies in databases and attribute dependencies in decision systems are important when addressing problems concerning data quality and attribute reduction, in which measures play a significant role in approximating these dependencies to achieve better adaptation to uncertain data. This paper proposes a differential-relation-based rough set model from the perspective of relational databases to express the dependency degree, error measures, confidence, information granulation and differential class distance for differential dependencies (DDs) and the relationships among them in a unified framework. Moreover, the error measure g 3 has been widely studied and applied for data dependencies. However, the computation of g 3 for DDs is NP-complete. Therefore, based on the proposed rough set, we introduce a new method that can compute the approximate error measure g 3 ˜ of g 3 in polynomial time. This study demonstrates that our approach can provide a substantially better approximation, that is, an approximation closer to the optimal solution g 3 , compared to the existing greedy method. We also introduce the differential-relation-based rough set from the perspective of information systems and make a connection to the rough sets induced by non-equivalence relations. The two views of the differential-relation-based rough sets form an essential bridge between the DDs in databases and attribute dependencies in differential decision systems (DDSs) that allows sharing measures for approximating the dependencies. These results are meaningful for approximate computations, the development of algorithms for attribute reduction in decision systems and the discovery of approximate differential dependencies (ADDs) in databases. [ABSTRACT FROM AUTHOR]

Abstract A partition (C 1 , C 2 , ... , C q) of G = (V , E) into clusters of strong (respectively, weak) diameter d , such that the supergraph obtained by contracting each C i is ℓ -colorable is called a strong (resp., weak) (d , ℓ) -network-decomposition. Network-decompositions were introduced in a seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. Awerbuch et al. showed that strong (d , ℓ) -network-decompositions with d = ℓ = exp ⁡ { O (log ⁡ n log ⁡ log ⁡ n) } can be computed in distributed deterministic time O (d). Even more importantly, they demonstrated that network-decompositions can be used for a great variety of applications in the message-passing model of distributed computing. The result of Awerbuch et al. was improved by Panconesi and Srinivasan in 1992: in the latter result d = ℓ = exp ⁡ { O (log ⁡ n) } , and the running time is O (d) as well. In another remarkable breakthrough Linial and Saks (in 1992) showed that weak (O (log ⁡ n) , O (log ⁡ n)) -network-decompositions can be computed in distributed randomized time O (log 2 ⁡ n). Much more recently Barenboim (2012) devised a distributed randomized constant-time algorithm for computing strong network decompositions with d = O (1). However, the parameter ℓ in his result is O (n 1 / 2 + ϵ). In this paper we drastically improve the result of Barenboim and devise a distributed randomized constant-time algorithm for computing strong (O (1) , O (n ϵ)) -network-decompositions. As a corollary we derive a constant-time randomized O (n ϵ) -approximation algorithm for the distributed minimum coloring problem, improving the previously best-known O (n 1 / 2 + ϵ) approximation guarantee. We also derive other improved distributed algorithms for a variety of problems. Most notably, for the extremely well-studied distributed minimum dominating set problem currently there is no known deterministic polylogarithmic-time algorithm. We devise a deterministic polylogarithmic-time approximation algorithm for this problem, addressing an open problem of Lenzen and Wattenhofer (2010). [ABSTRACT FROM AUTHOR]

Abstract We present a (1 + 3 + ϵ) -approximation algorithm for the k -median problem with uniform penalties, extending the recent result by Li and Svensson for the classical k -median problem without penalties. One important difference of this work from that of Li and Svensson is a new definition of sparse instance to exploit the combinatorial structure of our problem. [ABSTRACT FROM AUTHOR]

Created by Zadeh in 1965, Fuzzy Set Theory (FST) has been continuously developed in the past five decades and has established itself one of the preeminent approximate reasoning methodologies. In the literature, there exists multitudes of differing approaches for specifying FST's foundational building blocks (such as the various versions of fuzzy set and arithmetic operators) that it has become challenging for an FST user (e.g. an otherwise proficient engineer who is not an expert in fuzzy set theory) to select or tailor-make fuzzy operators truly appropriate for solving his/her problems. In a recent work (Ngan, 2017a), within the type-1 fuzzy setting, a framework termed probabilistic linguistic computing (PLC) has been proposed to empower such type of FST users to understand and dissect fuzzy operators available in the literature, and to tailor-make their own fuzzy operators to solve their own application problems. In this article, we will revisit this work and extend it to the general type-2 fuzzy setting, as well as to other type-2-like fuzzy settings. Among the contributions are: (i) we demonstrate that the generalized PLC framework can indeed provide a concrete, accessible pathway for the FST users to understand and tailor-make their own set operators in the type-2 and type-2-like fuzzy settings – this is distinct from many other theoretical studies within the type-2 fuzzy set (T2FS) literature which primarily focus on deep technical developments while offering virtually no accessible guidelines for the FST users to use T2FS in their applications; (ii) the set operators constructed from the proposed approach are computationally simple and efficient; and (iii) the proposed approach offers a straightforward way to understand the logical relations between set operators for the general type-2 fuzzy sets and those for type-2-like fuzzy sets. [ABSTRACT FROM AUTHOR]

Optimization is one of the research areas where quantum computing could bring significant benefits. In this scenario, a hybrid quantum–classical variational algorithm, the Quantum Approximate Optimization Algorithm (QAOA), is receiving much attention for its potential to efficiently solve combinatorial optimization problems. This approach works by using a classical optimizer to identify appropriate parameters of a problem-dependent quantum circuit, which ultimately performs the optimization process. Unfortunately, learning the most appropriate QAOA circuit parameters is a complex task that is affected by several issues, such as search landscapes characterized by many local optima. Moreover, gradient-based optimizers, which have been pioneered in this context, tend to waste quantum computing resources. Therefore, gradient-free approaches are emerging as promising methods to address this parameter-setting task. Following this trend, this paper proposes, for the first time, the use of genetic algorithms as gradient-free methods for optimizing the QAOA circuit. The proposed evolutionary approach has been evaluated in solving the MaxCut problem for graphs with 5 to 9 nodes on a noisy quantum device. As the results show, the proposed genetic algorithm statistically outperforms the state-of-the-art gradient-free optimizers by achieving solutions with a better approximation ratio. • A genetic algorithm is proposed to optimize the gate parameters of QAOA. • The QAOA optimized by a genetic algorithm is applied to solve the MaxCut problem. • The proposed genetic algorithm outperforms state-of-the-art gradientfree methods. [ABSTRACT FROM AUTHOR]

The present paper is devoted to recovering the source term and the initial data simultaneously for a time-fractional diffusion equation from additional temperature data at two fixed times t = T 1 and t = T 2 . Firstly, we prove the uniqueness result for the direct problem. And then we apply a non-stationary iterative Tikhonov regularization method to solve the inverse problem and propose a finite dimensional approximation algorithm. Three numerical examples in both one-dimensional and two-dimensional cases are provided to demonstrate the effectiveness and feasibility of the proposed method. [ABSTRACT FROM AUTHOR]

In this article, we employ Nyström method with locally linear embedding (LLE) to approximate the node location and develop an iterative localization technique for accurate node localization. Initially, a group of three adjacent anchor nodes forms a reference structure and nodes in one hop neighborhood of this reference structure are localized using LLE. After this, remaining sensor nodes are localized using Nyström extended LLE. Experimental results show that the proposed Nyström extended LLE (NLLE) is able to localize the nodes accurately for different value of anchors, connectivity and varying size of the neighborhood. It is also observed that the NLLE is able to localize sensor nodes with an increased accuracy at low cost as compared to existing manifold learning techniques. [ABSTRACT FROM AUTHOR]

Topic model is a practical method for learning interpretable models of text corpora and have become a key problem of document representation. Some recently proposed topic models incorporate the intrinsic geometrical information of the document manifold and yield a discriminative topic representation. However, the existing manifold-inspired topic models fail to provide the probability weighting information of local geometrical pattern, thus leads to a limitation to estimate intrinsic semantic information of topic representation. In this paper, we consider the problem of topic modeling with intrinsic structure of document manifold and propose an unsupervised AutoEncoder-based topic modeling framework, named locally weighted embedding topic model (LWE-TM). Different from existing manifold-inspired topic models, LWE-TM defines a group of probability coefficients to uncover the local geometrical pattern by the Markov random walk structure of affinity graph, and regularizes the training of sparse AutoEncoder (sAE) to explicitly recover such local geometrical pattern with the topics encoding. Under the regularized training framework, the encoding network becomes local-invariant around the neighborhood of the document manifold and enable us to perform a readily topic inference for out-of-sample documents, efficiently improving the generalization and discrimination of topics encoding. The experimental results on two widely-used corpus demonstrate the superiority of LWE-TM to comparative models in document modeling, document clustering and classification tasks. [ABSTRACT FROM AUTHOR]

Feature selection is an effective pre-processing step to remove possible redundant and irrelevant features for various machine learning paradigms, which can help build a more understandable machine learning based component in hybrid expert systems. Single-label quadratic programming feature selection (QPFS) model is formulated as a QP problem with a unit simplex constraint to both minimize feature-feature redundancy and maximize feature-label relevance simultaneously. Since its redundancy matrix is desired not to be positive semi-definite and then estimated by Nystrom low-rank approximation method, its performance depends greatly on under-sampling rate and random permutation. In this paper, without any approximation, we extend this model to construct a regularized version (rQPFS), resulting in a strictly convex QP problem, to achieve a globally optimal subset of features. To reduce the increment of computational time for entire redundancy matrix, Frank–Wolfe method with a sub-linear convergence rate and its special cases for strictly convex function and unit simplex constraint are applied to solve our rQPFS efficiently. Furthermore, to tackle multi-label FS paradigm, pruned problem transformation trick is used to evaluate feature-label relevance to describe label correlations sufficiently. The detailed experimental study on eight data sets shows that our proposed method performs the best, compared with six state-of-the-art multi-label FS methods, according to six instance-based performance evaluation measures. [ABSTRACT FROM AUTHOR]

Learning from imbalanced datasets is a frequent but challenging task for standard classification algorithms. Although there are different strategies to address this problem, methods that generate artificial data for the minority class constitute a more general approach compared to algorithmic modifications. Standard oversampling methods are variations of the SMOTE algorithm, which generates synthetic samples along the line segment that joins minority class samples. Therefore, these approaches are based on local information, rather on the overall minority class distribution. Contrary to these algorithms, in this paper the conditional version of Generative Adversarial Networks (cGAN) is used to approximate the true data distribution and generate data for the minority class of various imbalanced datasets. The performance of cGAN is compared against multiple standard oversampling algorithms. We present empirical results that show a significant improvement in the quality of the generated data when cGAN is used as an oversampling algorithm. [ABSTRACT FROM AUTHOR]

We present a study of the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, which is a restricted version of the Discrete Unit Disk Cover (DUDC) problem. For the WSDUDC problem, there exist a set of points and a set of unit disks in the plane, and the points and disk centres are confined to a strip of fixed width. An optimal solution to the WSDUDC problem is a subset of the disks of minimum cardinality that covers all points in the input set. We describe two approximation algorithms for the problem: a 3-approximate algorithm which applies for strips of width at most 0.8 units, and a general scheme for any strip with less than unit width. We prove that the WSDUDC problem is NP -hard on strips of any fixed width, which is our most interesting result from a theoretical standpoint. The result is also quite surprising, since a number of similar problems are tractable on strips of fixed width. Finally, we discuss how these results may be applied to known DUDC approximation algorithms. [ABSTRACT FROM AUTHOR]

The p -center problem is finding the location of p facilities among a set of n demand points such that the maximum distance between any demand point and its nearest facility is minimized. In this paper, we study this problem in the context of uncertainty, that is, the location of the demand points may change in a region like a disk or a segment, or belong to a finite set of points. We introduce Max- p -center and Min- p -center problems which are the worst and the best possible solutions for the p -center problem under such locational uncertainty. We propose approximation and parameterized algorithms to solve these problems under the Euclidean metric. Further, we study the MinMax Regret 1-center problem under uncertainty and propose a linear-time algorithm to solve it under the Manhattan metric as well as an O (n 4) time algorithm under the Euclidean metric. [ABSTRACT FROM AUTHOR]

The art gallery problem is a classical sensor placement problem that asks for the minimum number of guards required to see every point in an environment. The standard formulation does not take into account self-occlusions caused by a person or an object within the environment. Obtaining good views of an object from all orientations despite self-occlusions is an important requirement for surveillance and visual inspection applications. We study the art gallery problem under a constraint, termed △-guarding, that ensures that all sides of any convex object are always visible in spite of self-occlusion. Our contributions in this paper are three-fold: We first prove that Ω ( n ) guards are always necessary for △-guarding the interior of a simple polygon having n vertices. Second, we present a O ( log ⁡ c opt ) factor approximation algorithm for △-guarding polygons with or without holes, when the guards are restricted to vertices of the polygon. Here, c opt is the optimal number of guards. Third, we study the problem of △-guarding a set of line segments connecting points on the boundary of the polygon. This is motivated by applications where an object or person of interest can only move along certain paths in the polygon. We present a constant factor approximation algorithm for this problem – one of the few such results for art gallery problems. [ABSTRACT FROM AUTHOR]

Suppose n colored points with k colors in R d are given. The Smallest Color-Spanning Ball ( SCSB ) is the smallest ball containing at least one point of each color. As the computation of the SCSB in L p metric ( p ≥ 1 ) is time-consuming, we focus on approximately computing the SCSB in near-linear time. Initially, we propose a 3-approximation algorithm running in O ( n log ⁡ n ) time. This algorithm is then utilized to present a ( 1 + ε ) -approximation algorithm with the running time of O ( ( 1 ε ) d n log ⁡ n ) . We improve the running time to O ( ( 1 ε ) d n ) using randomized techniques. Afterward, spanning colors with two balls is studied. For a special case where d = 1 , there is an algorithm with O ( n 2 ) time. We demonstrate that for any ε > 0 under the assumption that SETH is true, no approximation algorithm running in O ( n 2 − ε ) time exists for the problem even in one-dimensional space. Nevertheless, we consider the L ∞ metric where a ball is an axis-parallel hypercube and present a ( 1 + ε ) -approximation algorithm running in O ( ( 1 ε ) 2 d ( n 2 k ) log 2 ⁡ n ) time which is remarkable when k is large. This time can be reduced to O ( ( 1 ε ) n 2 k log ⁡ n ) when d = 1 . [ABSTRACT FROM AUTHOR]

We study the problem of permuting each column of a given matrix to achieve minimum maximal row sum or maximum minimal row sum, a problem of interest in probability theory and quantitative finance where quantiles of a random variable expressed as the sum of several random variables with unknown dependence structure are estimated. If the minimum maximal row sum is equal to the maximum minimal row sum the matrix has been termed jointly mixable (see e.g. Haus (2015), Wang and Wang (2015), Wang et al. (2013)). We show that the lack of joint mixability (the joint mixability gap) is not significant, i.e., the gap between the minimum maximal row sum and the maximum minimal row sum is either zero or one for a class of integer matrices including binary and complete consecutive integers matrices. For integer matrices where all entries are drawn from a given set of discrete values, we show that the gap can be as large as the difference between the maximal and minimal elements of the discrete set. The aforementioned result also leads to a polynomial-time approximation algorithm for matrices with restricted domain. Computing the gap for a { 0 , 1 , 2 } -matrix is proved to be equivalent to finding column permutations minimizing the difference between the maximum and minimum row sums. A polynomial procedure for computing the optimum difference by solving the maximum flow problem on an appropriate graph is given. [ABSTRACT FROM AUTHOR]

We consider the problem of partitioning interval graphs into cliques of bounded size. Each interval has a weight, and the weight of a clique is the maximum weight of any interval in the clique. The goal is then to find such a partition of minimum total weight. This graph problem can also be interpreted as a batch scheduling problem. Solving a long-standing open question, we show NP-hardness, even if the bound on the clique sizes is constant. Moreover, we give a PTAS for this case. [ABSTRACT FROM AUTHOR]

We consider k -envy-free assignments for scheduling problems in which the completion time of each machine is not k times larger than the one she could achieve by getting the jobs of another machine, for a given factor k ≥ 1 . We introduce and investigate the notion of price of k -envy-freeness, defined as the ratio between the makespan of the best k -envy-free assignment and that of an optimal allocation achievable without envy-freeness constraints. We provide exact or asymptotically tight bounds on the price of k -envy-freeness for all the basic scheduling models, that is unrelated, related and identical machines. Moreover, we show how to efficiently compute such allocations with a worsening multiplicative factor being at most the best approximation ratio for the minimum makespan problem guaranteed by a polynomial time algorithm for each specific model. Finally, we extend our results to the case of restricted assignments and to the objective of minimizing the sum of the completion times of all the machines. [ABSTRACT FROM AUTHOR]

Locating source of diffusion in networks is crucial for controlling and preventing epidemic risks. It has been studied under various probabilistic models. In this paper, we study source location from a deterministic point of view by modeling it as the minimum cost doubly resolving set (DRS) problem, which is a strengthening of the well-known metric dimension problem. Let G be an undirected graph on n vertices, where each vertex has a nonnegative cost. A vertex subset S of G is a doubly resolving set (DRS) of G if for every pair of vertices u , v in G , there exist x , y ∈ S such that the difference of distances (in terms of number of edges) between u and x , y is not equal to the difference of distances between v and x , y . The minimum cost DRS problem consists of finding a DRS in G with minimum total cost. We establish Θ ( ln ⁡ n ) approximability of the minimum DRS problem on general graphs for both weighted and unweighted versions. This provides the first explicit lower and upper bounds on approximation for the minimum (cost) DRS, which are nearly tight. Moreover, we design the first known strongly polynomial time exact algorithms for the minimum cost DRS problem on general wheels and trees with additional constant k ≥ 0 edges. [ABSTRACT FROM AUTHOR]

In large wireless multi-hop networks, routing is a main issue as they include many nodes that span over relatively a large area. In such a scenario, finding smallest set of dominant nodes for forwarding packets would be a good approach for better communication. Connected dominating set (CDS) computation is one of the method to find important nodes in the network. As CDS computation is an NP problem, several approximation algorithms are available but these algorithms have high message complexity. This paper discusses the design and implementation of a distributed algorithm to compute connected dominating sets in a wireless network with the help of network spectral properties. Based on local neighborhood, each node in the network finds its ego centric network. To identify dominant nodes, it uses bridge centrality value of ego centric network. A distributed algorithm is proposed to find nodes to connect dominant nodes which approximates CDS. The algorithm has been applied on networks with different network sizes and varying edge probability distributions. The algorithm outputs 40% important nodes in the network to form back haul communication links with an approximation ratio ≤ 0.04 * ∂ + 1, where ∂ is the maximum node degree. The results confirm that the algorithm contributes to a better performance with reduced message complexity. [ABSTRACT FROM AUTHOR]

Let G be a graph in which each vertex v has a positive integer weight b ( v ) and each edge ( v , w ) has a nonnegative integer weight b ( v , w ) . A bandwidth consecutive multicoloring, simply called a b -coloring of G , assigns each vertex v a specified number b ( v ) of consecutive positive integers as colors of v so that, for each edge ( v , w ) , all integers assigned to vertex v differ from all integers assigned to vertex w by more than b ( v , w ) . The maximum integer assigned to vertices is called the span of the coloring. The b -coloring problem asks to find a b -coloring of a given graph G with the minimum span. In the paper, we present four efficient approximation algorithms for the problem, which have theoretical performance guarantees for the computation time, the span of a found b -coloring and the approximation ratio. We also obtain several upper bounds on the minimum span, expressed in terms of the maximum b -degrees, one of which is an extension of Brooks' theorem on an ordinary coloring. [ABSTRACT FROM AUTHOR]

We consider a version of parallel machine scheduling with rejection. An instance of the problem is given by m identical parallel machines and a set of n independent jobs, with each job having a processing time and a penalty. A job may be accepted to be processed or be rejected at its penalty. The objective of the problem is to partition the set of jobs into two subsets, the subset of accepted and the subset of rejected jobs, and to schedule the set of accepted jobs such that the makespan is minimized under the constraint that the total penalty of the rejected jobs is no more than a given bound. In this paper, we present a 2-approximation algorithm within strongly polynomial time for the problem. We also present a polynomial time approximation scheme whose running time is O ( n m O ( 1 ϵ 2 ) + mn 2 ) for the problem. Moreover, for the case where the number of machines is a fixed constant m , our results lead to a fully polynomial time approximation scheme for the problem. Our result is fairly good in the sense that in a reasonable size of jobs, our FPTAS improves previous best running time from O ( n m + 2 / ϵ m ) to O ( 1 / ϵ 2 m + 3 + mn 2 ) . [ABSTRACT FROM AUTHOR]

Sorting genomes by translocations is a classic combinatorial problem in genome rearrangements. The translocation distance for signed genomes can be computed exactly in polynomial time, but for unsigned genomes the problem becomes NP-hard and the current best approximation ratio is 1.5 + ε . In this paper, we investigate the problem of sorting unsigned genomes by translocations. Firstly, we propose a tighter lower bound of the optimal solution by analyzing some special sub-permutations; then, by exploiting the two well-known algorithms for approximating the maximum independent set on graphs with a bounded degree and for set packing with sets of bounded size, we devise a new polynomial-time approximation algorithm, improving the approximation ratio to 1.408 + ε , where ε = O ( 1 / log ⁡ n ) . [ABSTRACT FROM AUTHOR]

The Multiple Cluster Scheduling Problem corresponds to minimizing the maximum completion time (makespan) of a set of n parallel rigid (and non-preemptive) jobs submitted to N identical clusters. It cannot be approximated with a ratio better than 2 (unless P = NP ). We present in this paper the methodology that encompasses several existing results [1,2] . We detail first how to apply it for obtaining a 5 2 -approximation. Then, we use it to provide a new 7 3 -approximation running in O ( log ⁡ ( n h max ) N ( n + log ⁡ ( n ) ) ) , where h max is the processing time of the longest job. Finally, we apply it to a restriction of the problem to jobs of limited size, leading to a 2-approximation which is the best possible ratio since the restriction remains 2-inapproximable. [ABSTRACT FROM AUTHOR]

We study the Stackelberg/bilevel knapsack problem as proposed by Chen and Zhang [1] : Consider two agents, a leader and a follower. Each has his own knapsack. (Knapsack capacities are possibly different.) As usual, there is a set of items i = 1 , … , n of given weights w i and profits p i . It is allowed to pack item i into both knapsacks, but in this case the corresponding profit for each player becomes p i + a i , where a i is a given (positive or negative) number. The objective is to find a packing for the leader such that the total profit of the two knapsacks is maximized, assuming that the follower acts selfishly. We present tight approximation algorithms for all settings considered in [1] . [ABSTRACT FROM AUTHOR]

The traditional approach for the problems of sorting permutations by rearrangements is to consider that all operations have the same unitary cost. In this case, the goal is to find the minimum number of allowed rearrangements that are needed to sort a given permutation, and numerous efforts have been made over the past years regarding these problems. On the other hand, a long rearrangement (which is in fact a mutation) is more likely to disturb the organism. Therefore, weights based on the length of the segment involved may have an important role in the evolutionary process. In this paper we present the first results regarding problems of sorting permutations by length-weighted operations that consider rearrangement models with prefix and suffix variations of reversals and transpositions, which are the two most common types of genome rearrangements. Our main results are O ( lg 2 ⁡ n ) -approximation algorithms for 10 such problems. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling jobs in batches on a single machine where the processing time of each job is a simple increasing linear function of its waiting time, i.e., the time between the starting time of processing the batch to which the job belongs and the starting time of processing of the job. The objective is to minimize the sum of the total job flow time and the batching cost. We first show that the case with a given number of batches is strongly NP-hard and we present a fully polynomial-time approximation scheme (FPTAS) for this case. We then show that the case with an arbitrary number of batches is also strongly NP-hard and there is no polynomial-time approximation algorithm with a constant upper bound for this case unless P = NP . [ABSTRACT FROM AUTHOR]

This paper considers a three-stage flexible flow shop scheduling problem, where the jobs have the group constraint at the second stage and the three stages consist of unrelated parallel machines. Because of the complexity of this problem, approximation algorithms are more appropriate to solve it. Firstly, we propose ten heuristic algorithms based on the idea of combined algorithms proposed by Soewandi and Elmaghraby (2001) and give their time complexities. Secondly, since there is no reference on the worst-case performance ratios of RDM, SP.H1 and SP.H2 algorithms for the unrelated parallel machines, we provide the worst-case performance ratios of these three algorithms and then give the worst-case performance ratios of the nine algorithms proposed in this paper. Finally, to evaluate the performance of the ten algorithms, four lower bounds of this problem are proposed in Appendix A and a computational experiment is designed, where lots of instances are generated and each algorithm is run with every instance. Experimental results indicate that the performances of ten heuristic algorithms are contingent on different configurations and SP.JH-MJ algorithm generally outperforms the others with respect to the three-stage flexible flow shop scheduling problem addressed in this paper. [ABSTRACT FROM AUTHOR]

Some hard-to solve combinatorial problems of finding several disjoint discrete structures in complete weighted graph are considered. Efficient algorithms with performance guarantees are constructed for the Euclidean m -Peripatetic Salesman Problem, m -Weighted Clique Problem and m -Layer Planar three-index Assignment Problem. [ABSTRACT FROM AUTHOR]

The capacitated K-center (CKC) problem calls for locating K service centers in the vertices of a given weighted graph, and assigning each vertex as a client to one of the centers, where each service center has a limited service capacity and thus may be assigned at most L clients, so as to minimize the maximum distance from a vertex to its assigned service center. This paper studies the fault-tolerant version of this problem, where one or more service centers might fail simultaneously. We consider two variants of the problem. The first is the α-fault-tolerant capacitated K-center ( α - F T - C K C ) problem. In this version, after the failure of some centers, all nodes are allowed to be reassigned to alternate centers. The more conservative version of this problem, hereafter referred to as the α-fault-tolerant conservative capacitated K-center ( α - F T - C K C ) problem, is similar to the α - F T - C K C problem, except that after the failure of some centers, only the nodes that were assigned to those centers before the failure are allowed to be reassigned to other centers. We present polynomial time algorithms that yield 9-approximation for the α - F T - C K C problem and 17-approximation for the α - F T - C K C problem. [ABSTRACT FROM AUTHOR]

In this paper a class of combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing K distinct cost scenarios. The Ordered Weighted Averaging (OWA for short) aggregation operator is applied to choose a solution. Some well known criteria used in decision making under uncertainty such as the maximum, minimum, average, Hurwicz and median are special cases of OWA. Furthermore, by using OWA, the traditional robust (min–max) approach to combinatorial optimization problems with uncertain costs can be generalized. The computational complexity and approximability of the problem of minimizing OWA for the considered class of problems are investigated and some new positive and negative results in this area are provided. These results remain valid for many basic problems, such as network or resource allocation problems. [ABSTRACT FROM AUTHOR]

In this paper, we present a new algorithm for the Sorting by Prefix Reversals and Prefix Transpositions Problem. The previous approximation algorithm was bounded by factor 3, and here we present an asymptotic 2-approximation algorithm. We consider theoretical and practical aspects in our analysis, and we show that our method is better than other approaches in both cases. [ABSTRACT FROM AUTHOR]

We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed s then the energy consumption is sα units of energy per time unit, where α > 1 is a small constant. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption to be minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances: (i) equal-work jobs on a single-processor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case. [ABSTRACT FROM AUTHOR]