Search

Online social network has deeply changed our lives, such as the style of communication and business, and hence promotes a lot of researches in social influence. The prior works in social influence mainly consider the influence from the view of individuals. However, in many cases, influencing the most of members of an important group such as the board of directors in a company can bring bigger profit than directly influencing the individuals of the company. We call such high profit group which obeys the vote rule as an union, different from existed targeted influence model, we consider such scenarios to make union acceptable and propose the union acceptable profit problem (UAPM) to choose seeds to maximize the union-acceptable profit, i.e., maximize the probability of the union being acceptable. The objective of profit in UAPM is #P-hard, and not submodularity or supmodularity. To solve the problem, we propose an efficient estimation method for the objective and design a heuristic algorithm and further a data-driven β (1 − 1 ϵ) -approximation algorithm where β is the data-driven parameter which is related to the input data. At last we evaluate the performance of the algorithms we proposed on effectiveness and efficiency by the experiments in real-world social network datasets. • We formulate a new problem of UAPM which proved to be hard to solve. • An efficient estimation method for the objective is proposed based on an optimized sampling algorithm. • We propose a heuristic algorithm and a data-driven approximation algorithm respectively to solve the problem. • Experiments with the real-world databases validate the effectiveness of our algorithms. [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]

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

We study the approximation capabilities of two families of univariate polynomials that arise in applications of quantum signal processing. Although approximation only in the domain [ 0 , 1 ] is physically desired, these polynomial families are defined by bound constraints not just in [ 0 , 1 ] , but also with additional bound constraints outside [ 0 , 1 ]. One might wonder then if these additional constraints inhibit their approximation properties within [ 0 , 1 ]. The main result of this paper is that this is not the case — the additional constraints do not hinder the ability of these polynomial families to approximate arbitrarily well any continuous function f : [ 0 , 1 ] → [ 0 , 1 ] in the supremum norm, provided f also matches any polynomial in the family at 0 and 1. We additionally study the specific problem of approximating the step function on [ 0 , 1 ] (with the step from 0 to 1 occurring at x = 1 2 ) using one of these families, and propose two subfamilies of monotone and non-monotone approximations. For the non-monotone case, under some additional assumptions, we provide an iterative heuristic algorithm that finds the optimal polynomial approximation. [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]

In this paper, the problem of optimal assignment of trailer-mounted steam generators for cyclic steam stimulation (CSS) of petroleum wells is formulated as a parallel uniform machines scheduling (PMS) problem with release dates. The total weighed tardiness is used as the goal of the optimization process. The distinctive features of the proposed PMS formulation include: jobs with variable weights, variable machine setup time, constraint capacity of drilling pads (where machines are allocated), and modified tardiness criterion. A two-stage scheduling algorithm combining heuristic and genetic algorithms is proposed for solving it. A chromosome representation, crossover and mutation operators generating only feasible solutions and thus avoiding the use of any repair mechanism are discussed. The performance of the algorithm is tested on a real-world data set from the oilfield asset located in the coastal swamps of the Gulf of Mexico. The experiments indicate that the proposed approach gives good results in optimization of the operational costs and petroleum recovery. The algorithm is implemented as a part of the software platform for optimization of CSS and currently is in use by oilfield engineers. [ABSTRACT FROM AUTHOR]

The minimum vertex cover problem (MVCP) and minimum weighted vertex cover problem (MWVCP) have been used in a variety of applications. This paper focuses on a view of test-cost-sensitive rough set for MWVCP. We first provide a method to convert a minimum weight vertex cover of a graph into a minimal test cost attribute reduct of a test-cost-sensitive decision table. Then, an induced test-cost-sensitive decision table from an undirected weighted graph is established. On the foundation of the induced decision table, an improved heuristic algorithm for finding minimum weight vertex covers is proposed, it can avoid a mass of redundant computation. Furthermore, to improve efficiency, a quantum-behaved particle swarm optimization with immune mechanism is presented, which can avoid the phenomenon of premature, improve the global searching ability, and enhance the convergence speed. The results of the experiment show the advantages and limitations of the proposed algorithms compared with state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Using the characteristic property of chordal graphs that they are the intersection graphs of subtrees of a tree, Erich Prisner showed that every chordal graph admits an eccentricity 2 -approximating spanning tree. That is, every chordal graph G has a spanning tree T such that e c c T ( v ) − e c c G ( v ) ≤ 2 for every vertex v , where e c c G ( v ) ( e c c T ( v ) ) is the eccentricity of a vertex v in G (in T , respectively). Using only metric properties of graphs, we extend that result to a much larger family of graphs containing among others chordal graphs, the underlying graphs of 7-systolic complexes and plane triangulations with inner vertices of degree at least 7. Furthermore, based on our approach, we propose two heuristics for constructing eccentricity k -approximating trees with small values of k for general unweighted graphs. We validate those heuristics on a set of real-world networks and demonstrate that all those networks have very good eccentricity approximating trees. [ABSTRACT FROM AUTHOR]

