Search

When using traditional Euler deconvolution optimization strategies, it is difficult to distinguish between anomalies and their corresponding Euler tails (those solutions are often distributed outside the anomaly source, forming "tail"-shaped spurious solutions, i.e., misplaced Euler solutions, which must be removed or marked) with only the structural index. The nonparametric estimation method based on the normalized B-spline probability density (BSS) is used to separate the Euler solution clusters and mark different anomaly sources according to the similarity and density characteristics of the Euler solutions. For display purposes, the BSS needs to map the samples onto the estimation grid at the points where density will be estimated in order to obtain the probability density distribution. However, if the size of the samples or the estimation grid is too large, this process can lead to high levels of memory consumption and excessive computation times. To address this issue, a fast linear binning approximation algorithm is introduced in the BSS to speed up the computation process and save time. Subsequently, the sample data are quickly projected onto the estimation grid to facilitate the discrete convolution between the grid and the density function using a fast Fourier transform. A method involving multivariate B-spline probability density estimation based on the FFT (BSSFFT), in conjunction with fast linear binning appropriation, is proposed in this paper. The results of two random normal distributions show the correctness of the BSS and BSSFFT algorithms, which is verified via a comparison with the true probability density function (pdf) and Gaussian kernel smoothing estimation algorithms. Then, the Euler solutions of the two synthetic models are analyzed using the BSS and BSSFFT algorithms. The results are consistent with their theoretical values, which verify their correctness regarding Euler solutions. Finally, the BSSFFT is applied to Bishop 5X data, and the numerical results show that the comprehensive analysis of the 3D probability density distributions using the BSSFFT algorithm, derived from the Euler solution subset of  x 0 , y 0 , z 0 , can effectively separate and locate adjacent anomaly sources, demonstrating strong adaptability. [ABSTRACT FROM AUTHOR]

A dominating set of a graph is a subset of vertices such that every vertex not in the subset has at least one neighbor within the subset. The corresponding optimization problem is known to be NP-hard. It is proved to be beneficial to separate the solution process in two stages. First, one can apply a fast greedy algorithm to obtain an initial dominating set and then use an iterative procedure to purify (reduce) the size of this dominating set. In this work, we develop the purification stage and propose new purification algorithms. The purification procedures that we present here outperform, in practice, the earlier known purification procedure. We have tested our algorithms for over 1300 benchmark problem instances. Compared to the estimations due to known upper bounds, the obtained solutions are about seven times better. Remarkably, for the 500 benchmark instances for which the optimum is known, the optimal solutions are obtained for 46.33% of the tested instances, whereas the average error for the remaining instances is about 1.01. [ABSTRACT FROM AUTHOR]

This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modularity that enhances its effectiveness. We formulate community detection as an integer programming problem of an equivalent yet more compact counterpart model of the revised Max-Min Modularity maximization problem. Using a row generation technique alongside the heuristic approach, we then provide a hybrid procedure for near-optimally solving the model and discovering high-quality communities. Through a series of experiments, we demonstrate the success of our algorithm, showcasing its efficiency in detecting communities, particularly in extensive networks. [ABSTRACT FROM AUTHOR]

This paper is concerned with designing algorithms for and analyzing the computational complexity of the partial vertex cover problem in trees. Graphs (and trees) are frequently used to model risk management in various systems. In particular, Caskurlu et al. in [4] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Cover problem on bipartite graphs. In this paper, we focus on a special case of the partial vertex cover problem, when the input graph is a tree. We consider four possible versions of this setting, depending on whether or not, the vertices and edges are weighted. Two of these versions, where edges are assumed to be unweighted, are known to be polynomial-time solvable. However, the computational complexity of this problem with weighted edges, and possibly with weighted vertices, remained open. The main contribution of this paper is to resolve these questions by fully characterizing which variants of partial vertex cover remain NP-hard in trees, and which can be solved in polynomial time. In the paper, we propose two pseudo-polynomial DP-based algorithms for the most general case in which weights are present on both the edges and the vertices of the tree. One of these algorithms leads to a polynomial-time procedure, when weights are confined to the edges of the tree. The insights used in this algorithm are combined with additional scaling ideas to derive an FPTAS for the general case. A secondary contribution of this work is to propose a novel way of using centroid decompositions in trees, which could be useful in other settings as well. [ABSTRACT FROM AUTHOR]

In MAXSPACE, given a set of ads A , one wants to schedule a subset A ′ ⊆ A into K slots B 1 , ⋯ , B K of size L. Each ad A i ∈ A has a size s i and a frequency w i . A schedule is feasible if the total size of ads in any slot is at most L, and each ad A i ∈ A ′ appears in exactly w i slots and at most once per slot. The goal is to find a feasible schedule that maximizes the sum of the space occupied by all slots. We consider a generalization called MAXSPACE-R for which an ad A i also has a release date r i and may only appear in a slot B j if j ≥ r i . For this variant, we give a 1/9-approximation algorithm. Furthermore, we consider MAXSPACE-RDV for which an ad A i also has a deadline d i (and may only appear in a slot B j with r i ≤ j ≤ d i ), and a value v i that is the gain of each assigned copy of A i (which can be unrelated to s i ). We present a polynomial-time approximation scheme for this problem when K is bounded by a constant. This is the best factor one can expect since MAXSPACE is strongly NP-hard, even if K = 2 . [ABSTRACT FROM AUTHOR]

In this paper, we study a discrete momentum consensus-based optimization (Momentum-CBO) algorithm which corresponds to a second-order generalization of the discrete first-order CBO [S.-Y. Ha, S. Jin and D. Kim, Convergence of a first-order consensus-based global optimization algorithm, Math. Models Methods Appl. Sci. 30 (2020) 2417–2444]. The proposed algorithm can be understood as the modification of ADAM-CBO, replacing the normalization term by unity. For the proposed Momentum-CBO, we provide a sufficient framework which guarantees the convergence of algorithm toward a global minimum of the objective function. Moreover, we present several experimental results showing that Momentum-CBO has an improved success rate of finding the global minimum compared to vanilla-CBO and show the stability of Momentum-CBO under different initialization schemes. We also show that Momentum-CBO can be used as the alternative of ADAM-CBO which does not have a proper convergence analysis. Finally, we give an application of Momentum-CBO for Lyapunov function approximation using symbolic regression techniques. [ABSTRACT FROM AUTHOR]

