More Like this

1. Blocking Adversarial Influence in Social Networks

   Jia, Feiran; Zhou, Kai; Kamhoua, Charles; Vorobeychik, Yevgeniy (January 2020, International Conference on Game and Decision Theory for Security)

   null (Ed.)

   While social networks are widely used as a media for information diffusion, attackers can also strategically employ analytical tools, such as influence maximization, to maximize the spread of adversarial content through the networks. We investigate the problem of limiting the diffusion of negative information by blocking nodes and edges in the network. We formulate the interaction between the defender and the attacker as a Stackelberg game where the defender first chooses a set of nodes to block and then the attacker selects a set of seeds to spread negative information from. This yields an extremely complex bi- level optimization problem, particularly since even the standard influence measures are difficult to compute. Our approach is to approximate the attacker’s problem as the maximum node domination problem. To solve this problem, we first develop a method based on integer programming combined with constraint generation. Next, to improve scalability, we develop an approximate solution method that represents the attacker’s problem as an integer program, and then combines relaxation with duality to yield an upper bound on the defender’s objective that can be computed using mixed integer linear programming. Finally, we propose an even more scalable heuristic method that prunes nodes from the consideration set based on their degree. Extensive experiments demonstrate the efficacy of our approaches. 

   more » « less
2. Portfolio Selection Problem

   Begashaw, Negash; Comert, Gurcan; Medhin, Negash G (June 2025, Neural Parallel and Scientific Computations)

   Given a set of securities or assets it is of interest to find an optimal way of investing in these assets. What is optimal has to specified. The objective is to optimize the return consistent with the specified objective. When there are several assets it is unlikely all the assets will increase if they are correlated. It is necessary to diversify one’s assets for a secure return. To deal with the different assets a combination of the assets should be considered with constraints as needed. One approach is the Markowitz mean-variance model where the mean variance is minimized including constraints. In this paper neural networks and machine learning are used to extend the ways of dealing with portfolio asset allocation. Portfolio selection problem in an efficient way. The use of heuristic algorithms in this case is imperative. In the past some heuristic methods based mainly on evolutionary algorithms, tabu search and simulated annealing have been developed. The purpose of this paper is to consider a particular neural network model, the Hopfield network, which has been used to solve some other optimisation problems and apply it here to the portfolio selection problem, comparing the new results to those obtained with previous heuristic algorithms. Although great success has been achieved for portfolio analysis with the birth of Markowitz model, the demand for timely decision making has significantly increased especially in recent years with the advancement of high frequency trading (HFT), which combines powerful computing servers and the fastest Internet connection to trade at extremely high speeds. This demand poses new challenges to portfolio solvers for real-time processing in the face of time-varying parameters. Neural networks, as one of the most powerful machine learning tools has seen great progress in recent years for financial data analysis and signal processing ([1], [14]). Using computational methods, e.g., machine learning and data analytics, to empower conventional finance is becoming a trend widely adopted in leading investment companies ([3]). 

   more » « less
3. Optimal Data Rate Allocation for Dynamic Sensor Fusion over Resource Constrained Communication Networks

   Jung, H.& T. (May 2021, American Control Conference)

   We consider a dynamic sensor fusion problem where a large number of remote sensors observe a common Gauss-Markov process and the observations are transmitted to a fusion center over a resource constrained communication network. The design objective is to allocate an appropriate data rate to each sensor in such a way that the total data traffic to the fusion center is minimized, subject to a constraint on the fusion center's state estimation error covariance. We show that the problem can be formulated as a difference-of-convex program, to which we apply the convex-concave procedure (CCP) and the alternating direction method of multiplier (ADMM). Through a numerical study on a truss bridge sensing system, we observe that our algorithm tends to allocate zero data rate to unneeded sensors, implying that the proposed method is an effective heuristic for sensor selection. 

   more » « less
4. Geometric Hitting Set for Line-Constrained Disks

   https://doi.org/10.1007/978-3-031-38906-1_38  

   Liu, Gang; Wang, Haitao (August 2023, Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023))

   Given a set P of n weighted points and a set S of m disks in the plane, the hitting set problem is to compute a subset 𝑃′ of points of P such that each disk contains at least one point of 𝑃′ and the total weight of all points of 𝑃′ is minimized. The problem is known to be NP-hard. In this paper, we consider a line-constrained version of the problem in which all disks are centered on a line ℓ. We present an 𝑂((𝑚+𝑛)log(𝑚+𝑛)+𝜅log𝑚) time algorithm for the problem, where 𝜅 is the number of pairs of disks that intersect. For the unit-disk case where all disks have the same radius, the running time can be reduced to 𝑂((𝑛+𝑚)log(𝑚+𝑛)). In addition, we solve the problem in 𝑂((𝑚+𝑛)log(𝑚+𝑛)) time in the 𝐿∞ and 𝐿1 metrics, in which a disk is a square and a diamond, respectively. 

   more » « less
5. Improved Algorithms for Distance Selection and Related Problems

   Wang, Haitao; Zhao, Yiming (August 2023, Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2023))

   In this paper, we propose new techniques for solving geometric optimization problems involving interpoint distances of a point set in the plane. Given a set P of n points in the plane and an integer 1 ≤ k ≤ binom(n,2), the distance selection problem is to find the k-th smallest interpoint distance among all pairs of points of P. The previously best deterministic algorithm solves the problem in O(n^{4/3} log² n) time [Katz and Sharir, 1997]. In this paper, we improve their algorithm to O(n^{4/3} log n) time. Using similar techniques, we also give improved algorithms on both the two-sided and the one-sided discrete Fréchet distance with shortcuts problem for two point sets in the plane. For the two-sided problem (resp., one-sided problem), we improve the previous work [Avraham, Filtser, Kaplan, Katz, and Sharir, 2015] by a factor of roughly log²(m+n) (resp., (m+n)^ε), where m and n are the sizes of the two input point sets, respectively. Other problems whose solutions can be improved by our techniques include the reverse shortest path problems for unit-disk graphs. Our techniques are quite general and we believe they will find many other applications in future. 

   more » « less