Heuristic Retrieval (HR) task aims to retrieve a set of documents from which the External Plagiarism detection identifies plagiarized pieces of text. In this context, we present Minmax Circular Sector Arcs ( MinmaxCSA ) algorithms that treats HR task as an approximate k -nearest neighbor search problem. Moreover, MinmaxCSA algorithms aim to retrieve the set of documents with greater amounts of plagiarized fragments, while reducing the amount of time to accomplish the HR task. Our theoretical framework is based on two aspects: (i) a triangular property to encode a range of sketches on a unique value; and (ii) a Circular Sector Arc property which enables (i) to be more accurate. Both properties were proposed for handling high-dimensional spaces, hashing them to a lower number of hash values. Our two MinmaxCSA methods, Minmax Circular Sector Arcs Lower Bound ( CSA L ) and Minmax Circular Sector Arcs Full Bound ( CSA ), achieved Recall levels slightly more imprecise than Minmaxwise hashing in exchange for a better Speedup in document indexing and query extraction and retrieval time in high-dimensional plagiarism-related datasets. [ABSTRACT FROM AUTHOR]

We consider the variant of the Two-Dimensional Bin Packing Problem in which items have to be obtained by a series of guillotine cuts and cannot be rotated. We present a heuristic algorithm based on partial enumeration, and computationally evaluate its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases. [ABSTRACT FROM AUTHOR]

This paper considers the laser-charged Unmanned Aerial Vehicle (UAV) assisted Wireless Rechargeable Sensor Network (WRSN), where rechargeable sensors are deployed in surveillance environment to monitor information, a UAV is not only used as aerial wireless mobile collector for gathering data from sensors but also used as mobile charger to replenish energy for sensors, Laser Beam Directors (LBDs) are uniformly deployed in the monitoring environment to charge UAV by emitting laser beams. In such network, we study the average Age of Information Optimization (AoIO) problem whose objective is to minimize the average AoI of data collected from sensors such that all data of the network are transported to the base station and the remaining energy of any sensor exceeds a certain threshold. We prove that the AoIO problem is NP-hard. To solve the AoIO problem, we first study the Total Flight Time Minimizing of UAV (TFTM) problem, which aims at finding an optimal charging solution of UAV to minimize the flight time of UAV based on the order of sensors visited by UAV. Then we prove that the TFTM problem is also NP-hard. Afterwards, we propose a heuristic algorithm to solve the TFTM problem by optimizing flight path, data collection, energy power transfer and laser charging of UAV. Based on the solution for the TFTM problem, we propose an approximation algorithm to solve the AoIO problem. Finally, we conduct extensive simulation experiments to verify the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Understanding a social network is a fundamental problem in social network analysis because of its numerous applications. Recently, user engagement in networks has received extensive attention from many research groups. However, most user engagement models focus on global user engagement to maximize (or minimize) the number of engaged users. In this study, we formulate the so-called L ocal U ser E ngagement M aximization (LUEM) problem. We prove that the LUEM problem is NP-hard. To obtain high-quality results, we propose an approximation algorithm that incorporates a traditional hill-climbing method. To improve efficiency, we propose an efficient pruning strategy while maintaining effectiveness. In addition, by observing the relationship between the degree and user engagement, we propose an efficient heuristic algorithm that preserves effectiveness. Finally, we conducted extensive experiments on ten real-world networks to demonstrate the superiority of the proposed algorithms. We observed that the proposed algorithm achieved up to 605% more engaged users compared to the best baseline algorithms. [ABSTRACT FROM AUTHOR]

