294 results on '"APPROXIMATION algorithms"'
Search Results
2. An 8-approximation algorithm for [formula omitted]-labeling of unit disk graphs.
- Author
-
Ono, Hirotaka and Yamanaka, Hisato
- Subjects
- *
REPRESENTATIONS of graphs , *APPROXIMATION algorithms , *ALGORITHMS , *POLYNOMIAL time algorithms , *GRAPH labelings , *GRAPH algorithms - Abstract
Given a graph G = (V , E) , an L (2 , 1) -labeling of the graph is an assignment ℓ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u , v) , | ℓ (u) − ℓ (v) | ≥ 2 if u and v are adjacent, and ℓ (u) ≠ ℓ (v) if u and v are at distance 2. The L (2 , 1) -labeling problem is to minimize the range of ℓ (i.e., max u ∈ V (ℓ (u)) − min u ∈ V (ℓ (u)) + 1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L (2 , 1) -labeling of unit disk graphs. • An 8-approximation algorithm of L(2,1)-labeling for unit disk graphs with geometric representations is presented. • The previously known bound is 10.67. • The presented algorithm gives a simple periodic labeling based on a new way of partitioning the plane into squares. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
3. A [formula omitted]-approximation algorithm for feedback vertex set in tournaments via Sherali–Adams.
- Author
-
Aprile, Manuel, Drescher, Matthew, Fiorini, Samuel, and Huynh, Tony
- Subjects
- *
TOURNAMENTS , *ALGORITHMS , *APPROXIMATION algorithms - Abstract
We study the feedback vertex set problem in tournaments from the polyhedral point of view, and in particular we show that performing just one round of the Sherali–Adams hierarchy gives a relaxation with integrality gap 7 / 3. This allows us to derive a 7 / 3 -approximation algorithm for the feedback vertex set problem in tournaments that matches the best deterministic approximation guarantee due to Mnich, Williams, and Végh, and is a simplification and runtime improvement of their approach. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
4. Hilfer fractional delay differential equations: Existence and uniqueness computational results and pointwise approximation utilizing the Shifted-Legendre Galerkin algorithm.
- Author
-
Sweis, Hind, Abu Arqub, Omar, and Shawagfeh, Nabil
- Subjects
DELAY differential equations ,NUMERICAL analysis ,ALGORITHMS ,FRACTIONAL differential equations ,APPROXIMATION algorithms - Abstract
In this research, we investigate Hilfer-type FDDEs of both linear and nonlinear nature, with orders α and β. We studied some Riemann-Liouville, Caputo-Liouville, and Hilfer fractional derivatives properties; and then used them to convert our fractional delay problem into an equivalent fractional Volterra delay problem. After that, for the resulting fractional Volterra delay problem, using the CMT, existence-uniqueness is demonstrated. For numerical solutions, we studied the orthogonal shifted Legendre polynomials and used them as the basis for the Galerkin algorithm to find an approximation solution to the corresponding FDDE. By employing this algorithm, the provided FDDE is converted into a series of algebraic systems. By solving this system, the approximated solutions for the equation are obtained. The main algorithm advantage is that the number of needed iterations is low compared with the soft gained results. Some linear and nonlinear numerical applications together with several figures and tables are utilized to prove the performance and accuracy of the algorithm. The outcomes results are considered according to the given analysis and the numerical method was offered in the last section with several hints to guide future work. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem.
- Author
-
Çivril, A.
- Subjects
- *
APPROXIMATION algorithms , *COMBINATORIAL optimization , *ALGORITHMS - Abstract
We present a new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem. Its approximation ratio is 4 3 , which matches the current best ratio. The approximation ratio of the algorithm is 6 5 on subcubic graphs, which is an improvement upon the previous best ratio of 5 4. The algorithm is a novel extension of the primal-dual schema, which consists of two distinct phases. Both the algorithm and the analysis are much simpler than those of the previous approaches. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
6. Improved approximation algorithms for solving the squared metric k-facility location problem.
- Author
-
Zhang, Zhen, Feng, Qilong, Huang, Junyu, and Wang, Jianxin
- Subjects
- *
APPROXIMATION algorithms , *LOCATION problems (Programming) , *SEARCH algorithms , *ALGORITHMS , *GENERALIZATION - Abstract
The squared metric k -facility location problem is a frequently encountered generalization of the k -means problem, where a specific cost should be paid for opening each facility. The current best approximation ratio for this problem is 44.473 + ϵ , which was obtained using a local search algorithm. We advance the state-of-the-art for the problem by devising a Lagrangian relaxation-based algorithm that achieves an improved approximation guarantee of 36.342 + ϵ. Our improvement comes from a new deterministic rounding approach, which exploits the properties of the squared metric. • We give a (36.342 + ϵ) -approximation algorithm for the squared metric k -facility location problem. • We obtain a well-behaved fractional solution to the squared metric k -facility location problem based on the framework of Lagrangian relaxation. • We give a new deterministic rounding approach that exploits the properties of the squared metric. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
7. Complexity and approximability of Minimum Path-Collection Exact Covers.
- Author
-
Valdés Ravelo, Santiago and Fernandes, Cristina G.
- Subjects
- *
APPROXIMATION algorithms , *NP-hard problems , *COMBINATORIAL optimization , *COMPUTATIONAL complexity , *ALGORITHMS , *POLYNOMIAL time algorithms - Abstract
This work considers the Minimum Path-Collection Exact Cover (PCEC) and the Minimum k -Path Splitting Exact Cover (k-PSEC). Both problems receive a digraph G and a set P of paths in G , and their objective is to find a minimum cardinality set S of paths, whose elements are arc-disjoint and cover all arcs of G. Despite the similarities, the solutions for each problem must satisfy different properties. For k-PSEC , the set S must be obtained by splitting the paths in P in order to guarantee that no element of S has length greater than a given integer k. For PCEC , the paths in P cannot be split, and the elements of S are single arcs of G or complete paths of P. PCEC and k-PSEC have practical applications in network design and network monitoring systems, being also natural versions of graph covering problems. However, there are no theoretical studies on their complexity. This work not only presents NP-hardness results for the problems, but also proves that, unless P = NP , PCEC cannot be | P | O (1) -approximated in polynomial-time. Moreover, polynomial-time algorithms are presented for paths, cycles, and trees, and polynomial-time approximation algorithms are proposed for special cases of k-PSEC. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
8. New approximation algorithms for the heterogeneous weighted delivery problem.
- Author
-
Bilò, Davide, Gualà, Luciano, Leucci, Stefano, Proietti, Guido, and Rossi, Mirko
- Subjects
- *
APPROXIMATION algorithms , *WEIGHTED graphs , *POLYNOMIAL time algorithms , *ENERGY consumption , *ALGORITHMS - Abstract
• We study the heterogeneous weighted delivery (HWD) problem, which was introduced in [Bärtschi et al., STACS'17]. • We efficiently 8-approximate HWD with k = O (log n) agents, closing an open problem in [Bärtschi et al., ATMOS'17]. • We design a O (k) -approximation algorithm that runs in polynomial time regardless of the value of k. • We design a polynomial-time O ˜ (log 3 n) -approximation algorithm. • We show that the HWD problem is 36-approximable in polynomial time when each agent has one of two possible consumption rates. We study the heterogeneous weighted delivery (HWD) problem introduced in [Bärtschi et al., STACS'17] where k heterogeneous mobile agents (e.g., robots, vehicles, etc.), initially positioned on vertices of an n -vertex edge-weighted graph G , have to deliver m messages. Each message is initially placed on a source vertex of G and needs to be delivered to a target vertex of G. Each agent can move along the edges of G and carry at most one message at any time. Each agent has a rate of energy consumption per unit of traveled distance and the goal is that of delivering all messages using the minimum overall amount of energy. This problem has been shown to be NP-hard even when k = 1 , and is 4 ρ -approximable where ρ is the ratio between the maximum and minimum energy consumption of the agents. In this paper, we provide approximation algorithms with approximation ratios independent of the energy consumption rates. First, we design a polynomial-time 8-approximation algorithm for k = O (log n) , closing a problem left open in [Bärtschi et al., ATMOS'17]. This algorithm can be turned into an O (k) -approximation algorithm that always runs in polynomial-time, regardless of the values of k. Then, we show that HWD problem is 36-approximable in polynomial-time when each agent has one of two possible consumption rates. Finally, we design a polynomial-time O ˜ (log 3 n) -approximation algorithm for the general case. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
9. APX-hardness and approximation for the k-burning number problem.
- Author
-
Mondal, Debajyoti, Rajasingh, Angelin Jemima, Parthiban, N., and Rajasingh, Indra
- Subjects
- *
CONTAGION (Social psychology) , *NP-hard problems , *APPROXIMATION algorithms , *DIFFUSION processes , *INFORMATION processing , *GENERALIZATION , *ALGORITHMS - Abstract
Consider an information diffusion process on a graph G that starts with k > 0 burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as k other unburnt vertices. The k-burning number of G is the minimum number of steps b k (G) such that all the vertices can be burned within b k (G) steps. Note that the last step may have smaller than k unburnt vertices available, where all of them are burned. The 1-burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to k -burning number allows us to examine different worst-case contagion scenarios by varying the spread factor k. In this paper we prove that computing k -burning number is APX-hard, for any fixed constant k. We then give an O ((n + m) log n) -time 3-approximation algorithm for computing k -burning number, for any k ≥ 1 , where n and m are the number of vertices and edges, respectively. Finally, we show that even if the burning sources are given as an input, computing a burning sequence itself is an NP-hard problem. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
17. 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
18. 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
19. 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
20. An ODE method to prove the geometric convergence of adaptive stochastic algorithms.
- Author
-
Akimoto, Youhei, Auger, Anne, and Hansen, Nikolaus
- Subjects
- *
STOCHASTIC convergence , *ORDINARY differential equations , *STOCHASTIC approximation , *ALGORITHMS , *MATHEMATICAL optimization , *APPROXIMATION algorithms - Abstract
We consider stochastic algorithms derived from methods for solving deterministic optimization problems, especially comparison-based algorithms derived from stochastic approximation algorithms with a constant step-size. We develop a methodology for proving geometric convergence of the parameter sequence { θ n } n ⩾ 0 of such algorithms. We employ the ordinary differential equation (ODE) method, which relates a stochastic algorithm to its mean ODE, along with a Lyapunov-like function Ψ such that the geometric convergence of Ψ (θ n) implies – in the case of an optimization algorithm – the geometric convergence of the expected distance between the optimum and the search point generated by the algorithm. We provide two sufficient conditions for Ψ (θ n) to decrease at a geometric rate: Ψ should decrease "exponentially" along the solution to the mean ODE, and the deviation between the stochastic algorithm and the ODE solution (measured by Ψ) should be bounded by Ψ (θ n) times a constant. We also provide practical conditions under which the two sufficient conditions may be verified easily without knowing the solution of the mean ODE. Our results are any-time bounds on Ψ (θ n) , so we can deduce not only the asymptotic upper bound on the convergence rate, but also the first hitting time of the algorithm. The main results are applied to a comparison-based stochastic algorithm with a constant step-size for optimization on continuous domains. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
21. Constrained flows in networks.
- Author
-
Bang-Jensen, J., Bessy, S., and Picasarri-Arrieta, L.
- Subjects
- *
NP-complete problems , *NP-hard problems , *APPROXIMATION algorithms , *TIME complexity , *ALGORITHMS - Abstract
The support of a flow x in a network is the subdigraph induced by the arcs uv for which x (u v) > 0. We discuss a number of results on flows in networks where we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example deciding whether a network N = (D , s , t , c) has a maximum flow x such that the maximum out-degree of the support D x of x is at most 2 is NP-complete as it contains the 2-linkage problem as a very special case. Another problem which is NP-complete for the same reason is that of computing the maximum flow we can send from s to t along p paths (called a maximum p -path-flow) in N. Baier et al. (2005) gave a polynomial time algorithm which finds a p -path-flow x whose value is at least 2 3 of the value of a optimum p -path-flow when p ∈ { 2 , 3 } , and at least 1 2 when p ≥ 4. When p = 2 , they show that this is best possible unless P=NP. We show for each p ≥ 2 that the value of a maximum p -path-flow cannot be approximated by any ratio larger than 9 11 , unless P=NP. We also consider a variant of the problem where the p paths must be disjoint. For this problem, we give an algorithm which gets within a factor 1 H (p) of the optimum solution, where H (p) is the p 'th harmonic number (H (p) ∼ ln (p)). We show that in the case where the network is acyclic, we can find such a maximum p -path-flow in polynomial time for every p. We determine the complexity of a number of related problems concerning the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some sense best possible. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
22. A deterministic approximation algorithm for metric triangle packing.
- Author
-
Zhao, Jingyang and Xiao, Mingyu
- Subjects
- *
APPROXIMATION algorithms , *DETERMINISTIC algorithms , *COMPLETE graphs , *ALGORITHMS , *TRIANGLES - Abstract
Given an edge-weighted metric complete graph with n vertices, the maximum weight metric triangle packing problem is to find a set of n / 3 vertex-disjoint triangles with the total weight of all triangles in the packing maximized. Several simple methods can lead to a 2/3-approximation ratio. However, this barrier is not easy to break. Chen et al. proposed a randomized approximation algorithm with an expected ratio of (0.66768 − ε) for any constant ε > 0. In this paper, we improve the approximation ratio to (0.66835 − ε). Furthermore, we can derandomize our algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
23. New algorithms for fair k-center problem with outliers and capacity constraints.
- Author
-
Wu, Xiaoliang, Feng, Qilong, Xu, Jinhui, and Wang, Jianxin
- Subjects
- *
APPROXIMATION algorithms , *POLYNOMIAL approximation , *METRIC spaces , *POLYNOMIAL time algorithms , *ALGORITHMS - Abstract
The fair k -center problem has been paid lots of attention recently. In the fair k -center problem, we are given a set X of points in a metric space and a parameter k ∈ Z + , where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k -center problem objective is minimized. In this paper, we consider the fair k -center problem with outliers and capacity constraints, denoted as the fair k -center with outliers (F k CO) problem and the capacitated fair k -center (CF k C) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + ϵ) -approximations with FPT time for the F k CO and CF k C problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the F k CO problem with some reasonable assumptions. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
24. Complementary influence maximization under comparative linear threshold model.
- Author
-
Yang, Wujian, Shi, Qihao, Yan, Jiangzhe, Wang, Can, Song, Mingli, and Wu, Minghui
- Subjects
- *
SOCIAL networks , *APPROXIMATION algorithms , *ALGORITHMS - Abstract
The influence maximization problem asks to find a small number of early adopters of a product in a social network, such that the expected number of total adoptions is maximized over the network. The problem has been well-studied, but most of the studies focus on the case of a single product or purely competitive products. This paper proposes a new influence diffusion model for multiple complementary products, namely, the comparative linear threshold (Com-LT) model. Under the Com-LT model, we model the complementary relation by reducing the thresholds of nodes. With this model, we study two problems: SelfInfMax and CompInfMax. We prove that these two problems are both NP-Hard under the Com-LT model. For both the SelfInfMax and the CompInfMax problem, we theoretically analyze the monotonicity and submodularity, and accordingly leverage lower bound optimization to devise non-trivial effective approximation algorithms. We conduct experiments over 4 real-world datasets. The experimental results demonstrate the correctness and efficiency of the proposed algorithms. • We study the complementary version of the influence maximization problem. • We propose Com-LT model to describe the influence spread of non- competitive products. • We studied the SelfInfMax and the CompInfMax problem and show their hardness. • We propose approximation algorithms with high quality feasible solutions. • We conduct experiments on real networks and show the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
25. Efficient algorithms for finding diversified top-k structural hole spanners in social networks.
- Author
-
Li, Mengshi, Peng, Jian, Ju, Shenggen, Liu, Quanhui, Li, Hongyou, Liang, Weifa, Yu, Jeffrey Xu, and Xu, Wenzheng
- Subjects
- *
WRENCHES , *SOCIAL networks , *ALGORITHMS , *VIDEO coding , *INFORMATION sharing , *APPROXIMATION algorithms - Abstract
A structural hole spanner in a social network is a user who bridges multiple communities, and he can benefit from acting the bridging role, such as arbitrating information across different communities or getting earlier access to valuable and diverse information. Existing studies of finding hole spanners either identified redundant hole spanners (i.e., communities bridged by different hole spanners are redundant) or found nonredundant hole spanners only by network structure. Unlike the existing studies, we not only study a problem of finding top- k hole spanners that connect nonredundant communities in the social network, but also consider the tie strengths between different pairs of users and the different information sharing rates of different users, so that after removing the found users, the number of blocked information diffusion is maximized. In addition, we devise a novel (1 - 1 e) -approximation algorithm for the problem, where e is the base of the natural logarithm. We further propose a fast randomized algorithm with a smaller time complexity. Our experiment results demonstrate that, after removing the nodes found by the proposed two algorithms, the numbers of blocked information diffusion can be up to 80% larger than those by existing algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
26. A 2/3-approximation algorithm for vertex-weighted matching.
- Author
-
Al-Herz, Ahmed and Pothen, Alex
- Subjects
- *
BIPARTITE graphs , *APPROXIMATION algorithms , *WEIGHTED graphs , *MAGNITUDE (Mathematics) , *ALGORITHMS - Abstract
We consider the maximum vertex-weighted matching problem (MVM) for non-bipartite graphs in which non-negative weights are assigned to the vertices of a graph and a matching that maximizes the sum of the weights of the matched vertices is desired. In earlier work we have described a 2 / 3 -approximation algorithm for the MVM on bipartite graphs (Florin Dobrian et al., 2019). Here we show that a 2 / 3 -approximation algorithm for MVM on non-bipartite graphs can be obtained by restricting the length of augmenting paths to at most three. The algorithm has time complexity O (m log Δ + n log n) , where n is the number of vertices, m is the number of edges, and Δ is the maximum degree of a vertex. The approximation ratio of the algorithm is obtained by considering failed vertices , i.e., vertices that the approximation algorithm fails to match but the exact algorithm does. We show that there are two distinct heavier matched vertices that we can charge each failed vertex to. Our proof techniques characterize the structure of augmenting paths in a novel way. We have implemented the 2 / 3 -approximation algorithm and show that it runs in under a minute on graphs with tens of millions of vertices and hundreds of millions of edges. We compare its performance with five other algorithms: an exact algorithm for MVM, an exact algorithm for the maximum edge-weighted matching (MEM) problem, as well as three approximation algorithms. The approximation algorithms include a 1 / 2 -approximation algorithm for MVM, and (2 / 3 − ε) - and (1 − ε) -approximation algorithms for the MEM. In our test set of nineteen problems, there are graphs on which the exact algorithms fail to terminate in 100 hours. In addition, the new 2 / 3 -approximation algorithm for MVM outperforms the other approximation algorithms by either being faster (often by orders of magnitude) or obtaining better weights. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
27. An improved approximation for Maximum[formula omitted]-dependent Set on bipartite graphs.
- Author
-
Hosseinian, Seyedmohammadhossein and Butenko, Sergiy
- Subjects
- *
BIPARTITE graphs , *ALGORITHMS , *APPROXIMATION algorithms - Abstract
We present a (1 + k k + 2) -approximation algorithm for the Maximum k - dependent Set problem on bipartite graphs for any k ≥ 1. For a graph with n vertices and m edges, the algorithm runs in O (k m n) time and improves upon the previously best-known approximation ratio of 1 + k k + 1 established by Kumar et al. (2014). Our proof also indicates that the algorithm retains its approximation ratio when applied to the (more general) class of König–Egerváry graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
28. Metric [formula omitted]-median clustering in insertion-only streams.
- Author
-
Braverman, Vladimir, Lang, Harry, Levin, Keith, and Rudoy, Yevgeniy
- Subjects
- *
CLUSTER analysis (Statistics) , *ALGORITHMS , *APPROXIMATION algorithms - Abstract
We present a low-constant approximation for the metric k -median problem on insertion-only streams using O (ε − 3 k log n) space. In particular, we present a streaming (O (ε − 3 k log n) , 2 + ε) -bicriterion solution that reports cluster weights. Running the offline approximation algorithm due to Byrka et al. (2015) on this bicriterion solution yields a (17. 66 + ε) -approximation (Guha et al., 2003; Charikar et al., 2003; Braverman et al., 2011). Our result matches the best-known space requirements for streaming k -median clustering while significantly improving the approximation accuracy. We also provide a lower bound, showing that any polylog (n) -space streaming algorithm that maintains an (α , β) -bicriterion must have β ≥ 2. Our technique breaks the stream into segments defined by jumps in the optimal clustering cost, which increases monotonically as the stream progresses. By storing an accurate summary of recent segments of the stream and a lower-space summary of older segments, our algorithm maintains a (O (ε − 3 k log n) , 2 + ε) -bicriterion solution for the entirety of the stream. In addition to our main result, we introduce a novel construction that we call a candidate set. This is a collection of points that, with high probability, contains k points that yield a near-optimal k -median cost. We present an algorithm called monotone faraway sampling (MFS) for constructing a candidate set in a single pass over a data stream. We show that using this candidate set in tandem with a coreset speeds up the search for a solution set of k cluster centers upon termination of the data stream. While coresets of smaller asymptotic size are known, comparative simplicity of MFS makes it appealing as a practical technique. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
29. Neural-network-based discounted optimal control via an integrated value iteration with accuracy guarantee.
- Author
-
Ha, Mingming, Wang, Ding, and Liu, Derong
- Subjects
- *
ARTIFICIAL neural networks , *ALGORITHMS , *NONLINEAR systems , *SYSTEM dynamics , *NEURAL circuitry , *APPROXIMATION algorithms - Abstract
A data-based value iteration algorithm with the bidirectional approximation feature is developed for discounted optimal control. The unknown nonlinear system dynamics is first identified by establishing a model neural network. To improve the identification precision, biases are introduced to the model network. The model network with biases is trained by the gradient descent algorithm, where the weights and biases across all layers are updated. The uniform ultimate boundedness stability with a proper learning rate is analyzed, by using the Lyapunov approach. Moreover, an integrated value iteration with the discounted cost is developed to fully guarantee the approximation accuracy of the optimal value function. Then, the effectiveness of the proposed algorithm is demonstrated by carrying out two simulation examples with physical backgrounds. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
30. Coherent network partitions: Characterizations with cographs and prime graphs.
- Author
-
Angeleska, Angela, Omranian, Sara, and Nikoloski, Zoran
- Subjects
- *
BIPARTITE graphs , *ALGORITHMS , *APPROXIMATION algorithms , *SUBGRAPHS - Abstract
We continue to study coherent partitions of graphs whereby the vertex set is partitioned into subsets that induce biclique spanned subgraphs. The problem of identifying the minimum number of edges to obtain biclique spanned connected components (CNP), called the coherence number, is NP-hard even on bipartite graphs. Here, we propose a graph transformation geared towards obtaining an O (log n) -approximation algorithm for the CNP on a bipartite graph with n vertices. The transformation is inspired by a new characterization of biclique spanned subgraphs. In addition, we study coherent partitions on prime graphs, and show that finding coherent partitions reduces to the problem of finding coherent partitions in a prime graph. Therefore, these results provide future directions for approximation algorithms for the coherence number of a given graph. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
31. Approximation algorithms for sorting permutations by extreme block-interchanges.
- Author
-
Pai, Jayakumar and Chitturi, Bhadrachalam
- Subjects
- *
PERMUTATIONS , *ALGORITHMS , *COMPUTER engineering , *COMPUTER networks , *SUFFIXES & prefixes (Grammar) , *APPROXIMATION algorithms - Abstract
Sorting permutations with various operations has applications in macro rearrangement of genes in a genome and the design of computer interconnection networks. Block-interchange is a powerful operation that swaps two substrings that are called as blocks in literature, in a given permutation. When the blocks are restricted to be adjacent then one obtains a well studied operation: transposition. We call either a prefix or a suffix as an extreme. Restricting one of the swapped blocks to be an extreme in block-interchange operation yields a prefix or a suffix block-interchange respectively, the two types of extreme block-interchanges. For prefix block-interchange operation over permutations we design: (i) an optimum algorithm to sort reverse permutation, R n , in n /2 moves, (ii) a simple 2-approximation algorithm, and (iii) for permutations with O (1) cycles, a 4/3 approximation algorithm. Due to symmetry, these results apply to suffix block-interchange operation also. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
32. A more efficient deterministic annealing neural network algorithm for the max-bisection problem.
- Author
-
Jiang, Shicong and Dang, Chuangyin
- Subjects
- *
ALGORITHMS , *SIMULATED annealing , *PROBLEM solving , *DETERMINISTIC algorithms , *METAHEURISTIC algorithms , *APPROXIMATION algorithms , *CONSTRAINED optimization - Abstract
• Transform the max-bisection problem to a linearly constrained optimization problem. • Propose a deterministic annealing neural network algorithm by introducing a barrier function in square-root form. • Prove the existence of the integral minimum solution of the max-bisection problem in theory and the proof is simpler than other algorithms. • Experimental results show that the proposed method outperforms other methods. The max-bisection problem has extensive applications in network engineering, making it imperative to develop effective methods to solve this problem. However, the efficient computation on this problem remains challenging due to its NP-hard computational complexity. To address this question, in this paper, we transform the max-bisection problem to an artificial linearly constrained optimization problem and develop a modified deterministic annealing neural network algorithm by introducing a barrier function. The barrier parameter of this function acts as the temperature in the annealing process and decreases from a large positive number to zero. The initial value of the barrier parameter promises that the artificial problem is convex and can be easily solved at the beginning of the descending process. The solution to the original max-bisection problem is finally obtained through a descent algorithm, in which the bound limit of the solution is always satisfied as long as the iteration step length is less than one. We have proved the theoretical convergence of the proposed algorithm. Numerical results demonstrate that the proposed algorithm has several advantages over both the approximation algorithms and metaheuristic methods. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
33. Approximate set union via approximate randomization.
- Author
-
Fu, Bin, Gu, Pengfei, and Zhao, Yuming
- Subjects
- *
APPROXIMATION algorithms , *POLYNOMIAL time algorithms , *ALGORITHMS - Abstract
• A new randomized approximation algorithm for the size of set union problem. • The algorithm relaxes the computational model that requires exact set size and random element generator. • The algorithm runs in constant rounds and runs sublinear in time under certain condition. We develop a randomized approximation algorithm for the size of set union problem | A 1 ∪ A 2 ∪... ∪ A m | , which is given a list of sets A 1 ,... , A m with approximate set size m i for A i with m i ∈ ((1 − β L) | A i | , (1 + β R) | A i |) , and biased random generators with probability Prob (x = RandomElement (A i)) ∈ [ 1 − α L | A i | , 1 + α R | A i | ] for each input set A i and element x ∈ A i , where i = 1 , 2 ,... , m and α L , α R , β L , β R ∈ (0 , 1). The approximation ratio for | A 1 ∪ A 2 ∪... ∪ A m | is in the range [ (1 − ϵ) (1 − α L) (1 − β L) , (1 + ϵ) (1 + α R) (1 + β R) ] for any ϵ ∈ (0 , 1). The complexity of the algorithm is measured by both time complexity and round complexity. One round of the algorithm has non-adaptive accesses to those RandomElement (A i) functions 1 ≤ i ≤ m , and membership queries (x ∈ A i ?) to input sets A i with 1 ≤ i ≤ m. Our algorithm gives an approximation scheme with O (m ⋅ (log m) 7) running time and O (log m) rounds in contrast to the existing algorithm [1] that needs Ω (m) rounds in the worst case with O ((1 + ϵ) m / ϵ 2) running time, where m is the number of sets. Our algorithm gives a flexible tradeoff with time complexity O (m 1 + ξ) and round complexity O (1 ξ) for any ξ ∈ (0 , 1). Our algorithm runs sublinear in time under certain condition that each element in A 1 ∪ A 2 ∪... ∪ A m belongs to m a sets for any fixed a > 0 , to our best knowledge, we have not seen any sublinear results about this problem. Our algorithm can handle input sets that can generate random elements with bias, and its approximation ratio depends on the bias. We prove that it is #P-hard to count the number of lattice points in a set of balls, and we also show that there is no polynomial time algorithm to approximate the number of lattice points in the intersection of n -dimensional balls unless P=NP. As applications of our algorithm, we propose approximation algorithms for counting the number of lattice points in a union of high dimensional balls and for the maximal coverage problem with balls. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
34. Deterministic approximation algorithm for submodular maximization subject to a matroid constraint.
- Author
-
Sun, Xin, Xu, Dachuan, Guo, Longkun, and Li, Min
- Subjects
- *
DETERMINISTIC algorithms , *SUBMODULAR functions , *ALGORITHMS , *SET functions , *INFINITE series (Mathematics) , *MATROIDS , *APPROXIMATION algorithms , *CURVATURE - Abstract
• Present a deterministic approximation algorithm for submodular maximization with a curvature parameter α. • Generalize the previous deterministic 0.5008-approximation due to Buchbinder et al., achieving an identical ratio of 0.5008 when α = 1. • Achieve a ratio of 1 for α = 0 for which the function is actually linear that the problem is polynomial solvable. • Devise more sophisticated analysis on the inequalities about monotonicity with curvature via mathematical tools such as infinite series. In this paper, we study the generalized submodular maximization problem with a non-negative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter α ∈ [ 0 , 1 ] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for α = 1. For general value of the curvature parameter α ∈ [ 0 , 1 ] , we present an approximation algorithm with a factor of 1 + h α (y) + Δ ⋅ [ 3 + α − (2 + α) y − (1 + α) h α (y) ] 2 + α + (1 + α) (1 − y) , where y ∈ [ 0 , 1 ] is a predefined parameter for tuning the ratio. In particular, when α = 1 we obtain a ratio 0.5008 when setting y = 0.9 , coinciding with the renowned state-of-art approximate ratio; when α = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
35. Minimizing total interference in asymmetric sensor networks.
- Author
-
Abu-Affash, A. Karim, Carmi, Paz, and Katz, Matthew J.
- Subjects
- *
SENSOR networks , *WIRELESS sensor networks , *PROBLEM solving , *NP-complete problems , *ALGORITHMS - Abstract
The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common one is the receiver-centric, in which the interference of a node p is defined as the number of other nodes whose transmission range covers p. In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized. For the one-dimensional case, we show how to solve the problem optimally in O (n 3) time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
36. Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs.
- Author
-
Zhou, Peiyan, Jiang, Haitao, Zhu, Daming, and Zhu, Binhai
- Subjects
- *
APPROXIMATION algorithms , *LINEAR programming , *ALGORITHMS , *LINEAR systems - Abstract
The Maximum Vertex Coverage problem (abbreviated as MVC) is to maximum the number of edges covered by a set of vertices of size exactly K on a graph. This problem is the dual of the vertex cover problem and has attracted a lot of interests in the literature of approximation algorithm. So far, the best approximation factor for the MVC problem is 3/4, which is obtained using an LP-rounding method. The main results of this paper are new approximation algorithms for MVC on cubic graphs and 3-bounded graphs (the vertex degrees are at most 3). The approximation factor on cubic graphs is 79/90 (≈0.878), which is tight by analyzing the existence of a feasible solution for a linear programming system. This algorithm can also be extended to 3-bounded graphs and guarantees an approximation factor of 19/24 (≈0.792). [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
37. Scheduling with variable-length calibrations: Two agreeable variants.
- Author
-
Chen, Hua, Chen, Lin, Zhang, Guochuan, and Chau, Vincent
- Subjects
- *
ALGORITHMS , *SCHEDULING , *PRODUCTION scheduling , *APPROXIMATION algorithms , *CALIBRATION - Abstract
• Scheduling problem with different types of calibrations on a single machine. • Two models are considered: jobs have agreeable deadlines and calibrations costs are agreeable. • Constant approximation algorithms are given. Machines usually require maintenance after running a fixed period. A calibration at a cost has to be performed during the process. Finding a feasible schedule minimizing the total cost of calibrations is of great importance. In this paper, we deal with a single machine scheduling model with K types of calibrations. A calibration of type k ∈ { 1 , ... , K } can be made instantaneously at any time point, which incurs a cost f k and can keep the machine active for a length T k. Given a set of n jobs with release times, deadlines, and processing times, the goal is to minimize the total cost of calibrations by assigning all jobs in the calibrated state, where job preemption is allowed. We investigate two agreeable settings. Regarding agreeable jobs, later release times imply later deadlines. We establish a pseudo-polynomial time optimal algorithm and a (3 + ε) -approximation algorithm. Moreover, if the largest job processing time is no more than any calibration length, it admits a (2 + ε) -approximation algorithm. As for agreeable calibrations, where the cost of each calibration is proportional to its length, a 2-approximation algorithm is presented. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
38. Approximation algorithms for fuzzy C-means problem based on seeding method.
- Author
-
Liu, Qian, Liu, Jianxin, Li, Min, and Zhou, Yang
- Subjects
- *
APPROXIMATION algorithms , *ALGORITHMS , *FUZZY algorithms , *SEEDS - Abstract
• A new seeding algorithm is proposed for the fuzzy C-means problem. • Theoretical guarantees for both the new seeding algorithm and the fuzzy C-means++ algorithm are given. • Numerical experiments show the effectiveness of the new algorithm. As a kind of important soft clustering model, the fuzzy C -means method is widely applied in many fields. In this method, instead of the strict distributive ability in the classical k -means method, all the sample points are endowed with degrees of membership to each center to depict the fuzzy clustering. In this paper, we show that the fuzzy C -means++ algorithm, which introduces the k -means++ algorithm as a seeding strategy, gives a solution for which the approximation guarantee is O (k 2 ln k). A novel seeding algorithm is then designed based on the contribution of the fuzzy potential function, which improves the approximation ratio to O (k ln k). Preliminary numerical experiments are proposed to support the theoretical results of this paper. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
39. An improved algorithm for a two-stage production scheduling problem with an outsourcing option.
- Author
-
Jiang, Xiaojuan, Zhang, An, Chen, Yong, Chen, Guangting, and Lee, Kangbok
- Subjects
- *
CONTRACTING out , *POLYNOMIAL time algorithms , *PRODUCTION scheduling , *ALGORITHMS , *BATCH processing , *APPROXIMATION algorithms , *FLOW shops - Abstract
We consider a two-stage production scheduling problem where each operation can be outsourced or processed in-house. For each operation in the same machine, the ratio of its outsourcing cost to its processing time is constant. The objective is to minimize the sum of the makespan and the total outsourcing cost. It is known that this problem is either polynomial time solvable or NP-hard according to the conditions of the ratios. Even though approximation algorithms for NP-hard cases had been developed, their tight worst-case performance ratios are still open. In this paper, we carefully analyze the approximation algorithms to identify their tight worst-case performance ratios for cases. In one case, we propose a new approximation algorithm with a better and tight worst-case performance ratio. In the process of analyzing the algorithm, we propose a technique utilizing nonlinear optimization. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
40. On Lagrangian relaxation for constrained maximization and reoptimization problems.
- Author
-
Kulik, Ariel, Shachnai, Hadas, and Tamir, Gal
- Subjects
- *
SUBSET selection , *ASSIGNMENT problems (Programming) , *INDEPENDENT sets , *ALGORITHMS , *APPROXIMATION algorithms - Abstract
We prove a general result demonstrating the power of Lagrangian relaxation in solving constrained maximization problems with arbitrary objective functions. This yields a unified approach for solving a wide class of subset selection problems with linear constraints. Given a problem in this class and some small ε ∈ (0 , 1) , we show that if there exists an r -approximation algorithm for the Lagrangian relaxation of the problem, for some r ∈ (0 , 1) , then our technique achieves a ratio of r r + 1 − ε to the optimal, and this ratio is tight. Using the technique we obtain (re)approximation algorithms for natural (reoptimization) variants of classic subset selection problems, including real-time scheduling, the maximum generalized assignment problem (GAP) and maximum weight independent set. For all of the problems studied in this paper, the number of calls to the r -approximation algorithm, used by our algorithms, is linear in the input size and in log (1 ∕ ε) for inputs with a cardinality constraint, and polynomial in the input size and in log (1 ∕ ε) for inputs with an arbitrary linear constraint. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
41. On the complexity of min–max–min robustness with two alternatives and budgeted uncertainty.
- Author
-
Chassein, André and Goerigk, Marc
- Subjects
- *
BACKPACKS , *KNAPSACK problems , *APPROXIMATION algorithms , *UNCERTAINTY , *ROBUST optimization , *COMBINATORIAL optimization , *ALGORITHMS - Abstract
We study robust solutions for combinatorial optimization problems with budgeted uncertainty sets in the min–max–min setting, where the decision maker is allowed to choose a set of k different solutions from which one can be chosen after the uncertain scenario has been revealed. We first show how the problem can be decomposed into polynomially many subproblems if k is fixed. We then consider the special case where k = 2 , i.e., one is allowed to choose two different solutions to hedge against the uncertainty. Using the decomposition, we provide polynomial-time algorithms for the unconstrained combinatorial optimization problem, the matroid maximization problem, the selection problem, and the shortest path problem on series–parallel graphs. The shortest path problem on general graphs turns out to be NP -hard. We show how to transform approximation algorithms for minimization subproblems to approximation algorithms for the robust problem and study the knapsack problem to show that this does not hold for maximization problems in general. We present a PTAS for the corresponding subproblem and prove that the min–max–min knapsack problem with k = 2 is not approximable at all. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
42. Approximation of fixed points and fractal functions by means of different iterative algorithms.
- Author
-
Navascués, M.A.
- Subjects
- *
APPROXIMATION algorithms , *APPLIED mathematics , *METRIC spaces , *ALGORITHMS , *CONTRACTIONS (Topology) , *PROLOGUES & epilogues - Abstract
Banach's contraction principle is a fundamental result in pure and applied mathematics, and all the fields of physics. In this paper a new type of contraction, called in the text partial contractivity, is presented in the framework of b-metric spaces (an extension of the usual metric spaces). The new mappings generalize the classical Banach contractions, that appear as a particular case. The properties of the new self-maps are studied, giving sufficient conditions for the existence and uniqueness of their fixed points. Afterwords three different iterative algorithms for the approximation of critical points (Picard, Ishikawa and Karakaya) are considered, concerning their convergence and stability. These findings are applied to the approximation of fractal functions, coming from contractive and non-contractive operators. • Definition of a new type of contraction. • Existence and uniqueness of fixed points for this self-map. • Study of Ishikawa and Karakaya algorithms for the approximation of critical points. • Analysis of convergence and stability of these procedures. • Application to the approximation of fractal functions. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
43. Advice complexity of adaptive priority algorithms.
- Author
-
Boyar, Joan, Larsen, Kim S., and Pankratov, Denis
- Subjects
- *
ALGORITHMS , *ADVICE , *ONLINE algorithms , *TRIANGLES , *APPROXIMATION algorithms , *GREEDY algorithms - Abstract
The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7 n / 22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7 n / 22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
44. Improved deterministic algorithms for non-monotone submodular maximization.
- Author
-
Sun, Xiaoming, Zhang, Jialin, Zhang, Shuo, and Zhang, Zhijie
- Subjects
- *
APPROXIMATION algorithms , *CONSTRAINT algorithms , *DETERMINISTIC algorithms , *COMBINATORIAL optimization , *ALGORITHMS , *BACKPACKS - Abstract
Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 − o (1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
45. A survey on algorithms for Nash equilibria in finite normal-form games.
- Author
-
Li, Hanyu, Huang, Wenhan, Duan, Zhijian, Mguni, David Henry, Shao, Kun, Wang, Jun, and Deng, Xiaotie
- Subjects
NASH equilibrium ,ALGORITHMS ,GAME theory ,ARTIFICIAL intelligence ,COMPUTER science - Abstract
Nash equilibrium is one of the most influential solution concepts in game theory. With the development of computer science and artificial intelligence, there is an increasing demand on Nash equilibrium computation, especially for Internet economics and multi-agent learning. This paper reviews various algorithms computing the Nash equilibrium and its approximation solutions in finite normal-form games from both theoretical and empirical perspectives. For the theoretical part, we classify algorithms in the literature and present basic ideas on algorithm design and analysis. For the empirical part, we present a comprehensive comparison on the algorithms in the literature over different kinds of games. Based on these results, we provide practical suggestions on implementations and uses of these algorithms. Finally, we present a series of open problems from both theoretical and practical considerations. • A classification on Nash equilibrium algorithms in the literature with basic ideas on design and analysis presented. • A comprehensive comparison on Nash equilibrium algorithms in the literature over different kinds of games. • Practical suggestions on implementations and uses of Nash equilibrium algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
46. Algorithms and hardness results for edge total domination problem in graphs.
- Author
-
Henning, Michael A., Pandey, Arti, Sharma, Gopika, and Tripathi, Vikash
- Subjects
- *
BIPARTITE graphs , *DOMINATING set , *PLANAR graphs , *NP-complete problems , *APPROXIMATION algorithms , *ALGORITHMS , *HARDNESS - Abstract
For a graph G = (V , E) without an isolated edge, a set D ⊆ E is an edge total dominating set of G if every edge e ∈ E is adjacent to at least one edge of D. The Minimum Edge Total Dominating Set problem is to compute a minimum cardinality edge total dominating set of G. It is known that the decision version of the problem is NP-complete for bipartite graphs, chordal graphs, and planar graphs. On the positive side, the problem is efficiently solvable for trees. In this paper, we further study the complexity of this problem in other graph classes. We design a linear-time algorithm to compute a minimum cardinality edge total dominating set in chain graphs, a subclass of bipartite graphs. We also propose linear-time algorithms for two subclasses of chordal graphs, namely, split graphs and proper interval graphs with no cut vertices. In addition, we show that the problem is APX-complete for graphs with maximum degree 3 and propose an approximation algorithm for the problem in k -regular graphs, where k ≥ 4. We discuss the complexity difference between the Minimum Edge Dominating Set problem and Minimum Edge Total Dominating Set problem which seem to be closely related. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
47. A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity.
- Author
-
Chen, Shengminjie, Du, Donglei, Yang, Ruiqi, Yang, Wenguo, and Zhang, Yapu
- Subjects
- *
APPROXIMATION algorithms , *INTEGERS , *EXPECTATION-maximization algorithms , *ALGORITHMS , *RANDOM sets - Abstract
In this work, we investigate the problem of maximizing nonmonotone DR-submodular function (possibly negative) subject to cardinality constraints on an integer lattice space. We propose a M -Threshold Decrease Algorithm that uses a compensation constant M from a special decomposition h (x) = f (x) − g (x) , which achieves a 1 − e − δ − ϵ approximation guarantee. To ensure that the algorithm ends in finite time, the supremum of δ is δ (ϵ) = ϵ max s ∈ Ω h (χ s | 0) 2 k max s ∈ Ω g (χ s | 0) + ϵ max s ∈ Ω h (χ s | 0). If max s ∈ Ω h (χ s | 0) > 2 k max s ∈ Ω g (χ s | 0) , there exists ϵ ⁎ = arg max ϵ ∈ (0 , 1) 1 − e − δ (ϵ) − ϵ such that 1 − e − δ (ϵ ⁎) − ϵ ⁎ > 0. This implies that there is a valid δ such that 1 − e − δ − ϵ > 0. To accelerate the algorithm, we employ a random subset to replace the ground set and propose a Random M -Threshold Decrease Algorithm, where δ (ϵ) = ϵ r max s ∈ Ω h (χ s | 0) 2 n k max s ∈ Ω g (χ s | 0) + [ k (n − r) + ϵ r ] max s ∈ Ω h (χ s | 0) with r being the size of the random subset and n being the size of the ground set. Furthermore, we demonstrate that, based on the DR-ratio γ d and the DS decomposition, the M -Threshold Decrease Algorithm is also suitable for solving the monotone non-DR-submodular maximization problem, achieving a 1 − e − γ d δ − O (ϵ) approximation guarantee. Because γ d is a challenging metric to calculate, we refine the M -Threshold Decrease Algorithm, which can return an estimate of γ d. To the best of our knowledge, this is the first time that a single factor approximation ratio has been proposed for the nonmonotone DR-submodular maximization problem (possibly negative) subject to cardinality constraints. • This paper adopts the decomposition structure to compensate the non-monotonicity and non-negativity for DR-submodular maximization. • Using a compensation constant M , we design a 1 − e − δ − ϵ approximation algorithm, namely M -Threshold Decrease Algorithm. • Based on the DR-ratio γ d , our algorithm is a 1 − e − δ γ d − O (ϵ) approximation algorithm for monotone non-DR-submodular maximization. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
48. An approximation algorithm for high-dimensional table compression on balanced [formula omitted]-partite graph.
- Author
-
Li, Guangfeng, Sun, Jian, Sun, Zhiren, Du, Donglei, and Zhang, Xiaoyan
- Subjects
- *
SEMIDEFINITE programming , *APPROXIMATION algorithms , *ALGORITHMS - Abstract
This paper considers the high-dimensional table compression problem on balanced k -partite graph. The objective is to choose half of the vertices from each of the k -partite to maximize the total weight of edges connecting the chosen vertices. Our main contribution is a 0.8785-approximation algorithm for the high-dimensional table compression problem by introducing the α - i n d e p e n d e n t solutions through Lasserre semidefinite programming. This new algorithm improved two previous low-dimensional results, namely the 0.8731-approximation algorithm of Wu et al. for the one-dimensional case and the 0.6708-approximation of Xu and Du for the two-dimensional case. [Display omitted] • Present a 0.8785-approximation algorithm for high-dimensional table compression problem. • Obtain a group of independent optimal solutions through Lasserre hierarchy semidefinite programming. • The integer solutions to the original problem are obtained through deformed random hyperplane recognition. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
49. Sparse and robust estimation with ridge minimax concave penalty.
- Author
-
Jiang, He, Zheng, Weihua, and Dong, Yao
- Subjects
- *
FEATURE selection , *ALGORITHMS , *APPROXIMATION algorithms , *PREDICTION models , *DATA mining , *DATA analysis - Abstract
• Derived a novel penalty function with ridge and minimax concave penalty. • A simple algorithm was designed based on the local quadratic approximation. • Derived the forecasting and estimation error bounds of the proposed estimator. • Experiment reveals that our developed models get better performance. Feature selection is an important procedure that is used in data mining to extract valuable information from large quantities of data. Existing penalization methods use a single penalty function to select important features. However, these methods do not yield sufficiently accurate predictions and selection outcomes. Therefore, construction of a concise and efficient prediction model would be beneficial. In this study, we propose a novel penalty function using a ridge and minimax concave penalty to overcome the limitations of individual penalty functions. Furthermore, we introduce a robust penalized feature selection method with Huber loss function, which is implemented by a local approximation algorithm. The theoretical properties of the algorithm have been described. Simulated and real-world data analyses are used to demonstrate the efficacy of the proposed method. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
50. Sampling-based dimension reduction for subspace approximation with outliers.
- Author
-
Deshpande, Amit and Pratap, Rameshwar
- Subjects
- *
APPROXIMATION algorithms , *KRYLOV subspace , *COST functions , *POWER (Social sciences) , *AFFINAL relatives , *ALGORITHMS - Abstract
• Consider the problem of finding low-rank approximations for norm in presence of ℓ p outliers in the dataset, where p ≥ 2. • Technique is sampling based and suggests additive and multiplicative approximation guarantees for the problem. • We extend our results to M-estimator loss functions and affine subspace approximation in presence of outliers. The subspace approximation problem with outliers, for given n points in d dimensions x 1 , x 2 , ... , x n ∈ R d , an integer 1 ≤ k ≤ d , and an outlier parameter 0 ≤ α ≤ 1 , is to find a k -dimensional linear subspace of R d that minimizes the sum of squared distances to its nearest (1 − α) n points. More generally, the ℓ p subspace approximation problem with outliers minimizes the sum of p -th powers of distances instead of the sum of squared distances. Even the case of p = 2 or robust PCA is non-trivial, and previous work requires additional assumptions on the input or generative models for it. Any multiplicative approximation algorithm for the subspace approximation problem with outliers must solve the robust subspace recovery problem, a special case in which the (1 − α) n inliers in the optimal solution are promised to lie exactly on a k -dimensional linear subspace. However, robust subspace recovery is Small Set Expansion (SSE)-hard, and known algorithmic results for robust subspace recovery require strong assumptions on the input, e.g., any d outliers must be linearly independent. In this paper, we show how to extend dimension reduction techniques and bi-criteria approximations based on sampling and coresets to the problem of subspace approximation with outliers. To get around the SSE-hardness of robust subspace recovery, we assume that the squared distance error of the optimal k -dimensional subspace summed over the optimal (1 − α) n inliers is at least δ times its squared-error summed over all n points, for some 0 < δ ≤ 1 − α. Under this assumption, we give an efficient algorithm to find a weak coreset or a subset of poly (k / ϵ) log (1 / δ) log log (1 / δ) points whose span contains a k -dimensional subspace that gives a multiplicative (1 + ϵ) -approximation to the optimal solution. Our technique is based on the squared-length sampling algorithm suggested for low-rank approximation problems in the seminal work of Frieze, Kannan, and Vempala [12]. The running time of our algorithm is linear in n and d. Interestingly, our results hold even when the fraction of outliers α is large, as long as the obvious condition 0 < δ ≤ 1 − α is satisfied. We show similar results for subspace approximation with ℓ p error or more general M-estimator loss functions, and also give an additive approximation for the affine subspace approximation problem. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.