Graph coloring is the assignment of one color to each vertex of a graph so that two adjacent vertices are not of the same color. The graph coloring problem (GCP) is a matter of combinatorial optimization, and the goal of GCP is determining the chromatic number (G). Since GCP is an NP-hard problem, then in this paper, we propose a new approximated algorithm for finding the coloring number (it is an approximation of chromatic number) by using a graph adjacency matrix to colorize or separate a graph. To prove the correctness of the proposed algorithm, we implement it in MATLAB software, and for analysis in terms of solution and execution time, we compare our algorithm with some of the best existing algorithms that are already implemented in MATLAB software, and we present the results in tables of various graphs. Several available algorithms used the largest degree selection strategy, while our proposed algorithm uses the graph adjacency matrix to select the vertex that has the smallest degree for coloring. We provide some examples to compare the performance of our algorithm to other available methods. We make use of the Dolan-Moré performance profiles to assess the performance of the numerical algorithms, and demonstrate the efficiency of our proposed approach in comparison with some existing methods. [ABSTRACT FROM AUTHOR]

Experimentation is prevalent in online marketplaces and social networks to assess the effectiveness of new market intervention. To mitigate the interference among users in an experiment, a common practice is to use a cluster-based experiment, where the designer partitions the market into loosely connected clusters and assigns all users in the same cluster to the same variant (treatment or control). Given the experiment, we assume an unbiased Horvitz–Thompson estimator is used to estimate the total market effect of the treatment. We consider the optimization problem of choosing (correlated) randomized assignments of clusters to treatment and control to minimize the worst-case variance of the estimator under a constraint that the marginal assignment probability is q∈(0,1) for all clusters. This problem can be formulated as a linear program where both the number of decision variables and constraints are exponential in the number of clusters—and hence is generally computationally intractable. We develop a family of practical experiments that we refer to as independent block randomization (IBR) experiments. Such an experiment partitions clusters into blocks so that each block contains clusters of similar size. It then treats a fraction q of the clusters in each block (chosen uniformly at random) and does so independently across blocks. The optimal cluster partition can be obtained in a tractable way using dynamic programming. We show that these policies are asymptotically optimal when the number of clusters grows large and no cluster size dominates the rest. In the special case where cluster sizes take values in a finite set and the number of clusters of each size is a fixed proportion of the total number of clusters, the loss is only a constant that is independent of the number of clusters. Beyond the asymptotic regime, we show that the IBR experiment has a good approximation for any problem instance when q is not very tiny. We also examine the performance of the IBR experiments on data-driven numerical examples, including examples based on Airbnb and Facebook data. This paper was accepted by Itai Ashlagi, revenue management and market analytics. Funding: O. Candogan acknowledges NSF [Award 2216912] for "Institute for Data, Econometrics, Algorithms and Learning." Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2021.02741. [ABSTRACT FROM AUTHOR]

Vegetable oils, which are considered potential lubricants, are composed of different types and proportions of fatty acids. Because of their diverse types and varying compositions, they exhibit different lubrication performances. The genetic function approximation algorithm was used to model the quantitative structure–property relationship between fatty acid structure and the wear scar diameter and friction coefficients measured by four-ball friction and wear tests. Based on the models with adjusted R2 greater than 0.9 and fatty acid compositions of vegetable oils, the wear scar diameter and friction coefficients of Xanthoceras sorbifolia bunge oil and Soybean oil as validation oil samples were predicted. The difference between the predicted and experimental values was small, indicating that the models could accurately predict the lubrication performances of vegetable oils. The lubrication performances of 14 kinds of vegetable oils were predicted by GFA-QSPR models, and the primary factors influencing their lubrication properties were studied by cluster analysis. The results show that the content of C18:1 has a positive effect on the lubrication performances of vegetable oils, while the content of C18:3 has a negative effect, and the length of the carbon chain of fatty acids significantly affects their lubrication properties. [ABSTRACT FROM AUTHOR]

We study two scheduling problems in a proportionate flow shop environment, where job processing times are machine independent. In contrast to classical proportionate flow shop models, we assume (in both problems) that processing times are step-deteriorating. Accordingly, each job J j has a normal processing time, a j , if it starts to be processed in the shop no later than its deteriorating date, δ j . Otherwise, the job's processing time increases by b j (the job's deterioration penalty). Our aim is to find a job schedule that minimizes either the makespan or the total load. These two problems are known to be N P -hard for the special case of a single machine, even when all jobs have the same deteriorating date. In this paper, we derive several positive results in relation to the two problems. We first show that the two problems can be represented in a unified way. We then prove that the unified problem is only ordinary N P -hard by providing a pseudo-polynomial time algorithm for its solution. We also show that the pseudo-polynomial time algorithm can be converted into a fully polynomial time approximation scheme (FPTAS). Finally, we analyze the parameterized complexity of the problem with respect to the number of different deteriorating dates in the instance, v δ . We show that although the problem is N P -hard when v δ = 1 , it is fixed parameterized tractable (FPT) for the combined parameters (i) (ν δ , ν a) and (ii) (ν δ , ν b) , where ν a is the number of different normal processing times in the instance, and ν b is the number of different deterioration penalties in the instance. [ABSTRACT FROM AUTHOR]

We improve the approximation ratio for Maximum Weight Series-Parallel Subgraph from 1 / 2 to 1 / 2 + 1 / 60. [ABSTRACT FROM AUTHOR]

In the network flow interdiction problem (NFI), an interdictor aims to remove arcs of total cost at most a given budget B from a network with given arc costs and capacities such that the value of a maximum flow from a source s to a sink t is minimized. We present a polynomial-time (B + 1) -approximation algorithm for NFI with unit arc costs, which is the first approximation algorithm for any variant of network flow interdiction whose approximation ratio only depends on the budget available to the interdictor, but not on the size of the network. [ABSTRACT FROM AUTHOR]