Various recent theoretical studies have achieved considerable progress in understanding combined link scheduling and power control in wireless networks with SINR constraints. These analyses were mainly focused on designing and analyzing approximation algorithms with provable approximation guarantees. While these studies revealed interesting effects from a theoretical perspective, so far there has not been a systematic evaluation of the theoretical results in simulations. In this paper, we examine the performance of various approximation algorithms and heuristics for the common scheduling problems on instances generated by different random network models, e.g., taking clustering effects into account. Using (mixed) integer linear programming, we are able to compute the theoretical optima for some of these instances such that the performance of the different algorithms can be compared with these optima. The simulations support the practical relevance of the theoretical findings. For example, setting transmission powers by a square-root power assignment, the network's capacity increases significantly in comparison to uniform power assignments. Furthermore, the developed approximation algorithms are able to exploit this gap providing in general a better performance than any algorithm using uniform transmission powers, even with unlimited computational power. The obtained results are robust against changes in parameters and network generation models. [ABSTRACT FROM AUTHOR]

Abstract: In the minimum common string partition problem one is given two strings S and T with the same character statistics and one seeks for the smallest partition of S into substrings so that T can also be partitioned into the same substring multiset. The problem is fundamental in several variants of edit distance with block operations, e.g. signed reversal distance with duplicates and edit distance with moves. The minimum common string partition problem is known to be NP-complete and the best approximation algorithm known has an approximation factor of . Since the minimum common string partition problem is of utmost practical importance one seeks a heuristic that will (1) usually have a low approximation factor and (2) will run fast. A simple greedy algorithm is known, which iteratively choose non-overlapping longest common substrings of the input strings. This algorithm has been well-studied from an approximation point of view and it has been shown to have a bad worst case approximation factor. However, all the bad approximation factors presented so far stem from complicated recursive construction. In practice the greedy algorithm seems to have small approximation factors. However, the best current implementation of greedy runs in quadratic time. We propose a novel method to implement greedy in linear time. [Copyright &y& Elsevier]

Abstract: All-Optical Label Switching (AOLS) is a new technology that performs packet forwarding without any optical–electrical–optical conversions. In this paper, we study the problem of routing a set of requests in AOLS networks using GMPLS technology, with the aim of minimizing the number of labels required to ensure the forwarding. We first formalize the problem by associating to each routing strategy a logical hypergraph, called a hypergraph layout, whose hyperarcs are dipaths of the physical graph, called tunnels in GMPLS terminology. We define a cost function for the hypergraph layout, depending on its total length plus its total hop count. Minimizing the cost of the design of an AOLS network can then be expressed as finding a minimum cost hypergraph layout. We prove hardness results for the problem, namely for general directed networks we prove that it is NP-hard to find a -approximation, where is a positive constant and is the number of nodes of the network. For symmetric directed networks, we prove that the problem is APX-hard. These hardness results hold even if the traffic instance is a partial broadcast. On the other hand, we provide approximation algorithms, in particular an -approximation for symmetric directed networks. Finally, we focus on the case where the physical network is a directed path, providing a polynomial-time dynamic programming algorithm for a fixed number of sources running in time. [Copyright &y& Elsevier]

Abstract: Sorting permutations by operations such as reversals and block-moves has received much attention because of its applications in the study of genome rearrangements. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. In this paper, we investigate the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation, and devise a ()-approximation algorithm for this problem, where is the number of elements divided by the number of inversions in the permutation. The algorithm mostly relies on a new structure in the permutation graph called an umbrella, which can be optimally sorted in time. [Copyright &y& Elsevier]

Abstract: Given a finite set of straight line segments in and some , is there a subset of points on segments in with such that each segment of contains at least one point in ? This is a special case of the set covering problem where the family of subsets given can be taken as a set of intersections of the straight line segments in . Requiring that the given subsets can be interpreted geometrically this way is a major restriction on the input, yet we have shown that the problem is still strongly NP-complete . In light of this result, we studied the accuracy of two polynomial-time approximation algorithms along with a third heuristic based algorithm which return segment coverings. We obtain certain theoretical results, and in particular we show that the performance ratio for each of these algorithms is unbounded, in general. Despite this, our experimental results suggest that the cases where this ratio exceeds 2 are rare for “reasonable” methods of placing segments. This is evidence that these polynomial-time algorithms solve the problem accurately in practice. [Copyright &y& Elsevier]

