Search

In this work we introduce the Minimum Rural Postmen Cover Problem (MRPCP) and the Minimum Chinese Postmen Cover Problem (MCPCP). The MRPCP aims to cover a given subset R of edges of an undirected weighted graph G = (V , E) by a minimum size set of closed walks of bounded length λ. The MCPCP is a special case of the MRPCP with R = E. We give the first approximation algorithms for these two problems, which have constant approximation ratios of 5 and 4, respectively. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]

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]

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]

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]

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]

• 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]

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]

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]

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]

• 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]

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]

• 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]

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]

• 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]

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]

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]

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]

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]

• 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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

• 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]

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]

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]

• 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]

• 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]

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]

• 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]

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

• The 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]

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]

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]

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]