Algorithmic approaches for network design with facility location: A survey [PDF]
AUT Journal of Mathematics and Computing, 2022 We consider a family of problems that combine network design and facility location. Such problems arise in many practical applications in different fields such as telecommunications, transportation networks, logistic, and energy supply networks.
Mohsen Rezapour
doaj +1 more source
Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs [PDF]
, 2016 We study the prize-collecting version of the Node-weighted Steiner Tree problem (NWPCST) restricted to planar graphs. We give a new primal-dual Lagrangian-multiplier-preserving (LMP) 3-approximation algorithm for planar NWPCST.
Byrka, Jarosław +2 more
core +2 more sources
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest [PDF]
, 2016 We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the Subtree Prune-and-Regraft (SPR ...
Schalekamp, Frans +2 more
core +2 more sources
Algorithms For Positive Polynomial Approximation [PDF]
SIAM Journal on Numerical Analysis, 2019 Summary: We propose several algorithms for positive polynomial approximation. The main tool is a novel iterative method to compute nonnegative interpolation polynomials at any order, which is shown to converge under conditions that make it suitable for the numerical approximation of positive functions. Our method is based on the special representations
Charles, Frédérique +2 more
openaire +2 more sources
NORA: An Approach for Transforming Network Management Policies into Automated Planning Problems
Sensors, 2021 Realizing autonomic management control loops is pivotal for achieving self-driving networks. Some studies have recently evidence the feasibility of using Automated Planning (AP) to carry out these loops. However, in practice, the use of AP is complicated
Angela Rodriguez-Vivas +4 more
doaj +1 more source
Approximation Algorithms for Aligning Points [PDF]
Algorithmica, 2003 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Sergio Cabello, Marc J. van Kreveld
openaire +4 more sources
A Primal–Dual-Based Power Control Approach for Capacitated Edge Servers
Sensors, 2022 The intensity of radio waves decays rapidly with increasing propagation distance, and an edge server’s antenna needs more power to form a larger signal coverage area.
Qinghui Zhang +3 more
doaj +1 more source
An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty
Computation, 2022 In this paper, we consider the minimum power cover problem with submodular penalty (SPMPC). Given a set U of n users, a set S of m sensors and a penalty function π:2U→R+ on the plane, the relationship that adjusts the power p(s) of each sensor s and its ...
Han Dai
doaj +1 more source
Revision of Specification Automata under Quantitative Preferences [PDF]
, 2014 We study the problem of revising specifications with preferences for automata based control synthesis problems. In this class of revision problems, the user provides a numerical ranking of the desirability of the subgoals in their specifications.
Fainekos, Georgios, Kim, Kangjin
core +1 more source
Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover [PDF]
, 2013 Stochastic Boolean Function Evaluation is the problem of determining the value of a given Boolean function f on an unknown input x, when each bit of x_i of x can only be determined by paying an associated cost c_i.
Deshpande, Amol +2 more
core +1 more source