1,560 results on '"APPROXIMATION algorithms"'
Search Results
52. Maximum 0-1 timed matching on temporal graphs.
- Author
-
Mandal, Subhrangsu and Gupta, Arobinda
- Subjects
- *
BIPARTITE graphs , *APPROXIMATION algorithms , *NP-complete problems , *GRAPH algorithms - Abstract
Temporal graphs are graphs where the topology and/or other properties of the graph change with time. They have been used to model applications with temporal information in various domains. Problems on static graphs become more challenging to solve in temporal graphs because of dynamically changing topology, and many recent works have explored graph problems on temporal graphs. In this paper, we define a type of matching called 0-1 timed matching for temporal graphs, and investigate the problem of finding a maximum 0-1 timed matching for different classes of temporal graphs. We assume that only the edge set of the temporal graph changes with time. Thus, a temporal graph can be represented by associating each edge with one or more non-overlapping discrete time intervals for which that edge exists. We first prove that the problem is NP-complete for rooted temporal trees when each edge is associated with two or more time intervals. We then propose an O (n log n) time algorithm for the problem on a rooted temporal tree with n vertices when each edge is associated with exactly one time interval. The problem is then shown to be NP-complete also for bipartite temporal graphs even when each edge is associated with a single time interval and degree of each vertex is bounded by a constant k ≥ 3. We next investigate approximation algorithms for the problem for temporal graphs where each edge is associated with more than one time intervals. It is first shown that there is no 1 n 1 − ϵ -factor approximation algorithm for the problem for any ϵ > 0 even on a rooted temporal tree with n vertices unless NP = ZPP. We then present a 5 2 N ∗ + 3 -factor approximation algorithm for the problem for general temporal graphs where N ∗ is the average number of edges overlapping in time with each edge in the temporal graph. The same algorithm is also a constant-factor approximation algorithm for temporal graphs with degree of each vertex bounded by a constant. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
53. Improved approximation for maximum edge colouring problem.
- Author
-
Chandran, L. Sunil, Lahiri, Abhiruk, and Singh, Nitin
- Subjects
- *
RAMSEY numbers , *APPROXIMATION algorithms , *COLOR , *GRAPH algorithms - Abstract
The anti-Ramsey number , a r (G , H) is the minimum integer k such that in any edge colouring of G with k colours there is a rainbow subgraph isomorphic to H , namely, a copy of H with each of its edges assigned a different colour. The notion was introduced by Erdös and Simonovits in 1973. Since then the parameter has been studied extensively. The case when H is a star graph was considered by several graph theorists from the combinatorial point of view. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge q -colouring problem: Find a colouring of the edges of G , maximizing the number of colours satisfying the constraint that each vertex spans at most q colours on its incident edges. It is easy to see that the maximum value of the above optimization problem equals a r (G , K 1 , q + 1) − 1. In this paper, we study the maximum edge 2-colouring problem from the approximation algorithm point of view. The case q = 2 is particularly interesting due to its application in real-life problems. Algorithmically, this problem is known to be NP-hard for q ≥ 2. For the case of q = 2 , it is also known that no polynomial-time algorithm can approximate to a factor less than 3 / 2 assuming the unique games conjecture. Feng et al. showed a 2-approximation algorithm for this problem. Later Adamaszek and Popa presented a 5 / 3 -approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say M) and different colours to the connected components of G ∖ M. In this article, we give a new analysis of the aforementioned algorithm to show that for triangle-free graphs with perfect matching the approximation ratio is 8 / 5. We also show that this algorithm cannot achieve a factor better than 58 / 37 on triangle free graphs that has a perfect matching. The contribution of the paper is a completely new, deeper and closer analysis of how the optimum achieves a higher number of colours than the matching based algorithm, mentioned above. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
54. A primal–dual approximation algorithm for Minsat.
- Author
-
Arif, Umair, Benkoczi, Robert, Gaur, Daya Ram, and Krishnamurti, Ramesh
- Subjects
- *
LINEAR programming , *APPROXIMATION algorithms , *INTERIOR-point methods , *ALGORITHMS - Abstract
We characterize the optimal solution to the linear programming relaxation of the standard formulation for the minimum satisfiability problem. We give a O (n m 2) combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n (m) is the number of variables (clauses). As a by-product, we obtain a 2 (1 − 1 / 2 k) approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
55. Vertex-edge domination in unit disk graphs.
- Author
-
Jena, Sangram K. and Das, Gautam K.
- Subjects
- *
DOMINATING set , *UNDIRECTED graphs , *APPROXIMATION algorithms , *STATISTICAL decision making , *NP-complete problems - Abstract
Let G = (V , E) be a simple undirected graph. A set D ⊆ V is called a vertex-edge dominating set of G if for each edge e = u v ∈ E , either u or v is in D or one vertex from their neighbor is in D. Simply, a vertex v ∈ V , vertex-edge dominates every edge u v , as well as every edge adjacent to these edges. The objective of the vertex-edge domination problem is to find a minimum size vertex-edge dominating set of G. Herein, we study the vertex-edge domination problem in unit disk graphs and prove that the decision version of the problem belongs to the NP-complete class. We also show that the problem admits a simple polynomial-time 4-factor approximation algorithm and a polynomial-time approximation scheme (PTAS) in unit disk graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
56. Monitoring the edges of a graph using distances.
- Author
-
Foucaud, Florent, Kao, Shih-Shun, Klasing, Ralf, Miller, Mirka, and Ryan, Joe
- Subjects
- *
GRAPH connectivity , *CHARTS, diagrams, etc. , *BIPARTITE graphs , *COMPLETE graphs , *NP-complete problems , *APPROXIMATION algorithms , *HYPERCUBES - Abstract
We introduce a new graph-theoretic concept in the area of network monitoring. A set M of vertices of a graph G is a distance-edge-monitoring set if for every edge e of G , there are a vertex x of M and a vertex y of G such that e belongs to all shortest paths between x and y. We denote by dem (G) the smallest size of such a set in G. The vertices of M represent distance probes in a network modeled by G ; when the edge e fails, the distance from x to y increases, and thus we are able to detect the failure. It turns out that not only we can detect it, but we can even correctly locate the failing edge. In this paper, we initiate the study of this new concept. We show that for a nontrivial connected graph G of order n , 1 ≤ dem (G) ≤ n − 1 with dem (G) = 1 if and only if G is a tree, and dem (G) = n − 1 if and only if it is a complete graph. We compute the exact value of dem for grids, hypercubes, and complete bipartite graphs. Then, we relate dem to other standard graph parameters. We show that dem (G) is lower-bounded by the arboricity of the graph, and upper-bounded by its vertex cover number. It is also upper-bounded by twice its feedback edge set number. Moreover, we characterize connected graphs G with dem (G) = 2. Then, we show that determining dem (G) for an input graph G is an NP-complete problem, even for apex graphs. There exists a polynomial-time logarithmic-factor approximation algorithm, however it is NP-hard to compute an asymptotically better approximation, even for bipartite graphs of small diameter and for bipartite subcubic graphs. For such instances, the problem is also unlikely to be fixed parameter tractable when parameterized by the solution size. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
57. Induced star partition of graphs.
- Author
-
Shalu, M.A., Vijayakumar, S., Sandhya, T.P., and Mondal, Joyashree
- Subjects
- *
POLYNOMIAL time algorithms , *NP-complete problems , *BIPARTITE graphs , *DOMINATING set , *GRAPH algorithms , *PLANAR graphs - Abstract
Given a graph G , we call a partition (V 1 , V 2 , ... , V k) of its vertex set an induced star partition of G if each set in the partition induces a star. In this paper, we consider the problem of finding an induced star partition of a graph of minimum size and its decision versions. This problem may be viewed as an amalgamation of the well-known dominating set and coloring problems. We obtain the following main results: (1) Deciding whether a graph can be partitioned into k induced stars is NP-complete for each fixed k ≥ 3 and has a polynomial time algorithm for each k ≤ 2. (2) It is NP-hard to approximate the minimum induced star partition size within n 1 2 − ϵ for all ϵ > 0. (3) The decision version of the induced star partition problem is NP-complete for subcubic bipartite planar graphs, line graphs (a subclass of K 1 , r -free graphs, r ≥ 3), K 1 , 5 -free split graphs and co-tripartite graphs. (4) The minimum induced star partition problem has an r 2 -approximation algorithm for K 1 , r -free graphs (r ≥ 2) and a 2-approximation algorithms for split graphs. We also identify some fixed parameter tractable and exact exponential time algorithms that follow from the literature. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
58. Collision-free routing problem with restricted L-path.
- Author
-
Ajay, Jammigumpula, Jana, Satyabrata, and Roy, Sasanka
- Subjects
- *
INDEPENDENT sets , *INTERSECTION graph theory , *ROUTING algorithms , *APPROXIMATION algorithms - Abstract
Given a set of vehicles that are allowed to move in a plane along a predefined directed rectilinear path, the collision-free routing problem seeks a maximum number of vehicles that can move without collision. This problem is known to be NP-hard (Ajaykumar et al., 2016). Here we study a variant of this problem called the constrained collision-free routing problem (in short, CCRP). In this problem, each vehicle is allowed only to move in a directed L-shaped path. First, we show that CCRP is NP-hard. Further, we prove that any β -approximation algorithm for the maximum independent set problem in B 1 -VPG graphs would produce a β -approximation for CCRP. Also, we propose a 2-approximation algorithm for the maximum independent set problem on intersection graph of n unit-L frames (the union of a unit-length vertical and a unit-length horizontal line segment that shares an endpoint) with O (n) space and O (n 2) time. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
59. Hardness results of global total [formula omitted]-domination problem in graphs.
- Author
-
Panda, B.S. and Goyal, Pooja
- Subjects
- *
DOMINATING set , *BIPARTITE graphs , *APPROXIMATION algorithms , *HARDNESS , *STATISTICAL decision making - Abstract
A subset D ⊆ V of a graph G = (V , E) is called a global total k -dominating set of G if D is a total k -dominating set of both G and G ¯ , the complement of G. The Minimum Global Total k - Domination problem is to find a global total k -dominating set of minimum cardinality of the input graph G and the Decide Global Total k - Domination problem is the decision version of the Minimum Global Total k - Domination problem. The Decide Global Total k - Domination problem is known to be NP -complete for general graphs. In this paper, we study the complexity of the Minimum Global Total k - Domination problem. We show the Decide Global Total k - Domination problem remains NP -complete for bipartite graphs and chordal graphs. We also show that Minimum Global Total k - Domination cannot be approximated within a factor of (1 − ϵ) ln | V | for any ϵ > 0 unless P = NP for bipartite graphs as well as for chordal graphs. Next, we show that Minimum Global Total k - Domination admits a constant approximation algorithm for bounded degree graphs. Finally, we show that Minimum Global Total k - Domination problem is APX -complete for bounded degree graphs. We also show that Decide Global Total k - Domination problem is W[2] -hard for bipartite graphs and for chordal graphs when we choose the size of the GTkD-set as the parameter. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
60. Improved algorithms for non-submodular function maximization problem.
- Author
-
Liu, Zhicheng, Jin, Jing, Chang, Hong, Du, Donglei, and Zhang, Xiaoyan
- Subjects
- *
SUBMODULAR functions , *GREEDY algorithms , *ALGORITHMS , *APPROXIMATION algorithms , *ARTIFICIAL intelligence , *EXPECTATION-maximization algorithms - Abstract
• We combine the distorted objective function, the threshold and the greedy algorithms. • This problem includes some previously studied problems as special cases, such as submodular+supermodular maximization, γ -weakly submodular function maximization. • The approximation ratio in Algorithm 1 is the minimum of 1 − k f e − 1 and 1 − (k g) 2 , improving the result obtained by Bai et al. • Algorithm 1 has an approximation ratio 1 − (1 − γ + γ α) e − γ , improving the result obtained by Bian et al. • Set g (S) = 0. Algorithm 2 has an approximation ratio γ γ + 1 , improving the approximate ratio 1 − 1 2 γ by Wang et al. The concept of submodularity finds wide applications in data science, artificial intelligence, and machine learning, providing a boost to the investigation of new ideas, innovative techniques, and creative algorithms to solve different submodular optimization problems arising from a diversity of applications. However pure submodular or supermodular problems only represent a small portion of the problems we are facing in real life applications. The main focus of this work is to consider a non-submodular function maximization problem subject to a cardinality constraint, where the objective function is the sum of a monotone γ -weakly submodular function and a supermodular function. This problem includes some previously studied problems as special cases, such as the submodular+supermodular maximization problem when γ =1, and the γ -weakly submodular function maximization problem when the supermodular function is void. We present greedy algorithms for this generalized problem under both offline and streaming models, improving existing results. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
61. Gaussian downlink user selection subject to access limit, power budget, and rate demands.
- Author
-
Liu, Xiang, Zou, Jinyu, Chen, Pengpeng, and Wan, Peng-Jun
- Subjects
- *
GAUSSIAN channels , *NP-hard problems , *APPROXIMATION algorithms - Abstract
Consider a Gaussian downlink between an access point with power budget P > 0 , and a set of users specified by their effective noises and rate demands. In order to control the decoding complexity and error propagation, an integer-valued access limit M > 0 is imposed on the number of superimposed users. For each subset S of users, its (total) power demand p (S) is a strictly increasing and nonseparable function of the effective noises and rate demands of users in S. A subset S of users is feasible if | S | ≤ M and p (S) ≤ P. The goal is to select a feasible subset S of users whose total rate demand is maximized. In this paper, we show that this problem is NP-hard, and present a (1 − 1 / e) -approximation algorithm for this problem. In addition, we also give several other approximation algorithms with trade-offs between accuracy and efficiency. • The Gaussian downlink user selection problem studied in this paper is an NP-hard maximization problem. • The first 1 2 (1 − 1 / e) -approximation algorithm takes the relaxation/extraction approach. • A better algorithm utilizes partial enumeration for reducing the extraction loss, and achieves (1 − 1 / e) -approximation factor. • The paper is concluded with a summary of the general algorithmic framework and some open problems for further studies. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
62. Approximating activation edge-cover and facility location problems.
- Author
-
Kortsarz, Guy, Nutov, Zeev, and Shalom, Eli
- Subjects
- *
MULTIGRAPH , *SET functions , *APPROXIMATION algorithms - Abstract
What approximation ratio can we achieve for the Facility Location problem if whenever a client u connects to a facility v , the opening cost of v is at most θ times the service cost of u ? We show that this and many other problems are a particular case of the Activation Edge-Cover problem. Here we are given a multigraph G = (V , E) , a set R ⊆ V of terminals, and thresholds { t u e , t v e } for each uv -edge e ∈ E. The goal is to find an assignment a = { a v : v ∈ V } to the nodes minimizing ∑ v ∈ V a v , such that the edge set E a = { e = u v : a u ≥ t u e , a v ≥ t v e } activated by a covers R. We obtain ratio 1 + max x ≥ 1 ln x 1 + x / θ ≈ ln θ − ln ln θ for the problem, where θ ≤ max e ∈ E max { t u e , t v e } min { t u e , t v e } is a problem parameter. This result is based on a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get the same ratio for the above variant of Facility Location. If for each facility all service costs are identical then we show a better ratio 1 + max k ∈ N H k − 1 1 + k / θ , where H k = ∑ i = 1 k 1 / i. For the Min-Power Edge-Cover problem we improve the ratio 1.406 of [4] (achieved by iterative randomized rounding) to 1.2785. For unit thresholds we improve the ratio 73 / 60 ≈ 1.217 of [4] to 1555 1347 ≈ 1.155. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
63. A polynomial-time approximation to a minimum dominating set in a graph.
- Author
-
Hernández Mira, Frank Ángel, Parra Inza, Ernesto, Sigarreta Almira, José María, and Vakhania, Nodari
- Subjects
- *
DOMINATING set , *APPROXIMATION algorithms , *CHARTS, diagrams, etc. , *GRAPH connectivity - Abstract
A dominating set of a graph G = (V , E) is a subset of vertices S ⊆ V such that every vertex v ∈ V ∖ S has at least one neighbor in S. Finding a dominating set with the minimum cardinality in a connected graph G = (V , E) is known to be NP-hard. A polynomial-time approximation algorithm for this problem, described here, works in two stages. At the first stage a dominant set is generated by a greedy algorithm, and at the second stage this dominating set is purified (reduced). The reduction is achieved by the analysis of the flowchart of the algorithm of the first stage and a special kind of clustering of the dominating set generated at the first stage. The clustering of the dominating set naturally leads to a special kind of a spanning forest of graph G , which serves as a basis for the second purification stage. We expose some types of graphs for which the algorithm of the first stage already delivers an optimal solution and derive sufficient conditions when the overall algorithm constructs an optimal solution. We give three alternative approximation ratios for the algorithm of the first stage, two of which are expressed in terms of solely invariant problem instance parameters, and we also give one additional approximation ratio for the overall two-stage algorithm. The greedy algorithm of the first stage turned out to be essentially the same as the earlier known state-of-the-art algorithms for the set cover and dominating set problem Chvátal [6] and Parekh [31]. The second purification stage results in a significant reduction of the dominant set created at the first stage, in practice. The practical behavior of both stages was verified for randomly generated problem instances. The computational experiments emphasize the gap between a solution of Stage 1 and a solution of Stage 2. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
64. Minimum color spanning circle of imprecise points.
- Author
-
Acharyya, Ankush, Jallu, Ramesh K., Keikha, Vahideh, Löffler, Maarten, and Saumell, Maria
- Subjects
- *
NP-hard problems , *COLORS , *COLOR , *CIRCLE , *PROTHROMBIN , *APPROXIMATION algorithms - Abstract
• The smallest minimum color-spanning circle (S-MCSC) problem can be solved in O (n k log n) time. • The largest minimum color-spanning circle (L-MCSC) problem is NP-Hard. • A 1 3 -factor (1 2 , if no two distinct color disks intersect) approximation to the L-MCSC problem can be computed in O (n k log n) time. Let R be a set of n colored imprecise points, where each point is colored by one of k colors. Each imprecise point is specified by a unit disk in which the point lies. We study the problem of computing the smallest and the largest possible minimum color spanning circle, among all possible choices of points inside their corresponding disks. We present an O (n k log n) time algorithm to compute a smallest minimum color spanning circle. Regarding the largest minimum color spanning circle, we show that the problem is NP - Hard and present a 1 3 -factor approximation algorithm. We improve the approximation factor to 1 2 for the case where no two disks of distinct color intersect. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
65. Complexity of paired domination in AT-free and planar graphs.
- Author
-
Tripathi, Vikash, Kloks, Ton, Pandey, Arti, Paul, Kaustav, and Wang, Hung-Lung
- Subjects
- *
PLANAR graphs , *DOMINATING set , *BIPARTITE graphs , *CHARTS, diagrams, etc. , *NP-complete problems , *GRAPH algorithms , *STATISTICAL decision making , *APPROXIMATION algorithms - Abstract
For a graph G = (V , E) , a subset D of vertex set V , is a dominating set of G if every vertex not in D is adjacent to at least one vertex of D. A dominating set D of a graph G with no isolated vertices is called a paired dominating set (PD-set) , if the subgraph induced by D in G has a perfect matching. The Min-PD problem requires to compute a PD-set of minimum cardinality. The decision version of the Min-PD problem is NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the other side, the problem is efficiently solvable for many graph classes including interval graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graphs. The class of AT-free graphs contains cocomparability graphs, permutation graphs, trapezoid graphs, and interval graphs as subclasses. We propose a polynomial-time algorithm to compute a minimum PD-set in AT-free graphs. In addition, we also present a linear-time 2-approximation algorithm for the problem in AT-free graphs. Further, we prove that the decision version of the problem is NP-complete for planar graphs, which answers an open question asked by Lin et al. (2015) [19] and (2020) [20]. Alvarado et al. (2015) [1] conjectured that given a graph G = (V , E) , it is NP-hard to decide whether γ (G) = γ p r (G). In this paper we settle this conjecture affirmatively. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
66. Approximation algorithm for prize-collecting sweep cover with base stations.
- Author
-
Liang, Wei and Zhang, Zhao
- Subjects
- *
APPROXIMATION algorithms , *ALGORITHMS - Abstract
• Propose a new problem: prize-collecting sweep cover problem. • Give a 5-LMP algorithm for prize-collecting sweep cover assuming constant number of base-stations. • Give a 2-LMP algorithm for the rooted prize-collecting forest with k components problem. In a sweep cover problem, positions of interest (PoIs) are required to be visited periodically by mobile sensors. In this paper, we propose a new sweep cover problem: the prize-collecting sweep cover problem (PCSC), in which penalty is incurred by those PoIs which are not sweep-covered, and the goal is to minimize the covering cost plus the penalty. Assuming that every mobile sensor has to be linked to some base station, and the number of base stations is upper bounded by a constant, we present a 5-LMP (Lagrangian Multiplier Preserving) algorithm. As a step stone, we propose the prize-collecting forest with k components problem (PCF k), which might be interesting in its own sense, and presented a 2-LMP for rooted PCF k. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
67. Adaptive influence maximization under fixed observation time-step.
- Author
-
Zhang, Yapu, Chen, Shengminjie, Xu, Wenqing, and Zhang, Zhenning
- Subjects
- *
APPROXIMATION algorithms , *GREEDY algorithms , *SOCIAL networks , *PROBLEM solving , *SAMPLING (Process) , *BACKPACKS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
68. Efficient scheduling strategy for mobile chargers in task-based wireless sensor networks.
- Author
-
Meng, Xiangguang, Guo, Jianxiong, Ding, Xingjian, and Zhang, Xiujuan
- Subjects
- *
WIRELESS sensor networks , *APPROXIMATION algorithms , *SCHEDULING - Abstract
• We study the task utility maximization problem by scheduling mobile chargers and prove the NP-hardness of the problem. • We design three approximation algorithms for our problems, and prove the approximation ratio through theoretical analysis. • We validate the effectiveness of our algorithms by conducting extensive simulations. Replenishing energy to wireless sensor networks is always a crucial problem as the energy capacity of sensor nodes is very limited. Scheduling mobile chargers to charge sensor nodes has been widely studied due to its efficiency and flexibility. However, most existing works focus on maximizing the charging utility or charging efficiency, which ignores the task performing functions of sensor nodes. In this paper, we study the problem of scheduling a mobile charger to maximize the task utility achieved by sensor nodes. We consider two different scenarios where sensor nodes are deployed on a line road and a ring road, respectively. We prove the NP-Hardness of our problems and design two approximation algorithms with guaranteed performance. We also investigate how to jointly schedule two mobile chargers in the line road scenario, and design a corresponding approximation algorithm to address the problem. We prove the approximation ratio of our algorithms through theoretical analysis, and conduct extensive simulations to validate the performance of our algorithms. Simulation results show that our algorithms always outperform the baselines, which demonstrates the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
69. Incentive design and profit sharing in multi-modal transportation networks.
- Author
-
Deng, Yuntian, Shao, Shiping, Mittal, Archak, Twumasi-Boakye, Richard, Fishelson, James, Gupta, Abhishek, and Shroff, Ness B.
- Subjects
- *
PROFIT-sharing , *COOPERATIVE game theory , *APPROXIMATION algorithms , *STOCHASTIC approximation , *MARKET design & structure (Economics) , *DISCOUNT prices - Abstract
We consider the situation where multiple transportation service providers cooperate to offer an integrated multi-modal platform to enhance the convenience to the passengers through ease in multi-modal journey planning, payment, and first and last mile connectivity. This market structure allows the multi-modal platform to coordinate profits across modes and also provide incentives to the passengers. Accordingly, in this paper, we use cooperative game theory coupled with the hyperpath-based stochastic user equilibrium framework to study such a market. We assume that the platform sets incentives (price discount or excess charge on passengers) along every edge in the transportation network. We derive the continuity and monotonicity properties of the equilibrium flow with respect to the incentives along every edge. The optimal incentives that maximize the profit of the platform are obtained through a two time-scale stochastic approximation algorithm. We use the asymmetric Nash bargaining solution to design a fair profit sharing scheme among the service providers. We show that the profit for each service provider increases after cooperation on such a platform. Finally, we complement the theoretical results through two numerical simulations. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
70. Isogeometric analysis of diffusion problems on random surfaces.
- Author
-
Huang, Wei and Multerer, Michael
- Subjects
- *
ISOGEOMETRIC analysis , *SINGULAR value decomposition , *NUMERICAL solutions to equations , *COMPUTATIONAL geometry , *APPROXIMATION algorithms - Abstract
In this article, we discuss the numerical solution of diffusion equations on random surfaces within the isogeometric framework. We describe in detail, how diffusion problems on random surfaces can be modelled and how quantities of interest may be derived. In particular, we employ a low rank approximation algorithm for the high-dimensional space-time correlation of the random solution based on an online singular value decomposition, cp. [7]. Extensive numerical studies are performed to validate the approach. In particular, we consider complex computational geometries originating from surface triangulations. The latter can be recast into the isogeometric context by transforming them into quadrangulations using the procedure from [41] and a subsequent approximation by NURBS surfaces. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
71. Optimal global approximation of systems of jump-diffusion SDEs on equidistant mesh.
- Author
-
Kałuża, Andrzej
- Subjects
- *
APPROXIMATION algorithms , *POISSON processes , *WIENER processes - Abstract
In this paper, we provide a construction of two algorithms for approximation of the system of the jump-diffusion SDEs. Both methods are based on the classical Milstein steps and use equidistant discretization points. We construct implementable algorithm and their derivative-free version. We show that constructed methods are asymptotically optimal in the class of methods that use equidistant discretization of the interval [ 0 , T ]. Moreover, we report numerical experiments performed for some test equations, which confirm theoretical properties. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
72. Data-driven iterative tuning based active disturbance rejection control for FOPTD model.
- Author
-
Chen, Zhuo, Hao, Yong-Sheng, Su, Zhi-gang, and Sun, Li
- Subjects
ITERATIVE learning control ,STOCHASTIC approximation ,APPROXIMATION algorithms ,SELF-tuning controllers - Abstract
Active Disturbance Rejection Control (ADRC) emerges as a promising control method that can effectively handle uncertainties and disturbances. However, many model-based ADRC tuning methods turn laborious to achieve satisfactory control performance, when the critical process parameters are difficult to accurately obtain, especially the time delay information. To this end, this paper aims to propose a data-driven iterative tuning method for time-delayed ADRC (TD-ADRC). Based on parameter scaling technique, the quantitative correlation among control performance, robustness and normalized controller parameters are investigated. It is then used to design robust nominal controller. Then, based on the TD-ADRC inner-loop equivalent structure, an iterative feedback tuning (IFT) method is proposed to optimally obtain the nominal first order plus time delay (FOPTD) process model. Its unbiasedness and convergence are also described. With the empirical relations and the IFT stochastic approximation algorithm, a data-driven iterative tuning method for TA-ADRC is proposed, which allows a reasonable trade-off between system performance and robustness. Simulation results validate the efficacy of the proposed method, and a water-tank control experiment depicts a promising prospect in control practice. • A data-driven iterative tuning method for time-delayed ADRC is proposed considering both control performance and robustness. • An unbiased gradient estimate with respect to the model parameters under noise conditions is derived. • Control parameters are tuned iteratively through a data-driven method: iterative feedback tuning method. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
73. Coordinated risk-averse distributionally robust optimization for maintenance and generation schedules of offshore wind farm cluster.
- Author
-
Feng, Xiangyong, Lin, Shunjiang, Liang, Yutao, Lai, Xin, and Liu, Mingbo
- Subjects
- *
OFFSHORE wind power plants , *DISTRIBUTION (Probability theory) , *TRAVEL time (Traffic engineering) , *OPERATING costs , *ROBUST optimization , *APPROXIMATION algorithms - Abstract
• A novel two-stage coordinated risk-averse distributionally robust optimization model for maintenance and generation schedules of wind turbines is proposed. • A risk-averse measurement method is combined with DRO model for considering the operation risks. • A feasible route generating algorithm for reducing the number of required binary variables is proposed. • The transformation of proposed model and the specific algorithm is proposed to solve the proposed model. • Test results show the computational accuracy and efficiency of the proposed method. The coordinated optimization of maintenance and generation schedules of multiple offshore wind farms (OWFs) bring great benefits in reducing the maintenance and operation cost of OWF cluster. Firstly, a two-stage coordinated risk-averse distributionally robust optimization (CRDRO) model for maintenance and generation schedules of wind turbines (WTs) in OWF cluster is proposed. This model takes into account uncertainties related to the prediction errors in WTs' maximum available active power outputs, the travel time of maintenance vessels, and the high operational cost risks associated with these uncertainties. A feasible route generating algorithm is designed to obtain all feasible maintenance combinations for WTs and the corresponding routes of maintenance vessels for the CRDRO model. The risk-averse term, which is a weighted sum of expected operation costs and GlueVaR value, is used to measure the tail risk of the worst probability distribution. To solve the two-stage CRDRO model, the risk-averse term is simplified into the form of expected value calculation, which can be further transformed into the tractable form by using the strong duality theorem. Finally, the two-stage CRDRO model is solved by the column-and-constraint generation algorithm, with the nonconvex sub-problem being addressed by the outer approximation algorithm. Case studies on an real-world cluster comprising three OWFs verify the correctness and efficiency of the proposed method, and demonstrate that the CRDRO model enhances the overall economic efficiency and reduces the high operational cost risk under extreme scenarios. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
74. New bounds for single-machine time-dependent scheduling with uniform deterioration.
- Author
-
Gkikas, Angelos, Letsios, Dimitrios, Radzik, Tomasz, and Steinhöfel, Kathleen
- Subjects
- *
APPROXIMATION algorithms , *SCHEDULING , *PRODUCTION scheduling - Abstract
We consider the single-machine time-dependent scheduling problem with linearly deteriorating jobs arriving over time. Each job i is associated with a release time r i and a processing time p i (s i) = α i + β i s i , where α i , β i > 0 are parameters and s i is the job's start time. In this setting, the approximability of both single-machine minimum makespan and total completion time problems remains open. We develop new bounds and approximation results for the special case of the problems with uniform deterioration, i.e. β i = β , for each i. The main contribution is a O (1 + 1 / β) -approximation algorithm for the makespan problem and a O (1 + 1 / β 2) approximation algorithm for the total completion time problem. Further, we propose greedy constant-factor approximation algorithms for instances with β = O (1 / n) and β = Ω (n) , where n is the number of jobs. Our analysis is based on an approach for comparing computed and optimal schedules via bounding pseudomatchings. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
75. An approximation algorithm for K-best enumeration of minimal connected edge dominating sets with cardinality constraints.
- Author
-
Kurita, Kazuhiro and Wasa, Kunihiro
- Subjects
- *
DOMINATING set , *APPROXIMATION algorithms , *GRAPH algorithms , *DATA analysis , *ALGORITHMS - Abstract
K-best enumeration , which asks to output k -best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, k -best enumeration tends to be intractable since, in many cases, finding one optimum solution is NP-hard. To overcome this difficulty, we combine k -best enumeration with a concept of enumeration algorithms called approximation enumeration algorithms. As a main result, we propose a 4-approximation algorithm for minimal connected edge dominating sets which outputs k minimal solutions with cardinality at most 4 ⋅ OPT ‾ , where OPT ‾ is the cardinality of a minimum solution which is not outputted by the algorithm. Our proposed algorithm runs in O (n m 2 Δ) delay, where n , m , Δ are the number of vertices, the number of edges, and the maximum degree of an input graph. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
76. Explicit machine learning-based model predictive control of nonlinear processes via multi-parametric programming.
- Author
-
Wang, Wenlong, Wang, Yujia, Tian, Yuhe, and Wu, Zhe
- Subjects
- *
PREDICTIVE control systems , *MACHINE learning , *APPROXIMATION algorithms , *PREDICTION models , *SEARCH algorithms , *CHEMICAL processes - Abstract
Machine learning-based model predictive control (ML-MPC) has been developed to control nonlinear processes with unknown first-principles models. While ML models can capture nonlinear dynamics of complex systems, the complexity of ML models leads to increased computation time for real-time implementation of ML-MPC. To address this issue, in this work, we propose an explicit ML-MPC framework for nonlinear processes using multi-parametric programming. Specifically, a self-adaptive approximation algorithm is first developed to obtain a piecewise linear affine function that approximates the behaviors of ML models. Then, multi-parametric quadratic programming (mpQP) problems are formulated to generate the solution map for states in discretized state–space. Furthermore, to accelerate the implementation of explicit ML-MPC, a neighbor-first search algorithm is developed. Finally, an example of a chemical reactor is used to demonstrate the effectiveness of the explicit ML-MPC. • An explicit MPC framework for MPCs using a general class of ML models. • A self-adaptive algorithm for approximating ML models with the desired accuracy. • Neighbor-first search algorithm for accelerating implementation of explicit ML-MPC. • Improvement of computational efficiency demonstrated in a chemical process example. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
77. Taking the human out of decomposition-based optimization via artificial intelligence, Part I: Learning when to decompose.
- Author
-
Mitrai, Ilias and Daoutidis, Prodromos
- Subjects
- *
ARTIFICIAL intelligence , *DEEP learning , *REPRESENTATIONS of graphs , *GRAPH neural networks , *NONLINEAR programming , *APPROXIMATION algorithms - Abstract
In this paper, we propose a graph classification approach for automatically determining whether to use a monolithic or a decomposition-based solution method. In this approach, an optimization problem is represented as a graph that captures the structural and functional coupling among the variables and constraints of the problem via an appropriate set of features. Given this representation, a graph classifier can be built to assist a solver in selecting the best solution strategy for a given problem with respect to some metric of choice. The proposed approach is used to develop a classifier that determines whether a convex Mixed Integer Nonlinear Programming problem should be solved using branch and bound or the outer approximation algorithm. Finally, it is shown how the learned classifier can be incorporated into existing mixed integer optimization solvers. • A deep learning framework is proposed to decide when to use a decomposition. • A feature-based graph representation of optimization problems is proposed. • The proposed approach is applied to Mixed Integer Nonlinear optimization problems. • Integration of the proposed approach with optimization solvers is discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
78. Consensus of networked nonlinear systems based on the distributed stochastic approximation algorithm.
- Author
-
Feng, Wenhui and Wang, Liying
- Subjects
- *
STOCHASTIC approximation , *NONLINEAR systems , *APPROXIMATION algorithms , *TIME-varying systems , *DISTRIBUTED algorithms , *MULTIAGENT systems - Abstract
Consensus of networked nonlinear nonparametric time-varying systems is studied, and the nonlinearity at input may possess arbitrary growth rate. In addition, the communication noise is also under consideration. The purely distributed control algorithm is designed on the basis of distributed stochastic approximation algorithm with expanding truncations (DSAAWET). The truncation mechanism neutralizes the divergent tendency caused by unknown nonlinearities and noises, which makes the algorithm well tackle more general nonlinearities with high growth rate and more complicated structure noises. We first prove the average consensus over fixed digraph, and then extend the results to averagely connected time-varying digraphs. Finally, the validity of the algorithm is justified by numerical simulations. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
79. Leaf sector covers with applications on circle graphs.
- Author
-
Mu, Ta-Yu, Wang, Po-Yuan, and Lin, Ching-Chi
- Subjects
- *
APPROXIMATION algorithms , *DOMINATING set , *DATA structures , *TIME complexity , *GRAPH algorithms - Abstract
Damian and Pemmaraju (2002) [8] introduced leaf sector covers for circle graphs and presented an O (n 2) -time algorithm to find this data structure. They subsequently employed it as an algorithmic tool, leading to the development of an 8-approximation algorithm for the dominating set problem, a (2 + ε) -approximation scheme for the dominating set problem, and a (3 + ε) -approximation scheme for the total dominating set problem. In this paper, we have improved the time complexity from O (n 2) to O (n + m) for finding a leaf sector cover. Furthermore, we employed leaf sector covers as a powerful algorithmic tool to design a 10-approximation algorithm for the total dominating set problem and a 12-approximation algorithm for the paired-dominating set problem. Moreover, we also proposed a (2 + ε) -approximation scheme for the total dominating set problem and a (4 + ε) -approximation scheme for the paired-dominating set problem. The results presented above are currently the best algorithms for circle graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
80. A Steiner-point-based algorithm for approximate shortest paths in weighted equilateral-triangle meshes.
- Author
-
Bose, Prosenjit, Esteban, Guillermo, and Maheshwari, Anil
- Subjects
- *
APPROXIMATION algorithms , *WEIGHTED graphs , *ALGORITHMS , *TRIANGLES , *STEINER systems , *TRIANGULATION - Abstract
Let T be a tessellation composed of equilateral triangular regions, where each region has an associated positive weight. We present two methods that discretize the space based on the placement of Steiner points in the cells of T. Using such a discretization, we can use Dijkstra's algorithm for computing the shortest path in the geometric graph obtained. This will lead us to two approximation algorithms for solving the Weighted Region Problem. For a given parameter ε ∈ (0 , 1 ] , the first discretization scheme provides an approximate path that is (1 + 0.428 ε) times better than the approximation given by Aleksandrov et al. (2005) [5]. The other discretization scheme uses at least ( ε + 2 ε + 4 ε + 4) log 2 e fewer points per segment of the triangulation with the same approximation factor. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
81. CMRS: A digital twin enabled workers recruitment and task scheduling scheme for future crowdsourcing networks under precedence constraints.
- Author
-
Teng, Haojun, Liu, Anfeng, Gui, Jinsong, Song, Houbing, Wang, Tian, and Zhang, Shaobo
- Subjects
- *
DIGITAL twins , *EMPLOYEE recruitment , *DIFFERENTIAL evolution , *APPROXIMATION algorithms , *CROWDSOURCING , *SCHEDULING , *PRODUCTION scheduling , *DIGITAL communications , *MULTICASTING (Computer networks) - Abstract
In crowdsourcing systems, a challenge arises in efficiently recruiting workers with unknown execution speed to complete tasks with precedence constraints within the shortest possible time. Recent research either only studies recruiting unknown workers or focuses on assigning tasks with precedence constraints, but few works consider both these factors. This paper aims to address this challenge considering all these factors by proposing a digital twin-assisted Combinatorial Multi-arm bandit based multi-round work Recruitment and task Scheduling (CMRS) scheme. Firstly, with the help of digital twin technology, we build digital twin models for crowdsourcing tasks and workers in digital twin layer of platform. And we formulate a Multi-round Workers recruitment and Task scheduling with Precedence constraints (MWTP) problem with the object of minimizing task completion time (makespan) to model the above challenging issue in crowdsourcing computing. The MWTP problem can be divided into two sub-problems, the task scheduling sub-problem and the worker recruitment sub-problem. Secondly, in the CMRS scheme, the differential evolution based task scheduling (DETS) algorithm and CUCB-based worker recruitment (CWR) method are proposed to solve them, respectively. Specifically, for the task scheduling sub-problem, we first propose a priority-driven based task scheduling (PDTS) approximation algorithm to produce a primary solution with an explicit approximation ratio. Then a DETS algorithm is proposed to use the solution of PDTS for initialization and generate a better solution that further improves the performance. For the unknown workers recruitment sub-problem, we use the Combinatorial Multi-Arm Bandit framework to model this, and propose CWR method to learn the computational capabilities of workers while maintaining good performance during multiple rounds of worker recruitment by adding a tuning term to balanced exploration and exploitation. Finally, verified by extensive comparison experiments, the CMRS scheme can achieve the best performance of makespan compared with the baselines in most cases. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
82. Efficient resource allocation for 5G/6G cognitive radio networks using probabilistic interference models.
- Author
-
Zaheer, Osama, Ali, Mudassar, Imran, Muhammad, Zubair, Humayun, and Naeem, Muhammad
- Subjects
COGNITIVE radio ,RADIO networks ,RESOURCE allocation ,NP-hard problems ,CONSTRAINT satisfaction ,APPROXIMATION algorithms - Abstract
The Cognitive Radio Network, incorporating Device-to-Device communication and a heterogeneous network, has garnered significant attention due to its ability to address spectrum shortage issues and optimize the efficient utilization of spectrum resources. However, resource allocation considering stochastic behavior has not been considered in existing studies. In this paper, our work aimed to maximize the throughput of the overall network considering multiple users under the umbrella of the Cognitive radio network assisted by amplify and forward relay. The constraints are treated as chance constraints with a probability of satisfaction in them, which leads to a non-convex mixed integer nonlinear problem which is an NP-Hard problem. To solve this problem an exhaustive search solution for optimal results is required. However, the computational burden always increases with the user equipment. Therefore, to obtain an optimal solution with having low computational burden, the Outer Approximation Algorithm is utilized in this research. To evaluate the desired results, extensive simulations have been carried out. The effectiveness of the proposed algorithm is verified by results in terms of throughput maximization under the impact of chance constraint formulation in the cognitive radio networks. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
83. Entropy for evaluation of Dempster-Shafer belief function models.
- Author
-
Jiroušek, Radim, Kratochvíl, Václav, and Shenoy, Prakash P.
- Subjects
- *
ENTROPY , *PROBABILITY theory , *DISTRIBUTION (Probability theory) , *APPROXIMATION algorithms , *ANALOGY - Abstract
Applications of Dempster-Shafer (D-S) belief functions to practical problems involve difficulties arising from their high computational complexity. One can use space-saving factored approximations such as graphical belief function models to solve them. Using an analogy with probability distributions, we represent these approximations in the form of compositional models. Since no theoretical apparatus similar to probabilistic information theory exists for D-S belief functions (e.g., dissimilarity measure analogous to the Kullback-Liebler divergence measure), the problems arise not only in connection with the design of algorithms seeking optimal approximations but also in connection with a criterion comparing two different approximations. In this respect, the application of the analogy with probability theory fails. Therefore, in this paper, we conduct some synthetic experiments and describe the results designed to reveal whether some belief function entropy definitions described in the literature can detect optimal approximations, i.e., that achieve their minimum for an optimal approximation. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
84. Positional Knapsack Problem: NP-hardness and approximation scheme (Brief Announcement).
- Author
-
Pedrosa, Lehilton L.C., da Silva, Mauro R.C., and Schouery, Rafael C.S.
- Subjects
KNAPSACK problems ,NP-hard problems ,DYNAMIC programming ,APPROXIMATION algorithms ,ALGORITHMS - Abstract
We present the Positional Knapsack Problem (PKP), show that it is NP-hard and admits a Fully Polynomial-Time Approximation Scheme (FPTAS). This problem is a variant of the classical Binary Knapsack Problem (KP) in which the contribution of an item to the objective function varies according to the position in which it is added. The change in the valuation adds new properties to the problem that do not hold for KP as PKP is not a generalization of KP. Our FPTAS is based on a dynamic programming algorithm and uses a recursive rounding approach, which is necessary since the objective function depends on each item's value and position. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
85. Sparse factorization of square matrices with application to neural attention modeling.
- Author
-
Khalitov, Ruslan, Yu, Tong, Cheng, Lei, and Yang, Zhirong
- Subjects
- *
LOW-rank matrices , *MATRIX decomposition , *SPARSE matrices , *MATRIX multiplications , *LEARNING problems , *APPROXIMATION algorithms - Abstract
Square matrices appear in many machine learning problems and models. Optimization over a large square matrix is expensive in memory and in time. Therefore an economic approximation is needed. Conventional approximation approaches factorize the square matrix into a number matrices of much lower ranks. However, the low-rank constraint is a performance bottleneck if the approximated matrix is intrinsically high-rank or close to full rank. In this paper, we propose to approximate a large square matrix with a product of sparse full-rank matrices. In the approximation, our method needs only N (log N) 2 non-zero numbers for an N × N full matrix. Our new method is especially useful for scalable neural attention modeling. Different from the conventional scaled dot-product attention methods, we train neural networks to map input data to the non-zero entries of the factorizing matrices. The sparse factorization method is tested for various square matrices, and the experimental results demonstrate that our method gives a better approximation when the approximated matrix is sparse and high-rank. As an attention module, our new method defeats Transformer and its several variants for long sequences in synthetic data sets and in the Long Range Arena benchmarks. Our code is publicly available 2 2 https://github.com/RuslanKhalitov/SparseFactorization.. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
86. Mean isoperimetry with control on outliers: Exact and approximation algorithms.
- Author
-
Alimi, Morteza, Daneshgar, Amir, and Foroughmand-Araabi, Mohammad-Hadi
- Subjects
- *
WEIGHTED graphs , *APPROXIMATION algorithms , *COST functions , *CUTTING stock problem , *NP-hard problems , *GRAPH algorithms - Abstract
Given a weighted graph G = (V , E) with weight functions c : E → R + and π : V → R + , and a subset U ⊆ V , the normalized cut value for U is defined as the sum of the weights of edges exiting U divided by the weight of vertices in U. The mean isoperimetry problem , ISO 1 (G , k) , for a weighted graph G is a generalization of the classical uniform sparsest cut problem in which, given a parameter k , the objective is to find k disjoint nonempty subsets of V minimizing the average normalized cut value of the parts. The robust version of the problem seeks an optimizer where the number of vertices that fall out of the subpartition is bounded by some given integer 0 ≤ ρ ≤ | V |. The problem may also be considered as the normalized version of the classical k -multiway cut problem on edge-weighted graphs. Our main result states that ISO 1 (G , k) , as well as its robust version, CRISO 1 (G , k , ρ) , subjected to the condition that each part of the subpartition induces a connected subgraph, are solvable in time O (k 2 ρ 2 π (V (T)) 3) on any weighted tree T , in which π (V (T)) is the sum of the vertex-weights. This result implies that ISO 1 (G , k) is strongly polynomial-time solvable on weighted trees when the vertex-weights are polynomially bounded and may be compared to the fact that the problem is NP-hard for weighted trees in general. As far as applications are concerned, the connectivity requirement may be interpreted as an approach to model the practical consistency of the parts, which together with having control on the size of the outlier set and applying a smooth "mean" cost function (as opposed to, say, the "max" version), characterizes our solution to CRISO 1 (G , k , ρ) on trees as one of the most flexible and accurate procedures within the framework of isoperimetry-based clustering. Also, using this, we show that both mentioned problems, ISO 1 (G , k) and CRISO 1 (G , k , ρ) as well as the ordinary robust mean isoperimetry problem RISO 1 (G , k , ρ) , admit polynomial-time O (log 1.5 | V | log log | V |) -approximation algorithms for weighted graphs with polynomially bounded weights, using the Räcke-Shah tree cut sparsifier. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
87. Upper Dominating Set: Tight algorithms for pathwidth and sub-exponential approximation.
- Author
-
Dublois, Louis, Lampis, Michael, and Paschos, Vangelis Th.
- Subjects
- *
DOMINATING set , *APPROXIMATION algorithms , *ALGORITHMS - Abstract
In the Upper Dominating Set problem, the goal is to find a minimal dominating set of maximum size. We study the complexity of parameterized algorithms for Upper Dominating Set , as well as its sub-exponential approximation. First, we prove that, under the ETH, Upper Dominating Set cannot be solved in time O (n o (k)) (improving on O (n o (k))), and in the same time we show under the same complexity assumption that for any constant ratio r and any ε > 0 , there is no r -approximation algorithm running in time O (n k 1 − ε ). Then, we settle the problem's complexity parameterized by pathwidth by giving an algorithm running in time O ⁎ (6 p w) (improving the current best O ⁎ (7 p w)), and a lower bound showing that our algorithm is the best we can get under the SETH. Furthermore, we obtain a simple sub-exponential approximation algorithm for this problem: an algorithm that produces an r -approximation in time n O (n / r) , for any desired approximation ratio r < n. We finally show that this time-approximation trade-off is tight, up to an arbitrarily small constant in the second exponent: under the randomized ETH, and for any ratio r > 1 and ε > 0 , no algorithm can output an r -approximation in time n (n / r) 1 − ε . Hence, we completely characterize the approximability of the problem in sub-exponential time. • We show that under ETH, Upper Dominating Set cannot be solved in time n o (k). • We give a 6 p w algorithm parameterized by pathwidth and show it is optimal under SETH. • We obtain a tight time-approximation trade-off under the ETH. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
88. Better guarantees for k-median with service installation costs.
- Author
-
Zhang, Zhen, Zhou, Yipeng, and Yu, Shaoqian
- Subjects
- *
APPROXIMATION algorithms , *COST , *ALGORITHMS - Abstract
k-median with service installation costs is a frequently encountered problem in applications involving multiple service requirements, which generalizes the standard k -median problem in that each client is associated with a specific service and can only be connected to the facilities where the service is installed. In this paper, we give a (13.349 + ϵ) -approximation algorithm for the k -median with service installation costs problem, improving upon the previous best approximation ratio of 18. We propose a new deterministic rounding approach to deal with the challenges caused by the service requirements, which is the crucial step in getting the improved ratio. • We give a (13.349 + ϵ) -approximation algorithm for the k -median with service installation costs problem. • We obtain a well-behaved fractional solution to the problem based on the framework of Lagrangian relaxation. • We give a new deterministic rounding approach to deal with the challenges caused by the service requirements. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
89. Approximation algorithms for the minimum power cover problem with submodular/linear penalties.
- Author
-
Liu, Xiaofei, Li, Weidong, and Dai, Han
- Subjects
- *
SUBMODULAR functions , *POLYNOMIAL approximation , *POLYNOMIAL time algorithms , *POWER (Social sciences) , *INTERIOR-point methods , *APPROXIMATION algorithms - Abstract
• We introduce the minimum power cover problem with submodular and linear penalties. • We present a combinatorial primal-dual approximation algorithm for the minimum power cover problem with submodular penalties. • We present a polynomial time approximation scheme for the minimum power cover problem with linear penalties. In this paper, we introduce the minimum power cover problem with submodular and linear penalties. Suppose U is a set of users and S is a set of sensors in a d -dimensional space R d with d ≥ 2. Each sensor can adjust its power and the relationship between the power p (s) and the radius r (s) of the service area of sensor s satisfies p (s) = c ⋅ r (s) α , where c > 0 and α ≥ 1. Let p be the power assignment for each sensor and R be the set of users who are not covered by any sensor supported by p. The objective is to minimize the total power of p plus the rejected penalty of R. For a submodular penalty function that is normalized and nondecreasing, we present a combinatorial primal-dual (3 α + 1) -approximation algorithm. For the case in which the submodular penalty function is linear, we present a polynomial time approximation scheme based on a plane subdivision technique. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
90. Distributed minimum vertex coloring and maximum independent set in chordal graphs.
- Author
-
Konrad, Christian and Zamaraev, Viktor
- Subjects
- *
INDEPENDENT sets , *APPROXIMATION algorithms , *DISTRIBUTED algorithms , *DISTRIBUTED computing , *GRAPH coloring , *GRAPH algorithms - Abstract
We give deterministic distributed (1 + ϵ) -approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O (1 ϵ log n) rounds, and our independent set algorithm has a runtime of O (1 ϵ log (1 ϵ) log ⁎ n) rounds. For coloring, existing lower bounds imply that the dependencies on 1 ϵ and log n are best possible. For independent set, we prove that Ω (1 ϵ) rounds are necessary. Both our algorithms make use of a tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O (log n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O (log 1 ϵ) layers are required as they already contain a large enough independent set. We develop a (1 + ϵ) -approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. While tree decompositions have only played a minor role in distributed computing, our work demonstrates their potential for designing efficient distributed algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
91. Hardness and approximation for the star p-Hub Routing Cost Problem in metric graphs.
- Author
-
Yeh, Hao-Ping, Lu, Wei, Chen, Li-Hsuan, Hung, Ling-Ju, Klasing, Ralf, and Hsieh, Sun-Yuan
- Subjects
- *
NP-hard problems , *HARDNESS , *RATIO analysis , *PROBLEM solving , *COST , *CHARTS, diagrams, etc. , *SPANNING trees - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
92. Multi-attribute based influence maximization in social networks: Algorithms and analysis.
- Author
-
Ni, Qiufen, Guo, Jianxiong, Du, Hongmin W., and Wang, Huan
- Subjects
- *
SOCIAL network analysis , *SOCIAL influence , *SOCIAL networks , *VIRAL marketing , *EXPECTATION-maximization algorithms , *PRODUCT attributes , *APPROXIMATION algorithms - Abstract
• The realization for multi-attribute influence maximization problem (MIMP) is proposed. • A Sandwich Approximation Algorithm for MIMP is proposed, which can get a max { f (S U) f ‾ (S U) , f _ (S L ⁎) f (S o ⁎) } (1 − 1 e) -approximation ratio. • A hypergraph is constructed and a Supermodular Degree Algorithm is proposed, its solution has an 1 / (d + 2) approximation ratio. The most valuable feature of social networks is that they can generate contents for users and spread them quickly on the network, which is a very important platform for viral marketing. Most of the related work on viral marketing focuses on the spread of single information, while a product may associate with multiple attributes in real life. Information about multiple attributes of a product propagates in the social networks simultaneously and independently. The attribute information that a user receives will determine whether he would purchase the product or not. We extend the traditional single information influence maximization problem to the multi-attribute based influence maximization problem. We also present the Multi-dimensional IC model (MIC model) for the proposed problem, then formulate the problem as the Multi-attribute based Influence Maximization Problem (MIMP). The objective function for MIMP is proved to be non-submodular, then we solve the problem with two different algorithms: the Sandwich Algorithm and the Supermodular Algorithm, whose solutions can get a m a x { f (S U) f ‾ (S U) , f _ (S L ⁎) f (S o ⁎) } (1 − 1 / e) approximation ratio and an 1 / (d + 2) approximation ratio to the optimal solution, respectively. Experiments based on the real world social network datasets verify the effectiveness and correctness of our proposed solutions. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
93. Scheduling multiple two-stage flowshops with a deadline.
- Author
-
Chen, Jianer, Huang, Minjie, and Guo, Yin
- Subjects
- *
APPROXIMATION algorithms , *KNAPSACK problems , *DEADLINES , *SCHEDULING , *CLOUD computing , *PRODUCTION scheduling - Abstract
• Research was motivated from recent research in cloud computing. • A new model for research on scheduling of multiple processors. • Computational complexity of the proposed scheduling problems. • Approximation algorithms for the proposed scheduling problems. • Relationship between the proposed scheduling problems and multiple knapsack packing. Recently, motivated by applications in cloud computing, scheduling multiple two-stage flowshops with the objective of minimizing the makespan has drawn increasing attention. Motivated by the same applications, the current paper studies the problem of scheduling multiple two-stage flowshops with a deadline, with the objective of maximizing the profit of the jobs that can be completed by the deadline. Algorithms and complexity of the problem are investigated. For the case where the number of two-stage flowshops is part of the input, we present an efficient approximation algorithm with a constant ratio. The approximation ratio is improved via a study of the relationship between the problem and the multiple knapsack problem, combined with the recent progresses in the research in approximation algorithms for the multiple knapsack problem. By integrating techniques in the study of the classical Knapsack problem and the classical Makespan problem on multiple processors, plus additional new techniques, a polynomial-time approximation algorithm with a further improved approximation ratio is developed for the case where the number of flowshops is a fixed constant. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
94. Investigating the recoverable robust single machine scheduling problem under interval uncertainty.
- Author
-
Bold, Matthew and Goerigk, Marc
- Subjects
- *
PRODUCTION scheduling , *APPROXIMATION algorithms , *POLYNOMIAL time algorithms , *SCHEDULING , *MACHINERY - Abstract
We investigate the recoverable robust single machine scheduling problem under interval uncertainty. In this setting, jobs have first-stage processing times p and second-stage processing times q and we aim to find a first-stage and second-stage schedule with a minimum combined sum of completion times, such that at least Δ jobs share the same position in both schedules. We provide positive complexity results for some important special cases of this problem, as well as derive a 2-approximation algorithm to the full problem. Computational experiments examine the performance of an exact mixed-integer programming formulation and the approximation algorithm, and demonstrate the strength of a proposed polynomial time greedy heuristic. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
95. Zero-freeness and approximation of real Boolean Holant problems.
- Author
-
Bai, Zonglei, Cao, Yongzhi, and Wang, Hanpin
- Subjects
- *
ISING model , *PARTITION functions , *CONSTRAINT satisfaction , *TAYLOR'S series , *HOMOMORPHISMS , *COUNTING , *APPROXIMATION algorithms - Abstract
• Show the complexity of approximating real Boolean Holant problems. • Present holographic transformations from the Holant problems to the Ising model. • Prove zero-freeness of the Holant problems. • Establish AP-reductions between the Holant problems and counting perfect matchings. Holant problems provide a novel framework to study the complexity of counting problems. It is a refinement to counting constraint satisfaction problems (#CSP) with a more explicit role for the constraint functions. Both graph homomorphisms and #CSP can be viewed as special cases of Holant problems. For approximation algorithms on Holant problems, the attention is focused on proving zero-freeness of the partition functions and establishing fully polynomial-time approximation schemes (FPTAS) using the Taylor expansion method. In this paper, we study the Holant problems defined by a real constraint function satisfying a generalized second-order recurrence. We present fully polynomial-time (deterministic or randomized) approximation schemes for the Holant problems except for a couple of cases. Our algorithms are established in two ways: 1) we construct holographic transformations from the Holant problems to the Ising model, and obtain the algorithms using the approaches with respect to the Ising model; 2) we prove the zero-freeness of the Holant problems, and present an algorithm based on the Taylor expansion method. In addition, for most of the other cases, there exist approximation-preserving reductions between the Holant problems and the problem of counting perfect matchings, which is a central open problem in approximate counting. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
96. Union acceptable profit maximization in social networks.
- Author
-
Rao, Guoyao, Wang, Yongcai, Chen, Wenping, Li, Deying, and Wu, Weili
- Subjects
- *
PROFIT maximization , *SOCIAL networks , *ONLINE social networks , *VIRTUAL communities , *HEURISTIC algorithms , *APPROXIMATION algorithms , *SOCIAL influence - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
97. Completeness, approximability and exponential time results for counting problems with easy decision version.
- Author
-
Antonopoulos, Antonis, Bakali, Eleni, Chalki, Aggeliki, Pagourtzis, Aris, Pantavos, Petros, and Zachos, Stathis
- Subjects
- *
STATISTICAL decision making , *APPROXIMATION algorithms , *APPROXIMATION error , *INDEPENDENT sets , *COMPLEXITY (Philosophy) , *COUNTING - Abstract
• The first TotP-complete problems under parsimonious reductions. • Hardness of approximation for these problems and some of their generalizations. • A family of hard-to-approximate instances for the complete problem Size-of-Subtree. • Exponential time hardness results for Size-of-Subtree under variants of the Exponential Time Hypothesis. • Approximation preserving reduction of the general #SAT to instances of it that are promised to be self-reducible with easy decision. Hard counting problems with easy decision version, like computing the permanent and counting independent sets, are of particular importance in counting complexity theory. TotP is the class of all self-reducible problems in # P with decision version in P. It has been a long standing open question to determine TotP -complete problems under strong reductions that preserve exactly the values of the functions (Karp), since Cook reductions blur structural differences between counting classes, specifically under Cook reductions TotP -complete problems are also # P -complete. In this paper we present the first such problems and we show some implications of these results to counting complexity. The problems that we prove to be TotP -complete under Karp reductions are: (a) #Tree-Monotone-Circuit-SAT , which further implies that it is hard to compute, both exactly and approximately, the number of satisfying assignments of monotone circuits, where the monotonicity is defined by a partial order which is given as part of the input. (b) Max-Lower-Set-Size , which implies that given a poset it is hard to compute and approximate the size of a principal upper set, and the size of the maximum lower set all elements of which share a given property P. (c) Size-of-Subtree , which directly implies that every problem in TotP admits a polynomial-time approximation algorithm the error of which depends on the amount of imbalance of the respective self-reducibility tree of the problem. We settle the worst case complexity of this problem, we provide a family of instances that are hard to approximate, and we show exponential time hardness results under variants of the exponential time hypothesis (ETH). (d) #Clustered-Monotone-SAT , which implies that approximating #SAT remains hard even on instances for which some kind of navigation among solutions is possible. Thus we narrow down any further research regarding the polynomial-time approximability of #SAT to instances with the aforementioned property. Among other implications, our results show that all these problems do not admit an FPRAS, unless NP = RP , something that we would not be able to conclude by showing them to be TotP -complete under Cook reductions.1 [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
98. Faster algorithms for orienteering and k-TSP.
- Author
-
Gottlieb, Lee-Ad, Krauthgamer, Robert, and Rika, Havana
- Subjects
- *
ORIENTEERING , *ORIENTEERS , *ALGORITHMS , *POLYNOMIAL time algorithms , *APPROXIMATION algorithms - Abstract
We consider the rooted orienteering problem in Euclidean space: Given n points P in R d , a root point s ∈ P and a budget B > 0 , find a path that starts from s , has total length at most B , and visits as many points of P as possible. This problem is known to be NP-hard, hence we study (1 − δ) -approximation algorithms. The previous Polynomial-Time Approximation Scheme (PTAS) for this problem, due to Chen and Har-Peled (2008), runs in time n O (d d / δ) 2 (d / δ) O (d) , and improving on this time bound was left as an open problem. Our main contribution is a PTAS with a significantly improved time complexity of n O (1 / δ) 2 (d / δ) O (d) . A known technique for approximating the orienteering problem is to reduce it to solving 1 / δ correlated instances of rooted k -TSP (a k -TSP tour is one that visits at least k points). However, the k -TSP tours in this reduction must achieve a certain excess guarantee (namely, their length can surpass the optimum length only in proportion to a parameter of the optimum called excess) that is stronger than the usual (1 + δ) -approximation. Our main technical contribution is to improve the running time of these k -TSP variants, particularly in its dependence on the dimension d. Indeed, our running time is polynomial even for a moderately large dimension, roughly up to d = O (log log n) instead of d = O (1). [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
99. New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints.
- Author
-
Györgyi, Péter and Kis, Tamás
- Subjects
- *
APPROXIMATION algorithms , *JOB qualifications , *TARDINESS , *PRODUCTION scheduling , *MACHINERY - Abstract
We consider single machine scheduling problems with additional non-renewable resource constraints. Examples for non-renewable resources include raw materials, energy, or money. Usually they have an initial stock and replenishments arrive over time at a-priori known time points and quantities. The jobs have some requirements from the resources and a job can only be started if the available quantity from each of the required resources exceeds the requirements of the job. Upon starting a job, it consumes its requirements which decreases the available quantities of the respective non-renewable resources. There is a broad background for this class of problems. Most of the literature concentrate on the makespan, and the maximum lateness objectives. This paper focuses on the total weighted completion time objective for which the list of the approximation algorithms is very short. We extend that list by considering new special cases and obtain new complexity results and approximation algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
100. Data-adaptive robust coordinated optimization of dynamic active and reactive power flow in active distribution networks.
- Author
-
Huang, Zhanghao, Zhang, Yachao, and Xie, Shiwei
- Subjects
- *
ELECTRICAL load , *REACTIVE power , *REACTIVE flow , *ROBUST optimization , *WIND power , *APPROXIMATION algorithms , *ECONOMIC security - Abstract
The uncertainty of wind power brings security and economic issues in active distribution networks. As an effective solution to these problems, the active/reactive optimization aims at minimizing the total operation cost and network loss by controlling multiple resources. This paper proposes a two-stage data-adaptive robust optimization model for the dynamic active-reactive power flow. The dynamic correlation between the uncertainties of active and reactive power is analyzed at two kinds of power factor modes of wind turbines and then is described by a linear affine decision rule. To characterize these uncertainties, a data-adaptive multi-band uncertainty set is constructed based on historical data, which allows the number of bands and the corresponding weight coefficients to be adjusted under different confidence levels. Subsequently, the conic relaxation and linearization techniques are performed to reformulate the robust optimization model as a mixed-integer second-order cone programming problem. A two-level solution framework, consisting of a column-and-constraint generation algorithm and an outer approximation algorithm, is employed to solve this problem. Simulation results on a modified IEEE 33-bus system indicate that the variable power factor mode is more suitable for describing the dynamic correlation than the constant power factor mode. Besides, the proposed model and method also show better practicality and solution efficiency than the existing ones. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.