The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximation algorithms with guarantees below 2 for both TAP and CAP, culminating in the currently best approximation factor for both problems of 1.393 through quite sophisticated techniques. We present a new and arguably simple matching-based method for the well-known special case of leaf-to-leaf instances. Combining our work with prior techniques, we readily obtain a (4 / 3 + ε) -approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a 4 / 3 -guarantee was only known for Leaf-to-Leaf TAP instances on trees of height 2. Moreover, when combining our technique with a recently introduced stack analysis approach, which is part of the above-mentioned 1.393-approximation, we can further improve the approximation factor to 1.29, obtaining for the first time a factor below 4 3 for a nontrivial class of TAP/CAP instances. [ABSTRACT FROM AUTHOR]

A λ $\lambda $‐backbone coloring of a graph G $G$ with its subgraph (also called a backbone) H $H$ is a function c:V(G)→{1,...,k} $c:V(G)\to \{1,\ldots ,k\}$ ensuring that c $c$ is a proper coloring of G $G$ and for each {u,v}∈E(H) $\{u,v\}\in E(H)$ it holds that |c(u)−c(v)|≥λ $|c(u)-c(v)|\ge \lambda $. In this paper we propose a way to color cliques with tree and forest backbones in linear time that the largest color does not exceed max{n,2λ}+Δ(H)2⌈logn⌉ $\max \{n,2\lambda \}+{\rm{\Delta }}{(H)}^{2}\lceil \mathrm{log}n\rceil $. This result improves on the previously existing approximation algorithms as it is (Δ(H)2⌈logn⌉) $({\rm{\Delta }}{(H)}^{2}\lceil \mathrm{log}n\rceil)$‐absolutely approximate, that is, with an additive error over the optimum. We also present an infinite family of trees T $T$ with Δ(T)=3 ${\rm{\Delta }}(T)=3$ for which the coloring of cliques with backbones T $T$ requires at least max{n,2λ}+Ω(logn) $\max \{n,2\lambda \}+{\rm{\Omega }}(\mathrm{log}n)$ colors for λ $\lambda $ close to n2 $\frac{n}{2}$. The construction draws on the theory of Fibonacci numbers, particularly on Zeckendorf representations. [ABSTRACT FROM AUTHOR]

We study the interplay between the data distribution and Q-learning-based algorithms with function approximation. We provide a unified theoretical and empirical analysis as to how different properties of the data distribution influence the performance of Q-learning-based algorithms. We connect different lines of research, as well as validate and extend previous results, being primarily focused on offline settings. First, we analyze the impact of the data distribution by using optimization as a tool to better understand which data distributions yield low concentrability coefficients. We motivate high-entropy distributions from a game-theoretical point of view and propose an algorithm to find the optimal data distribution from the point of view of concentrability. Second, from an empirical perspective, we introduce a novel four-state MDP specifically tailored to highlight the impact of the data distribution in the performance of Q-learning-based algorithms with function approximation. Finally, we experimentally assess the impact of the data distribution properties on the performance of two offline Q-learning-based algorithms under different environments. Our results attest to the importance of different properties of the data distribution such as entropy, coverage, and data quality (closeness to optimal policy). [ABSTRACT FROM AUTHOR]

This paper studies a two-agent scheduling problem on mixed batch machines in parallel. A mixed batch machine can process several jobs simultaneously as a batch, as long as the number of jobs in the batch does not exceed the machine capacity. The processing time of a mixed batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective is to minimise the weighted sum of two agents' makespans. We present four approximation algorithms based on two strategies: the machine-centric strategy and the agent-centric strategy. For each strategy, a full batch longest processing time (FBLPT) rule and a longest processing time greedy (LPTG) rule are used. We conduct theoretical analyses based on the worst-case performance ratio to provide the provable guarantees on the performances of the algorithms, and simulation analyses based on randomly generated instances to evaluate the average performances of the algorithms. Furthermore, we verify the consistency between the theoretical and simulation results. The algorithms using agent-centric strategy perform better than ones using machine-centric strategy. Finally, we provide managerial insights for the problem by analysing the technological parameters of batches, importance of agents, and demand seasonality. [ABSTRACT FROM AUTHOR]

Transportation networks frequently employ hub-and-spoke network architectures to route flows between many origin and destination pairs. Hub facilities work as switching points for flows in large networks. In this study, we focus on a problem, called the single allocation hub-and-spoke network design problem. In the problem, the goal is to allocate each non-hub node to exactly one of the given hub nodes so as to minimize the total transportation cost. The problem is essentially equivalent to another combinatorial optimization problem, called the metric labeling problem. The metric labeling problem was first introduced by Kleinberg and Tardos in 2002, motivated by application to segmentation problems in computer vision and related areas. In this study, we deal with a case where the set of hubs forms a star, which is encountered especially in telecommunication networks. We propose a polynomial-time randomized approximation algorithm for the problem, whose approximation ratio is less than 5.281. Our algorithms solve a linear relaxation problem and apply dependent rounding procedures. [ABSTRACT FROM AUTHOR]

We call a (not necessarily properly) edge-colored graph edge-color-avoiding connected if after the removal of edges of any single color, the graph remains connected. For vertex-colored graphs, similar definitions of color-avoiding connectivity can be given. In this article, we investigate the problem of determining the maximum number of edges that can be removed from either an edge- or a vertex-colored, color-avoiding connected graph so that it remains color-avoiding connected. First, we prove that this problem is NP-hard, and then, we give a polynomial-time approximation algorithm for it. To analyze the approximation factor of this algorithm, we determine the minimum number of edges of color-avoiding connected graphs on a given number of vertices and with a given number of colors. Furthermore, we also consider a generalization of edge-color-avoiding connectivity to matroids. [ABSTRACT FROM AUTHOR]

The advancement of autonomous capabilities in maritime navigation has gained significant attention, with a trajectory moving from decision support systems to full autonomy. This push towards autonomy has led to extensive research focusing on collision avoidance, a critical aspect of safe navigation. Among the various possible approaches, dynamic programming is a promising tool for optimizing collision avoidance maneuvers. This paper presents a DP formulation for the collision avoidance of autonomous vessels. We set up the problem framework, formulate it as a multi-stage decision process, define cost functions and constraints focusing on the actual requirements a marine maneuver must comply with, and propose a solution algorithm leveraging parallel computing. Additionally, we present a greedy approximation to reduce algorithm complexity. We put the proposed algorithms to the test in realistic navigation scenarios and also develop an extensive test on a large set of randomly generated scenarios, comparing them with the RRT* algorithm using performance metrics proposed in the literature. The results show the potential benefits of an autonomous navigation or decision support framework. [ABSTRACT FROM AUTHOR]