Abstract: We study a class of multi-commodity flow problems in geometric domains: For a given planar domain P populated with obstacles (holes) of types, compute a set of thick paths from a “source” edge of P to a “sink” edge of P for vehicles of K distinct classes. Each class k of vehicle has a given set, , of obstacles it must avoid and a certain width, , of path it requires. The problem is to determine if it is possible to route width- paths for class k vehicles from source to sink, with each path avoiding the requisite set of obstacles, and no two paths overlapping. This form of multi-commodity flow in two-dimensional domains arises in computing throughput capacity for multiple classes of aircraft in an airspace impacted by different types of constraints, such as those arising from weather hazards. We give both algorithmic theory results and experimental results. We show hardness of many versions of the problem by proving that two simple variants are NP-hard even in the case . If , then the problem is NP-hard even when . If , , then the problem is NP-hard even when . In contrast, the problem for a single width and a single type of obstacles is polynomially solvable. We present approximation algorithms for the multi-criteria optimization problems that arise when trying to maximize the number of routable paths. We also give a polynomial-time algorithm for the case in which the number of holes in the input domain is bounded. Finally, we give experimental results based on an implementation of our methods and experiment with enhanced heuristics for efficient solutions in practice. Our algorithms are being utilized in simulations with NASAʼs Future Air traffic management Concepts Evaluation Tool (FACET). We report on experimental results based on applying our algorithms to weather-impacted airspaces, comparing heuristic strategies for searching for feasible path orderings and for computing short multi-class routes. Our results show that multi-class routes can feasibly be computed on real weather data instances on the scale required in air traffic management applications. [Copyright &y& Elsevier]

Abstract: Biclustering is becoming a popular technique for the study of gene expression data. This is mainly due to the capability of biclustering to address the data using various dimensions simultaneously, as opposed to clustering, which can use only one dimension at the time. Different heuristics have been proposed in order to discover interesting biclusters in data. Such heuristics have one common characteristic: they are guided by a measure that determines the quality of biclusters. It follows that defining such a measure is probably the most important aspect. One of the popular quality measure is the mean squared residue (MSR). However, it has been proven that MSR fails at identifying some kind of patterns. This motivates us to introduce a novel measure, called virtual error (VE), that overcomes this limitation. Results obtained by using VE confirm that it can identify interesting patterns that could not be found by MSR. [Copyright &y& Elsevier]

Abstract: The Fermat–Weber center of a planar body is a point in the plane from which the average distance to the points in is minimal. We first show that for any convex body in the plane, the average distance from the Fermat–Weber center of to the points in is larger than , where is the diameter of . This proves a conjecture of Carmi, Har-Peled and Katz. From the other direction, we prove that the same average distance is at most . The new bound substantially improves the previous bound of due to Abu-Affash and Katz, and brings us closer to the conjectured value of . We also confirm the upper bound conjecture for centrally symmetric planar convex bodies. [Copyright &y& Elsevier]

Abstract: Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. It was shown that if the processor can run at arbitrary speeds and uses power when running at speed , the online heuristic AVR has a competitive ratio . In this paper we first study the online heuristics for the discrete model where the processor can only run at given speeds. We propose a method to transform online heuristic AVR to an online heuristic for the discrete model and prove a competitive ratio , where is the maximum ratio between adjacent non-zero speed levels. We also prove that the analysis holds for a class of heuristics that satisfy certain natural properties. We further study the throughput maximization problem when there is an upper bound for the maximum speed. We propose a greedy algorithm with running time and prove that the output schedule is a 3-approximation of the throughput and a -approximation of the energy consumption. [Copyright &y& Elsevier]

Abstract: We consider the minimum spanning tree problem with conflict constraints (MSTC). The problem is known to be strongly NP-hard and computing even a feasible solution is NP-hard. When the underlying graph is a cactus, we show that the feasibility problem is polynomially bounded whereas the optimization version is still NP-hard. When the conflict graph is a collection of disjoint cliques, (equivalently, when the conflict relation is transitive) we observe that MSTC can be solved in polynomial time. We also identify other special cases of MSTC that can be solved in polynomial time. Exploiting these polynomially solvable special cases we derive strong lower bounds. Also, various heuristic algorithms and feasibility tests are discussed along with preliminary experimental results. As a byproduct of this investigation, we show that if an -optimal solution to the maximum clique problem can be obtained in polynomial time, then a -optimal solution to the maximum edge clique partitioning (Max-ECP) problem can be obtained in polynomial time. As a consequence, we have a polynomial time approximation algorithm for the Max-ECP with performance ratio , improving the best previously known bound of . [Copyright &y& Elsevier]