The Susceptible–Infected–Susceptible (SIS) model in complex networks is one of the critical models employed in the modeling of virus spread. The study of the heterogeneous SIS model with a non-homogeneous nodal infection rate in finite-size networks has attracted little attention. Investigating the statistical properties of heterogeneous SIS epidemic dynamics in finite networks is thus intriguing. In this paper, we focus on the measure of variability in the number of infected nodes for the heterogeneous SIS epidemic dynamics in finite-size bipartite graphs and star graphs. Specifically, we investigate the metastable-state variance of the number of infected nodes for the SIS epidemic process in finite-size bipartite graphs and star graphs with heterogeneous nodal infection rates. We employ an extended individual-based mean-field approximation to analyze the heterogeneous SIS epidemic process in finite-size bipartite networks and star graphs. We derive the approximation solutions of the variance of the infected number. We verify the proposed theory by simulations. The proposed theory has the potential to help us better understand the fluctuations of SIS models like epidemic dynamics with a non-homogeneous infection rate. [ABSTRACT FROM AUTHOR]

We consider the following node-capacitated network design problem. The input is an undirected graph, a set of demands, uniform node capacity, and arbitrary node costs. The goal is to find a minimum node-cost subgraph that supports all demands concurrently subject to the node capacities. We consider both single- and multicommodity demands and provide the first polylogarithmic approximation guarantees. For single-commodity demands (i.e., all request pairs have the same sink node), we obtain an O(log²n) approximation to the cost with an O(log³n) factor violation in node capacities. For multicommodity demands, we obtain an O(log4n) approximation to the cost with an O(log10n) factor violation in node capacities. We use a variety of techniques, including single-sink confluent flows, low-load set cover, random sampling, and cut-sparsification. We also develop new techniques for clustering multicommodity demands into (nearly) node-disjoint clusters, which may be of independent interest. Moreover, this network design problem has applications to energy-efficient virtual circuit routing. In this setting, there is a network of routers that are speed scalable and that may be shut down when idle. We assume the standard model for power: the power consumed by a router with load (speed) s is \sigma + s\alpha, where \sigma is the static power and the exponent \alpha > 1. We obtain the first polylogarithmic approximation algorithms for this problem when speed-scaling occurs on nodes of a network. [ABSTRACT FROM AUTHOR]

This paper develops novel fast numerical solvers for subdiffusion problems with spatial interfaces. These problems are modeled by partial differential equations that contain both fractional order and conventional first order time derivatives. The former is non-local and approximated by L1 and L2 discretizations along with fast evaluation algorithms based on approximation by sums of exponentials. This results in an effective treatment of the "long-tail" kernel of subdiffusion. The latter is local and hence conventional implicit Euler or Crank-Nicolson discretizations can be used. Finite volumes are utilized for spatial discretization based on consideration of local mass conservation. Interface conditions for mass and fractional uxes are incorporated into these fast solvers. Computational complexity and implementation procedures are briey discussed. Numerical experiments demonstrate accuracy and efficiency of these new fast solvers. [ABSTRACT FROM AUTHOR]

This work studies solutions to determine the macro-elastic moduli of three-phase composite materials with imperfect interfaces in 2D. Which is based on the coated circular assemblage model of Hashin-Strikman and the polarization approximation method (PA) to develop the formulae for elastic moduli of circle inclusions with spring-layer and surface-stress imperfect interfaces. From that, explicit algebraic expressions were obtained to estimate the elastic moduli of three-phase composites with imperfect interfaces, in which two phases are different with circular inclusions distributed randomly in the matrix. Besides, the FFT algorithm and the differential approximation (DA) are also developed to determine the elastic moduli of the three-phase composite with imperfect interfaces. The results of the FFT numerical methods will be compared with the DA and PA results with different material cases to show the effectiveness of the applied methods. [ABSTRACT FROM AUTHOR]

Many modern day cloud hosted applications such as virtual reality, real time games require low latency data access and computation to improve response time. So it is essential to bring the computation and data storage edge servers closer to the user's geographical location to improve response times and save bandwidth. In particulars, in online gaming and on demand video services, the required application data present at cloud servers need to be placed on the edge servers to provide low latency app-functionalities. The transfer of huge amount of data from cloud server to edge server incurs high cost and time penalties. Thus, we need an efficient way to solve edge data distribution (EDD) problem which distribute the application data to the edge servers that minimizes transfer cost. In this work, we provide a refined formulation of an optimal approach to solve the EDD problem using integer linear programming (ILP) technique. Due to the time complexity limitation of the ILP approach, we propose an O(k) approximation algorithm based on network Steiner tree estimation (EDD-NSTE) for estimating solutions to dense large-scale EDD problem. The proposed approach is analyzed to be 11/6 approximation which is better than the state-of-the-art 2 approximation EDD-A approach. The experimental evaluation through simulation using real world EUA data set demonstrate that the EDD-NSTE outperform state-of-the-art approach and other representative approaches. [ABSTRACT FROM AUTHOR]