Abstract: In this work we address the problem of solving multiscenario optimization models that are deterministic equivalents of two-stage stochastic programs. We present a heuristic approximation strategy where we reduce the number of scenarios and obtain an approximation of the original multiscenario optimization problem. In this strategy, a subset of the given set of scenarios is selected based on a proposed criterion, and probabilities are assigned to the occurrence of scenarios in the reduced set. The original stochastic programming model is converted into a deterministic equivalent using the reduced set of scenarios. A mixed-integer linear program (MILP) is proposed for the reduced scenario selection. We apply this practical heuristic strategy to four numerical examples and show that reformulating and solving the stochastic program with the reduced set of scenarios yields an objective value close to the optimum of the original multiscenario problem. [Copyright &y& Elsevier]

Mobile edge computing (MEC) is envisioned as a prospective technology that supports latency-critical and computation-intensive applications by using storage and computation resources in network edges. The advantages of this technology are trapped in limited edge cloud resources, and one of the prime challenges is how to allocate available edge cloud resources to satisfy user requests. However, previous works usually optimize service (data&code) placement and request routing simultaneously within the same timescale, ignoring the fact that frequent service replacement will incur expensive operating expenses. In this paper, we jointly optimize service placement and request routing in the MEC network for data analysis applications, under the constraints of computation and storage resource. In particular, the Cloud Radio Access Network (C-RAN) architecture is applied to pool available resources and realize load balancing among edge clouds. In addition, we adopt a two timescale framework to reduce high operating expenses caused by frequent cross-cloud service replication and replica deletion. Then, we develop a greedy-based approximation algorithm for service placement subproblem and a linear programming (LP) relaxation-based heuristic algorithm for request routing subproblem, respectively. Finally, the numerical results demonstrate that our proposed solution reaches 90% of the optimal performance in services homogeneous case and 76% in services heterogeneous case. [ABSTRACT FROM AUTHOR]

• Investigation of residential shiftable loads (SLs) flexibility for grid operators • Large-scale multi-period optimal power flow (MP-OPF) framework for SLs management • Complex non-convex mixed-integer nonlinear programming (MINLP) formulation of MP-OPF • Proposal of new practical approaches: an NLP approximation and heuristic algorithms • Efficient (speed-wise and solution quality-wise) performance of proposed approaches The presence of smart buildings (SBs) is expected to grow manifold in the next decade, leading to both challenges and opportunities in managing increasingly "active" distribution systems. SBs are host to a number of devices and technologies capable of providing residential flexibility in order to maintain acceptable operating conditions within the distribution system. A prevalent class of devices with significant potential for flexibility provision are shiftable loads (SLs), which represent a large amount of potential SB-provided flexibility. However, the accurate modelling of SLs within the multi-period optimal power flow (MP-OPF) framework results in complex non-convex mixed-integer nonlinear programming (MINLP) problems. For realistic feeders, MINLP problems are intractable and hence require some heuristic form of circumvention. This work evaluates the limitations of the MINLP formulation and proposes new practical alternatives, namely a flexible NLP approximation and a multi-faceted heuristic algorithm. The proposed approaches are generic and applicable for any problem size or type of SL, while they are shown to work efficiently, both speed-wise and solution-quality-wise, outperforming state-of-the-art MINLP solvers. A simple scoring and ranking scheme is also proposed in order to make a direct comparison between the different approaches. [ABSTRACT FROM AUTHOR]

Traditional target coverage only ensures monitoring of targets. However, as people's security awareness increases, the requirement for target coverage also increases from monitoring to identification. Thus full-view coverage model is proposed to guarantee that any facing direction of a target could be covered. Based on this coverage model, we study the maximum full-view target coverage problem in camera sensor networks, where each camera sensor has P working directions, aiming at maximizing the number of full-view covered targets by scheduling the working directions of camera sensors. To solve this problem, we design a (1 − 1 e) -approximation algorithm based on pipage rounding and an efficient heuristic algorithm. Finally, simulation results are presented to demonstrate the performance of our algorithms. [ABSTRACT FROM AUTHOR]