This paper considers the problem of finding maximum volume (axis-aligned) inscribed boxes in a compact convex set, defined by a finite number of convex inequalities, and presents optimization and geometric approaches for solving them. Several optimization models are developed that can be easily generalized to find other inscribed geometric shapes such as triangles, rhombi, and squares. To find the largest volume axis-aligned inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed. For two-dimensional space, a parametrized optimization approach is developed to find the largest area (axis-aligned) inscribed rectangles in convex sets. The optimization approach provides a uniform framework for solving a wide variety of relevant problems. Finally, two computational geometric (1−ε) –approximation algorithms with sublinear running times are presented that improve the previous results. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: The author is grateful for the support of Northeastern University for this research. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0239) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0239). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In offline scheduling models, jobs are given with their exact processing times. In their online counterparts, jobs arrive in sequence together with their processing times and the scheduler makes irrevocable decisions on how to execute each of them upon its arrival. We consider a semi-online variant which has equally rich application background, called scheduling with testing, where the exact processing time of a job is revealed only after a required testing operation is finished, or otherwise the job has to be executed for a given possibly over-estimated length of time. For multiprocessor scheduling with testing to minimize the total job completion time, we present several first approximation algorithms with constant competitive ratios for various settings, including a 2 φ -competitive algorithm for the non-preemptive general testing case and a (0.0382 + 2.7925 (1 - 1 2 m)) -competitive randomized algorithm, when the number of machines m ≥ 37 or otherwise 2.7925-competitive, where φ = (1 + 5) / 2 < 1.6181 is the golden ratio and m is the number of machines, a (3.5 - 3 2 m) -competitive algorithm allowing job preemption when m ≥ 3 or otherwise 3-competitive, and a (φ + φ + 1 2 (1 - 1 m)) -competitive algorithm for the non-preemptive uniform testing case when m ≥ 5 or otherwise (φ + 1) -competitive. Our results improve three previous best approximation algorithms for the single machine scheduling with testing problems, respectively. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of finding a regression in a version control system (VCS), such as git. The set of versions is modelled by a directed acyclic graph (DAG) where vertices represent versions of the software, and arcs are the changes between different versions. We assume that somewhere in the DAG, a bug was introduced, which persists in all of its subsequent versions. It is possible to query a vertex to check whether the corresponding version carries the bug. Given a DAG and a bugged vertex, the Regression Search Problem consists in finding the first vertex containing the bug in a minimum number of queries in the worst-case scenario. This problem is known to be NP-complete. We study the algorithm used in git to address this problem, known as git bisect. We prove that in a general setting, git bisect can use an exponentially larger number of queries than an optimal algorithm. We also consider the restriction where all vertices have indegree at most 2 (i.e. where merges are made between at most two branches at a time in the VCS), and prove that in this case, git bisect is a 1 log 2 (3 / 2) -approximation algorithm, and that this bound is tight. We also provide a better approximation algorithm for this case. Finally, we give an alternative proof of the NP-completeness of the Regression Search Problem, via a variation with bounded indegree. [ABSTRACT FROM AUTHOR]

In this paper we study the classical problem of throughput maximization. In this problem we have a collection J of n jobs, each having a release time r j , deadline d j , and processing time p j . They have to be scheduled non-preemptively on m identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their [ r j , d j ] window. This problem has been studied extensively (even for the case of m = 1 ). Several special cases of the problem remain open. Bar-Noy et al. (Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1–4, 1999, Atlanta, Georgia, USA, pp. 622–631. ACM, 1999, https://doi.org/10.1145/301250.301420) presented an algorithm with ratio 1 - 1 / (1 + 1 / m) m for m machines, which approaches 1 - 1 / e as m increases. For m = 1 , Chuzhoy et al. (42nd Annual Symposium on Foundations of Computer Science (FOCS) 2001, 14–17 October 2001, Las Vegas, Nevada, USA, pp. 348–356. IEEE Computer Society, 2001) presented an algorithm with approximation with ratio 1 - 1 e - ε (for any ε > 0 ). Recently Im et al. (SIAM J Discrete Math 34(3):1649–1669, 2020) presented an algorithm with ratio 1 - 1 / e + ε 0 for some absolute constant ε 0 > 0 for any fixed m. They also presented an algorithm with ratio 1 - O (log m / m) - ε for general m which approaches 1 as m grows. The approximability of the problem for m = O (1) remains a major open question. Even for the case of m = 1 and c = O (1) distinct processing times the problem is open (Sgall in: Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceedings, pp 2–11, 2012). In this paper we study the case of m = O (1) and show that if there are c distinct processing times, i.e. p j 's come from a set of size c, then there is a randomized (1 - ε) -approximation that runs in time O (n m c 7 ε - 6 log T) , where T is the largest deadline. Therefore, for constant m and constant c this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning. [ABSTRACT FROM AUTHOR]

Stochastic optimization has experienced significant growth in recent decades, with the increasing prevalence of variance reduction techniques in stochastic optimization algorithms to enhance computational efficiency. In this paper, we introduce two projection-free stochastic approximation algorithms for maximizing diminishing return (DR) submodular functions over convex constraints, building upon the Stochastic Path Integrated Differential EstimatoR (SPIDER) and its variants. Firstly, we present a SPIDER Continuous Greedy (SPIDER-CG) algorithm for the monotone case that guarantees a (1 - e - 1) OPT - ε approximation after O (ε - 1) iterations and O (ε - 2) stochastic gradient computations under the mean-squared smoothness assumption. For the non-monotone case, we develop a SPIDER Frank–Wolfe (SPIDER-FW) algorithm that guarantees a 1 4 (1 - min x ∈ C ‖ x ‖ ∞) OPT - ε approximation with O (ε - 1) iterations and O (ε - 2) stochastic gradient estimates. To address the practical challenge associated with a large number of samples per iteration, we introduce a modified gradient estimator based on SPIDER, leading to a Hybrid SPIDER-FW (Hybrid SPIDER-CG) algorithm, which achieves the same approximation guarantee as SPIDER-FW (SPIDER-CG) algorithm with only O (1) samples per iteration. Numerical experiments on both simulated and real data demonstrate the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

The Power of Traffic Tolls The paper "In Congestion Games, Taxes Achieve Optimal Approximation" by Paccagnan and Gairing investigates the power and limitations of taxes as interventions in congestion games. Perhaps surprisingly, they find that efficiently computed taxes can achieve the same performance as the best polynomial time algorithm, even when the algorithm has full control over the agents' actions. The authors establish three main results to support this claim. First, they prove that minimizing congestion is NP-hard to approximate within a given factor based on the latency functions. Second, they demonstrate how convex optimization tools can be used to design optimal taxes. Third, they provide a polynomial time algorithm with an approximation factor matching the hardness barrier. The upshot of their contribution can be summarized as follows: Judiciously designed taxes achieve optimal approximation, and no other tractable intervention can improve upon this result. In this work, we address the problem of minimizing social cost in atomic congestion games. For this problem, we present lower bounds on the approximation ratio achievable in polynomial time and demonstrate that efficiently computable taxes result in polynomial time algorithms matching such bounds. Perhaps surprisingly, these results show that indirect interventions, in the form of efficiently computed taxation mechanisms, yield the same performance achievable by the best polynomial time algorithm, even when the latter has full control over the agents' actions. It follows that no other tractable approach geared at incentivizing desirable system behavior can improve upon this result, regardless of whether it is based on taxations, coordination mechanisms, information provision, or any other principle. In short: Judiciously chosen taxes achieve optimal approximation. Three technical contributions underpin this conclusion. First, we show that computing the minimum social cost is NP -hard to approximate within a given factor depending solely on the admissible cost functions. Second, we design a polynomially computable taxation mechanism whose efficiency (price of anarchy) matches this hardness factor, and thus is optimal among all tractable mechanisms. As these results extend to coarse correlated equilibria, any no-regret algorithm inherits the same performances, allowing us to devise polynomial time algorithms with optimal approximation. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2021.0526. [ABSTRACT FROM AUTHOR]

We study a shipment consolidation problem commonly faced by companies that outsource logistics operations and operate in a commit-to-delivery mode. It involves delivering a given set of orders to their destinations by their committed due times using multiple shipping methods at the minimum total shipping and inventory cost. The shipping cost is generally nonlinear in shipping quantity and can be represented by a subadditive piecewise linear function. We investigate two shipping scenarios, one involving long-haul shipping only and the other involving joint long-haul and short-haul shipping. We develop analytical results and solution algorithms for the shipment consolidation problem under each shipping scenario. The problem under the first shipping scenario is shown to be strongly NP -hard. We find that a simple policy, called the First-Due-First-Delivered (FDFD) policy, which assigns orders with earlier delivery due times to shipping methods with earlier destination arrival times, is very effective. This policy enables us to develop a polynomial time algorithm, which not only solves the problem under the concave shipping cost structure optimally but also achieves a performance guarantee of 2 for the problem under the general subadditive shipping cost structure. For the problem under the second shipping scenario, we extend the FDFD policy for long-haul shipping and derive another policy, called the No-Wait policy, for short-haul shipping. We use these policies to develop a polynomial time algorithm and analyze its performance guarantee. Our computational experiments show that the algorithm significantly outperforms a commercial optimization solver, and its performance is robust across different parameter settings that reflect various practical situations. This paper was accepted by Jeannette Song, operations management. Supplemental Material: The data and e-companion are available at https://doi.org/10.1287/mnsc.2023.4835. [ABSTRACT FROM AUTHOR]

In the past decades, explosive numbers of Internet of Things (IoT) devices (objects) have been connected to the Internet, which enable users to access, control, and monitor their surrounding phenomenons at anytime and anywhere. To provide seamless interactions between the cyber world and the real world, Digital twins (DTs) of objects (IoT devices) are key enablers for real time monitoring, behaviour simulations, and predictive decisions on objects. Compared to centralized cloud computing, mobile edge computing (MEC) has been envisioning as a promising paradigm for low latency IoT applications. Accelerating the usage of DTs in MEC networks will bring unprecedented benefits to diverse services, through the co-evolution between physical objects and their virtual DTs, and DT-assisted service provisioning has attracted increasing attention recently. In this article, we consider novel DT placement and migration problems in an MEC network with the mobility assumption of objects and users, by jointly considering the freshness of DT data and the service cost of users requesting for DT data. To this end, we first propose an algorithm for the DT placement problem with the aim to minimize the sum of the DT update cost of objects and the total service cost of users requesting for DT data, through efficient DT placements and resource allocation to process user requests. We then devise an approximation algorithm with a provable approximation ratio for a special case of the DT placement problem when each user requests the DT data of only one object. Meanwhile, considering the mobility of users and objects, we devise an online, two-layer scheduling algorithm for DT migrations to further reduce the total service cost of users within a given finite time horizon. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results show that the proposed algorithms are promising. [ABSTRACT FROM AUTHOR]

The use of drones for collecting information and detecting bugs in orchards covered by nets is a challenging problem. The nets help in reducing pest damage, but they also constrain the drone's flight path, making it longer and more complex. To address this issue, we model the orchard as an aisle-graph, a regular data structure that represents consecutive aisles where trees are arranged in straight lines. The drone flies close to the trees and takes pictures at specific positions for monitoring the presence of bugs, but its energy is limited, so it can only visit a subset of positions. To tackle this challenge, we introduce the Single-drone Orienteering Aisle-graph Problem (SOAP), a variant of the orienteering problem, where likely infested locations are prioritized by assigning them a larger profit. Additionally, the drone's movements have a cost in terms of energy, and the objective is to plan a drone's route in the most profitable locations under a given drone's battery. We show that SOAP can be optimally solved in polynomial time, but for larger orchards/instances, we propose faster approximation and heuristic algorithms. Finally, we evaluate the algorithms on synthetic and real datasets to demonstrate their effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

Problem definition: Content promotion policies are crucial for online content platforms to improve content consumption and user engagement. However, traditional promotion policies generally neglect the diffusion effect within a crowd of users. In this paper, we study the candidate generation and promotion optimization (CGPO) problem for an online content platform, emphasizing the incorporation of the diffusion effect. Methodology/results: We propose a diffusion model that incorporates platform promotion decisions to characterize the adoption process of online content. Based on this diffusion model, we formulate the CGPO problem as a mixed-integer program with nonconvex and nonlinear constraints, which is proved to be NP-hard. Additionally, we investigate methods for estimating the diffusion model parameters using available online platform data and introduce novel double ordinary least squares (D-OLS) estimators. We prove the submodularity of the objective function for the CGPO problem, which enables us to find an efficient (1−1/e) -approximation greedy solution. Furthermore, we demonstrate that the D-OLS estimators are consistent and have smaller asymptotic variances than traditional ordinary least squares estimators. By utilizing real data from a large-scale video-sharing platform, we show that our diffusion model effectively characterizes the adoption process of online content. Compared with the policy implemented on the platform, our proposed promotion policy increases total adoptions by 49.90%. Managerial implications: Our research highlights the essential role of diffusion in online content and provides actionable insights for online content platforms to optimize their content promotion policies by leveraging our diffusion model. Funding: R. Zhang is grateful for the financial support from the Hong Kong Research Grants Council General Research Fund [Grants 14502722 and 14504123] and the National Natural Science Foundation of China [Grant 72293560/72293565]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0172. [ABSTRACT FROM AUTHOR]

Problem definition: We investigate the effects of waiting time, mainly due to production in a make-to-batch-order (MTBO) system, on consumer choice behavior, pricing, assortment, and model estimation. In an MTBO system, the seller/manufacturer first collects orders placed within a certain period of time into a batch and then starts the production process. After the production of all orders in a batch are complete, the products are then shipped and delivered to individual consumers. Because of batch production and shipping, the disutility of the waiting time exhibits negative externality. Methodology/results: We adopt the widely used multinomial logit (MNL) model as a starting point and incorporate the anticipated wait into consumers' decision making. The derived model, referred to as the MNL with wait model, is a solution of the rational expectation equilibrium and is capable of capturing the effects of negative externality induced by anticipated wait that may change the substitution patterns dramatically. We characterize the multiproduct price optimization problem under the MNL with wait model by establishing a one-to-one mapping between the price vector and the choice probability vector. We find that firms tend to charge higher prices for time-consuming items and charge lower prices for time-saving items compared with the optimal prices under the standard MNL model. In addition to price competition, we also study the Cournot-type competition, in which the decision is the choice probability for each firm and establish the existence of a Nash equilibrium. For assortment optimization, we identify mild conditions under which the optimality of revenue-ordered assortments still holds. However, the assortment problem under the MNL with wait model is generally NP-hard, so we develop approximation algorithms with performance guarantees and provide an easy-to-compute tight upper bound. Moreover, we develop an efficient maximum likelihood-based algorithm for model calibration and further conduct numerical studies to showcase the importance of incorporating disutility due to wait in estimation, pricing, and assortment planning problems. Managerial implications: The MNL with wait model can increase prediction accuracy for consumers' choice behavior especially when they are aware of the potential wait. Failure to take into account the effects of anticipated wait in firms' decision making may lead to substantial losses. Funding: The research of C. Ke is supported in part by the National Natural Science Foundation of China [Grant 72101113]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2020.0346. [ABSTRACT FROM AUTHOR]

We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not guaranteed. We identify a natural property of markets (termed money clearing) that implies existence. We show that the set of equilibria is not always convex, answering a question posed in the literature. We design an FPTAS to compute an approximate equilibrium and prove that the problem of computing an exact equilibrium lies in the complexity class continuous local search (CLS ; i.e., the intersection of polynomial local search (PLS) and polynomial parity arguments on directed graphs (PPAD)). For a constant number of buyers or goods, we give a polynomial-time algorithm to compute an exact equilibrium. We show how (approximate) equilibria can be rounded and provide the first constant-factor approximation algorithm (with a factor of 2.404) for maximizing Nash social welfare when agents have capped linear (also known as budget-additive) valuations. Finally, we significantly improve the approximation hardness for additive valuations to 8/7>1.069. Funding: J. Garg was supported by the National Science Foundation [Grant CCF-1942321 (CAREER)]. M. Hoefer was supported by Deutsche Forschungsgemeinschaft [Grants Ho 3831/5-1, Ho 3831/6-1, and Ho 3831/7-1]. [ABSTRACT FROM AUTHOR]

Router nodes placement (RNP) is an important issue in the design and implementation of wireless mesh networks (WMN). This is known as an P-hard problem, which cannot be solved using conventional algorithms. Consequently, approximate optimization strategies are commonly used to solve this problem. With heavy node density and wide-area WMNs, solving the RNP problem using approximation algorithms often faces many difficulties, therefore, a more effective solution is necessary. This motivated us to conduct this work. We propose a new method for solving the RNP problem using reinforcement learning (RL). The RNP problem is modeled as an RL model with environment, agent, action, and reward are equivalent to the network system, routers, coordinate adjustment, and connectivity of the RNP problem, respectively. To the best of our knowledge, this is the first study that applies RL to solve the RNP problem. The experimental results showed that the proposed method increased the network connectivity by up to 22.73% compared to the most recent methods. [ABSTRACT FROM AUTHOR]

In this work we investigate the min-max-min robust optimization problem and the k-adaptability robust optimization problem for binary problems with uncertain costs. The idea of the first approach is to calculate a set of k feasible solutions which are worst-case optimal if in each possible scenario the best of the k solutions is implemented. It is known that the min-max-min robust problem can be solved efficiently if k is at least the dimension of the problem, while it is theoretically and computationally hard if k is small. However, nothing is known about the intermediate case, i.e., k lies between one and the dimension of the problem. We approach this open question and present an approximation algorithm which achieves good problem-specific approximation guarantees for the cases where k is close to or a fraction of the dimension. The derived bounds can be used to show that the min-max-min robust problem is solvable in oracle-polynomial time under certain conditions even if k is smaller than the dimension. We extend the previous results to the robust k-adaptability problem. As a consequence we can provide bounds on the number of necessary second-stage policies to approximate the exact two-stage robust problem. We derive an approximation algorithm for the k-adaptability problem which has similar guarantees as for the min-max-min problem. Finally, we test both algorithms on knapsack and shortest path problems. The experiments show that both algorithms calculate solutions with relatively small optimality gap in seconds. [ABSTRACT FROM AUTHOR]

The projected gradient method for matrix completion is generalized towards the higher-dimensional case of low-rank Tucker tensors. It is shown that an operation order rearrangement in the common projected gradient approach provides a complexity improvement. An even better algorithm complexity can be obtained by replacing the completion operator by a general operator that satisfies restricted isometry property; however, such a replacement transforms the completion algorithm into an approximation algorithm. [ABSTRACT FROM AUTHOR]

Modeling longitudinal and survival data jointly offers many advantages such as addressing measurement error and missing data in the longitudinal processes, understanding and quantifying the association between the longitudinal markers and the survival events, and predicting the risk of events based on the longitudinal markers. A joint model involves multiple submodels (one for each longitudinal/survival outcome) usually linked together through correlated or shared random effects. Their estimation is computationally expensive (particularly due to a multidimensional integration of the likelihood over the random effects distribution) so that inference methods become rapidly intractable, and restricts applications of joint models to a small number of longitudinal markers and/or random effects. We introduce a Bayesian approximation based on the integrated nested Laplace approximation algorithm implemented in the R package R-INLA to alleviate the computational burden and allow the estimation of multivariate joint models with fewer restrictions. Our simulation studies show that R-INLA substantially reduces the computation time and the variability of the parameter estimates compared with alternative estimation strategies. We further apply the methodology to analyze five longitudinal markers (3 continuous, 1 count, 1 binary, and 16 random effects) and competing risks of death and transplantation in a clinical trial on primary biliary cholangitis. R-INLA provides a fast and reliable inference technique for applying joint models to the complex multivariate data encountered in health research. [ABSTRACT FROM AUTHOR]

We investigate the seemingly untouched yet the most general parallel identical k-stage flow-shops scheduling, in which we are given an arbitrary number of indistinguishable k-stage flow-shops and a set of jobs each to be processed on one of the flow-shops, and the goal is to schedule these jobs to the flow-shops so as to minimize the makespan. Here the number k of stages is a fixed constant, but the number of flow-shops is part of the input. This scheduling problem is strongly NP-hard. To the best of our knowledge all previously presented approximation algorithms are for the special case where k = 2 , including a 17/6-approximation in 2017, a (2 + ϵ) -approximation in 2018, and the most recent polynomial-time approximation scheme in 2020; they all take advantage of the number of stages being two. We deal with an arbitrary constant k ≥ 3 , where the k-stage flow-shop scheduling is already strongly NP-hard. To define a configuration that summarizes the key information about the job assignments in a feasible schedule, we present novel concepts of big job type, big job assignment pair type, and flow-shop type. We show that the total number of distinct configurations is a polynomial in the input number of flow-shops. We then present how to compute a schedule for each configuration that assigns all the big jobs, followed by how to allocate all the small jobs into the schedule at a cost only a fraction of the makespan. These together lead to a polynomial-time approximation scheme for the problem. [ABSTRACT FROM AUTHOR]

In 2015, Haviv introduced the Remote set problem (RSP) and studied the complexity of the covering radius problem (CRP), which is a classical problem in lattices. The RSP aims to identify a set containing a point that is sufficiently distant from a given lattice L . It introduced a new method for analyzing the complexity of CRP. An open question in RSP is whether we can obtain the approximation factor γ = 1 / 2 . This paper investigates this question and proposes a probabilistic polynomial-time algorithm for RSP with an approximation factor of 1 / 2 - 1 / (c λ n (p)) , where c ∈ Z + and λ n (p) is the n-th successive minima in lattice under l p -norm. For a given lattice L with rank n and positive integer d, our algorithm outputs a set S of size d in polynomial time. This set S includes a point at least (1 2 - 1 c λ n (p) ) ρ (p) (L) from lattice L with a probability greater than 1 - 1 / 2 d . Here, c is a positive integer and ρ (p) (L) denotes the covering radius of L in l p -norm( 1 ≤ p ≤ ∞ ). Based on this, we obtain that GAPCRP 2 + 1 / 2 O (n) belongs to the complexity class coRP, and we provide new reductions from GAPCRP to GAPCVP. [ABSTRACT FROM AUTHOR]

In this work, we introduce a multi-vehicle (or multi-postman) extension of the classical Mixed Rural Postman Problem, which we call the Min–Max Mixed Rural Postmen Cover Problem (MRPCP). The MRPCP is defined on a mixed graph G = (V , E , A) , where V is the vertex set, E denotes the (undirected) edge set and A represents the (directed) arc set. Let F ⊆ E ( H ⊆ A ) be the set of required edges (required arcs). There is a nonnegative weight associated with each edge and arc. The objective is to determine no more than k closed walks to cover all the required edges in F and all the required arcs in H such that the weight of the maximum weight closed walk is minimized. By replacing closed walks with (open) walks in the MRPCP, we obtain the Min–Max Mixed Rural Postmen Walk Cover Problem (MRPWCP). The Min–Max Mixed Chinese Postmen Cover Problem (MCPCP) is a special case of the MRPCP where F = E and H = A . The Min–Max Stacker Crane Cover Problem (SCCP) is another special case of the MRPCP where F = ∅ and H = A For the MRPCP with the input graph satisfying the weakly symmetric condition, i.e., for each arc there exists a parallel edge whose weight is not greater than this arc, we devise a 27 4 -approximation algorithm. This algorithm achieves an approximation ratio of 33 5 for the SCCP with the weakly symmetric condition. Moreover, we obtain the first 5-approximation algorithm (4-approximation algorithm) for the MRPWCP (MCPCP) with the weakly symmetric condition. [ABSTRACT FROM AUTHOR]

Under an area-level random regression coefficient Poisson model, this article derives small area predictors of counts and proportions and introduces bootstrap estimators of the mean squared errors (MSEs). The maximum likelihood estimators of the model parameters and the mode predictors of the random effects are calculated by a Laplace approximation algorithm. Simulation experiments are implemented to investigate the behavior of the fitting algorithm, the predictors, and the MSE estimators with and without bias correction. The new statistical methodology is applied to data from the Spanish Living Conditions Survey. The target is to estimate the proportions of women and men under the poverty line by province. [ABSTRACT FROM AUTHOR]

In 1976–1977, Polyak published in the journal Avtomatica i Telemekhanika (Automation and Remote Control) two remarkable papers on how to study the properties of estimates of iterative pseudogradient algorithms. The first paper published in 1976 considered the general case based on the stochastic Lyapunov function, and the second one considered the linear case. The assumptions formulated in these papers and the estimates obtained in them can still be considered the state-of-the art. In the current paper, Polyak's approach is applied to the study of the properties of estimates of a (randomized) stochastic approximation search algorithm for the case of unknown-but-bounded noise in observations. The obtained asymptotic estimates were already known earlier, and exact estimates for a finite number of observations are published for the first time. [ABSTRACT FROM AUTHOR]