Search

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]

The Skolem problem is a long-standing open problem in linear dynamical systems: can a linear recurrence sequence (LRS) ever reach 0 from a given initial configuration? Similarly, the positivity problem asks whether the LRS stays positive from an initial configuration. Deciding Skolem (or positivity) has been open for half a century: the best known decidability results are for LRS with special properties (e.g., low order recurrences). On the other hand, these problems are much easier for “uninitialised” variants, where the initial configuration is not fixed but can vary arbitrarily: checking if there is an initial configuration from which the LRS stays positive can be decided by polynomial time algorithms (Tiwari in 2004, Braverman in 2006). In this paper, we consider problems that lie between the initialised and uninitialised variants. More precisely, we ask if 0 (resp. negative numbers) can be avoided from every initial configuration in a neighbourhood of a given initial configuration. This can be considered as a robust variant of the Skolem (resp. positivity) problem. We show that these problems lie at the frontier of decidability: if the neighbourhood is given as part of the input, then robust Skolem and robust positivity are Diophantine hard, i.e., solving either would entail major breakthroughs in Diophantine approximations, as happens for (non-robust) positivity. Interestingly, this is the first Diophantine hardness result on a variant of the Skolem problem. On the other hand, if one asks whether such a neighbourhood exists, then the problems turn out to be decidable in their full generality, with PSPACE complexity. Our analysis is based on the set of initial configurations such that positivity holds, which leads to new insights into these difficult problems, and interesting geometrical interpretations. [ABSTRACT FROM AUTHOR]

The JPEG algorithm is a defacto standard for image compression. We investigate whether adaptive mesh refinement can be used to optimize the compression ratio and propose a new adaptive image compression algorithm. We prove that it produces a quasi-optimal subdivision grid for a given error norm with high probability. This subdivision can be stored with very little overhead and thus leads to an efficient compression algorithm. We demonstrate experimentally, that the new algorithm can achieve better compression ratios than standard JPEG compression with no visible loss of quality on many images. The mathematical core of this work shows that Binev's optimal tree approximation algorithm is applicable to image compression with high probability, when we assume small additive Gaussian noise on the pixels of the image. [ABSTRACT FROM AUTHOR]

The surge in technology is driving demands for real-time interactive applications and high-speed transmissions, necessitating improved network throughput and energy efficiency (EE) for immersive experiences. The rise in industrial automation has led to higher connectivity needs, straining fifth-generation networks. Sixth-generation networks aim to address these demands, potentially maximizing throughput and EE through enhanced coverage. This paper introduces innovative techniques like phone user clustering-based downlink hybrid multiple access in unmanned aerial vehicle-assisted heterogeneous networks (HetNets) to jointly optimize phone user (PU) admission, cell association, throughput, and EE while ensuring PU fair association with cell (PUFAC) and quality of service (QoS), i.e., minimum rate requirement of PUs. An outer approximation algorithm solves the mixed integer non-linear programming (MINLP) optimization problem arising from the transformation of the concave fractional programming optimization problem using the Charnes-Cooper transformation. The method's effectiveness is assessed, showcasing its superiority over existing macro-cell-only networks and HetNets concerning throughput, EE, PU admission, PU-cell association, PUFAC, and QoS. [ABSTRACT FROM AUTHOR]

"Sim Sala Bim!" —Silvan, https://en.wikipedia.org/wiki/Silvan%5f(illusionist) Betweenness centrality is a popular centrality measure with applications in several domains and whose exact computation is impractical for modern-sized networks. We present SILVAN, a novel, efficient algorithm to compute, with high probability, accurate estimates of the betweenness centrality of all nodes of a graph and a high-quality approximation of the top-k betweenness centralities. SILVAN follows a progressive sampling approach and builds on novel bounds based on Monte Carlo Empirical Rademacher Averages, a powerful and flexible tool from statistical learning theory. SILVAN relies on a novel estimation scheme providing non-uniform bounds on the deviation of the estimates of the betweenness centrality of all the nodes from their true values and a refined characterisation of the number of samples required to obtain a high-quality approximation. Our extensive experimental evaluation shows that SILVAN extracts high-quality approximations while outperforming, in terms of number of samples and accuracy, the state-of-the-art approximation algorithm with comparable quality guarantees. [ABSTRACT FROM AUTHOR]

We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow to rotate the polygons by arbitrary angles. We present a quasi-polynomial time O(1)-approximation algorithm for the general case and a pseudopolynomial time O(1)-approximation algorithm if all input polygons are triangles, both assuming polynomially bounded integral input data. Additionally, we give a quasi-polynomial time algorithm that computes a solution of optimal weight under resource augmentation—that is, we allow to increase the size of the knapsack by a factor of 1+δ for some δ > 0 but compare ourselves with the optimal solution for the original knapsack. To the best of our knowledge, these are the first results for two-dimensional geometric knapsack in which the input objects are more general than axis-parallel rectangles or circles and in which the input polygons can be rotated by arbitrary angles. [ABSTRACT FROM AUTHOR]

Map matching is a common preprocessing step for analysing vehicle trajectories. In the theory community, the most popular approach for map matching is to compute a path on the road network that is the most spatially similar to the trajectory, where spatial similarity is measured using the Fréchet distance. A shortcoming of existing map matching algorithms under the Fréchet distance is that every time a trajectory is matched, the entire road network needs to be reprocessed from scratch. An open problem is whether one can preprocess the road network into a data structure, so that map matching queries can be answered in sublinear time. In this article, we investigate map matching queries under the Fréchet distance. We provide a negative result for geometric planar graphs. We show that, unless SETH fails, there is no data structure that can be constructed in polynomial time that answers map matching queries in O((pq)1-δ) query time for any δ > 0, where p and q are the complexities of the geometric planar graph and the query trajectory, respectively. We provide a positive result for realistic input graphs, which we regard as the main result of this article. We show that for c-packed graphs, one can construct a data structure of \(\tilde{O}(cp)\) size that can answer (1+ε)-approximate map matching queries in \(\tilde{O}(c^4 q \log ^4 p)\) time, where \(\tilde{O}(\cdot)\) hides lower-order factors and dependence on ε. [ABSTRACT FROM AUTHOR]

This paper investigates the potential of active reconfigurable intelligent surfaces (RIS) to enhance wireless-powered communication networks (WPCNs), addressing the evolving connectivity needs of the internet of things (IoT). Active RIS, capable of amplifying and reflecting signals, offers a solution to surpass the limitations of passive RIS, such as double-fading attenuation, aiming to significantly improve network throughput and coverage. Our research focuses on exploiting the amplification capabilities of active RIS to boost the overall network sum throughput, engaging in a comprehensive optimization of critical network parameters, including time allocation, reflection coefficients, and phase shift matrices specific to active RIS. The formulated problem is non-convex and highly complex due to the coupling of optimization variables. We employed a successive convex approximation algorithm to solve the throughput maximization problem by converting the non-convex constraints into approximated convex constraints and solving them iteratively. Through extensive simulations, we demonstrate that our active RIS-assisted network substantially outperforms networks facilitated by passive RIS, marking a significant advancement in WPCN performance. These findings underscore the potential of active RIS technology in realizing the full capabilities of IoT connectivity. [ABSTRACT FROM AUTHOR]

In this paper, we consider the $ k $-prize-collecting minimum power cover problem ($ k $-PCPC), which is defined as follows. Given a set $ X = \{x_1, x_2, $ $ \cdots, x_n\} $ of $ n $ points and a set $ S = \{s_1, s_2, \cdots, s_m\} $ of $ m $ sensors on the plane $ \mathbb{R}^2 $, an integer $ k $ satisfying $ 0 \leq k \leq n $ and a penalty function $ \pi: X \rightarrow \mathbb{R}_0^{+} $, each sensor $ s\in S $ can adjust its power $ p(s) $ and the covering range, which is a disk of radius $ r(s) $ satisfying $ p(s) = c\cdot r(s)^\alpha $, where $ \alpha\geq 1 $ and $ c>0 $ are constants. We are asked to determine a set of disks $ \mathcal{F} $ such that at least $ k $ points are covered, where the center of any disk in $ \mathcal{F} $ is a sensor. The objective is to minimize the total power of the set of disks $ \mathcal{F} $ plus the penalty of $ R $, where $ R $ is the set of points that are not covered by $ \mathcal{F} $. It has been proven that this problem is NP-hard and admits a $ 3^\alpha $-approximation algorithm. By using some properties of relaxed independent sets and combining the guessing technique and the primal-dual method, we design an $ O(\alpha) $-approximation algorithm. Numerical experiments are tested to evaluate the performance of the $ 3^\alpha $-approximation algorithm and our new algorithm. [ABSTRACT FROM AUTHOR]

We consider single-machine scheduling with a non-renewable resource. In this setting, we are given a set of jobs, each characterized by a processing time, a weight, and a resource requirement. At fixed points in time, certain amounts of the resource are made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that each job has enough resource available at the start of its processing. The objective that we consider is the minimization of the sum of weighted completion times. The main contribution of the paper is a PTAS for the case of 0 processing times ( 1 | r m = 1 , p j = 0 | ∑ w j C j ). In addition, we show strong NP-hardness of the case of unit resource requirements and weights ( 1 | r m = 1 , a j = 1 | ∑ C j ), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the latter problem. Finally, we investigate a variant of the problem where processing times are 0 and the resource arrival times are unknown. We present a (4 + ϵ) -approximation algorithm, together with a (4 - ε) -inapproximability result, for any ε > 0 . [ABSTRACT FROM AUTHOR]

In solving the whole process of interaction between soft rock and yielding support in high-stress environments in tunnels using mechanical analysis methods, it is challenging to simultaneously satisfy both displacement coordination and static equilibrium at the contact surface between the rock and the support structure. This paper, based on the mechanical analysis of rock and rigid support, considers the impact of the circumferential installation of yielding elements on radial displacement, and proposes displacement approximation and support force approximation methods using displacement coordination and static equilibrium as approximation conditions. The study fits curves of numerical simulation results and laboratory test results of yielding elements, and attempts to directly use the laboratory test data set of yielding elements as computational data. By calculating two circular tunnel examples and comparing the effects of the trisection method, bisection method, and substitution method on the convergence of the displacement approximation method, the effectiveness of the methods proposed in this paper is verified. The research results show that the two approximation algorithms proposed in this paper have good accuracy and reliability in calculating the relative displacement of rock and yielding support structure contact surfaces, and the support force of yielding support. The bisection method outperforms the trisection and substitution methods in terms of stability and convergence. However, there are certain limitations in this study, such as the effectiveness of the algorithm may be influenced by geological conditions; the complexity of actual geological conditions may exceed the assumptions of the current rock-support mechanical analysis model. [ABSTRACT FROM AUTHOR]

Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a global simple multiobjective evolutionary algorithm (GSEMO) and apply it on a minimum weight general cover problem, which is general enough to subsume many important problems including the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is nonsubmodular. We show that GSEMO yields theoretically guaranteed approximation ratios matching those achievable by a greedy algorithm in expected polynomial time when the potential function g is polynomial in the input size and the minimum gap between different g-values is a constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by National Natural Science Foundation of China [11771013, U20A2068]; Zhejiang Provincial Natural Science Foundation of China [LD19A010001]. [ABSTRACT FROM AUTHOR]

In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both nonadaptive and adaptive settings. It is shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to underrepresentation or overrepresentation of some particular groups. This motivates us to study the submodular maximization problem with group equality, in which we aim to select a group of items to maximize a (possibly nonmonotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint and other fairness notations. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0384. [ABSTRACT FROM AUTHOR]

Rank aggregation combines the preference rankings of multiple alternatives from different voters into a single consensus ranking, providing a useful model for a variety of practical applications but posing a computationally challenging problem. In this paper, we provide an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and an enhanced late acceptance local search method reinforced by a relaxed acceptance and replacement strategy and a fast incremental evaluation mechanism. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on both synthetic and real-world benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, a well-established machine learning task. We additionally analyze several key algorithmic components to gain insight into their operation. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant 72371157] and Shanghai Pujiang Programme [Grant 23PJC069]. 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.0019) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0019). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Quantum approximate optimization algorithms are hybrid quantum-classical variational algorithms designed to approximately solve combinatorial optimization problems such as the MAX-CUT problem. In spite of its potential for near-term quantum applications, it has been known that quantum approximate optimization algorithms have limitations for certain instances to solve the MAX-CUT problem, at any constant level p. Recently, the recursive quantum approximate optimization algorithm, which is a non-local version of quantum approximate optimization algorithm, has been proposed to overcome these limitations. However, it has been shown by mostly numerical evidences that the recursive quantum approximate optimization algorithm outperforms the original quantum approximate optimization algorithm for specific instances. In this paper, we analytically prove that the recursive quantum approximate optimization algorithm is more competitive than the original one to solve the MAX-CUT problem for complete graphs with respect to the approximation ratio. [ABSTRACT FROM AUTHOR]

Objective: Elective‐emergency admission control referred to allocating available inpatient bed capacity between elective and emergency hospitalization demand. Existing approaches for admission control often excluded several complex factors when making decisions, such as uncertain bed capacity and unknown true probability distributions of patient arrivals and departures. We aimed to create a data‐driven newsvendor framework to study the elective‐emergency admission control problem to achieve bed operational efficiency and effectiveness. Methods: We developed a data‐driven approach that utilized the newsvendor framework to formulate the admission control problem. We also created approximation algorithms to generate a pool of candidate admission control solutions. Past observations and relevant emergency demand and bed capacity features were modeled in a newsvendor framework. Using approximation algorithmic approaches (sample average approximation, separated estimation and optimization, linear programing‐LP, and distribution‐free model) allowed us to derive computationally efficient data‐driven solutions with tight bounds on the expected in‐sample and out‐of‐sample cost guaranteed. Results: Tight generalization bounds on the expected out‐of‐sample cost of the feature‐based model were derived with respect to the LP and quadratic programing (QP) algorithms, respectively. Results showed that the optimal feature‐based model outperformed the optimal observation‐based model with respect to the expected cost. In a setting where the unit overscheduled cost was higher than the unit under‐scheduled cost, scheduling fewer elective patients would replace the benefit of incorporating related features in the model. The tighter the available bed capacity for elective patients, the bigger the difference of the schedule cost between the feature‐based model and the observation‐based model. Conclusions: The study provides a reference for the theoretical study on bed capacity allocation between elective and emergency patients under the condition of the unknown true probability distribution of bed capacity and emergency demand, and it also proves that the approximate optimal policy has good performance. [ABSTRACT FROM AUTHOR]

We abstract and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph G=(V,E) and a set of demand pairs P⊆VxV, a reachability preserver is a sparse subgraph H that preserves reachability between all demand pairs. Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an n-node graph and demand pairs of the form P⊆SxV for a small node subset S, there is always a reachability preserver on O(n+√n/P//S/) edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which O(n) size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the O(n0.6+ε) of Chlamatac, et al. [Approximating spanners and directed steiner forest: Upper and lower bounds, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 534-443] (n4/7+ε). [ABSTRACT FROM AUTHOR]

Continual Learning (CL) plays a crucial role in enhancing learning performance for both new and previous tasks in continuous data streams, thus contributing to the advancement of cognitive computing. However, CL faces a fundamental challenge known as the stability-plasticity quandary. In this research, we present an innovative and effective CL algorithm called Primary Null Space Projection (PNSP) to strike a balance between network plasticity and stability. PNSP consists of three main components. Firstly, it leverages the NSP-LRA algorithm to project the gradient of network parameters from previous tasks into a meticulously designed null space. NSP-LRA harnesses high-dimensional geometric information extracted from the feature covariance matrix through low-rank approximation algorithm to obtain the basis of null space dynamically. This process constructs an innovation null space and ensures the continuous updating of orthonormal bases to accommodate changes in the input data. Secondly, we propose a Consistency-guided Task-specific Feature Learning (CTFL) mechanism to tackle the issue of catastrophic forgetting and facilitate continual learning. CTFL achieves this by aligning feature vectors and maintaining consistent feature learning directions, thereby preventing the loss of previously acquired knowledge. Lastly, we introduce Label Guided Self-Distillation (LGSD), a technique that utilizes true labels to guide the distillation process and incorporates a dynamic temperature mechanism to enhance performance. To evaluate the effectiveness of our proposed method, we conduct experiments on the CIFAR100 and TinyImageNet datasets. The results demonstrate significant improvements over state-of-the-art methods. We have made the implementation code of our approach available for reference. • Proposal of PNSP method: Addresses stability-plasticity dilemma in continual learning. • NSP-LRA: Dynamically constructs null space for minimizing interference. • CTFL mechanism: Ensures consistent feature learning directions. • LGSD technique: Incorporates true labels and dynamic temperature for enhanced distillation. [ABSTRACT FROM AUTHOR]

We present approximation algorithms for several network design problems in the model of flexible graph connectivity (Adjiashvili et al., in: IPCO, pp 13–26, 2020, Math Program 1–33, 2021). Let k ≥ 1 , p ≥ 1 and q ≥ 0 be integers. In an instance of the (p, q)-Flexible Graph Connectivity problem, denoted (p , q) -FGC , we have an undirected connected graph G = (V , E) , a partition of E into a set of safe edges S and a set of unsafe edges U , and nonnegative costs c : E → R ≥ 0 on the edges. A subset F ⊆ E of edges is feasible for the (p , q) -FGC problem if for any set F ′ ⊆ U with | F ′ | ≤ q , the subgraph (V , F \ F ′) is p-edge connected. The algorithmic goal is to find a feasible solution F that minimizes c (F) = ∑ e ∈ F c e . We present a simple 2-approximation algorithm for the (1 , 1) -FGC problem via a reduction to the minimum-cost rooted 2-arborescence problem. This improves on the 2.527-approximation algorithm of Adjiashvili et al. Our 2-approximation algorithm for the (1 , 1) -FGC problem extends to a (k + 1) -approximation algorithm for the (1 , k) -FGC problem. We present a 4-approximation algorithm for the (k , 1) -FGC problem, and an O (q log | V |) -approximation algorithm for the (p , q) -FGC problem. Finally, we improve on the result of Adjiashvili et al. for the unweighted (1 , 1) -FGC problem by presenting a 16/11-approximation algorithm. The (p , q) -FGC problem is related to the well-known Capacitatedk-Connected Subgraph problem (denoted Cap- k -ECSS ) that arises in the area of Capacitated Network Design. We give a min (k , 2 u max) -approximation algorithm for the Cap- k -ECSS problem, where u max denotes the maximum capacity of an edge. [ABSTRACT FROM AUTHOR]

In the 70 s, Berge introduced 1-extendable graphs (also called B-graphs), which are graphs where every vertex belongs to a maximum independent set. Motivated by an application in the design of wireless networks, we study the computational complexity of 1-extendability, the problem of deciding whether a graph is 1-extendable. We show that, in general, 1-extendability cannot be solved in 2 o (n) time assuming the Exponential Time Hypothesis, where n is the number of vertices of the input graph, and that it remains NP-hard in subcubic planar graphs and in unit disk graphs (which is a natural model for wireless networks). Although 1-extendability seems to be very close to the problem of finding an independent set of maximum size (a.k.a.Maximum Independent Set), we show that, interestingly, there exist 1-extendable graphs for which Maximum Independent Set is NP-hard. Finally, we investigate a parameterized version of 1-extendability. [ABSTRACT FROM AUTHOR]

Given a graph G, the minimum Connected- k -Subgraph Cover problem (MinC k SC) is to find a minimum vertex subset C of G such that every connected subgraph of G on k vertices has at least one vertex in C. If furthermore the subgraph of G induced by C is connected, then the problem is denoted as MinC k SC $_{con}$. In this paper, we first present a PTAS for MinC k SC on an H -minor-free graph, where H is a graph with a constant number of vertices. Then, we design an $O((\omega+1)(2(k-1)(\omega+2))^{3\omega+3})|V|$ -time FPT algorithm for MinC k SC $_{con}$ on a graph with treewidth $\omega$ , based on which we further design an $O(2^{O(\sqrt{t}\log t)}|V|^{O(1)})$ time subexponential FPT algorithm for MinC k SC $_{con}$ on an H -minor-free graph, where t is an upper bound of solution size. [ABSTRACT FROM AUTHOR]

This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. MESP is widely applied to many areas, including healthcare, power systems, manufacturing, and data science. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to study efficient approximation algorithms and develop their approximation bounds for MESP, which improves the best known one in the literature. This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to develop a sampling algorithm and derive its approximation bound for MESP, which improves the best known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. Besides, we investigate the widely used local search algorithm and prove its first known approximation bound for MESP. The proof techniques further inspire for us an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-size and large-scale instances to near optimality. Finally, we extend the analyses to the A-optimal MESP, for which the objective is to minimize the trace of the inverse of the selected principal submatrix. Funding: This work was supported by the National Science Foundation Division of Information and Intelligent Systems [Grant 2246417] and Division of Civil, Mechanical and Manufacturing Innovation [Grant 2246414]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.2488. [ABSTRACT FROM AUTHOR]

We consider the non-preemptive scheduling problem on identical machines where there is a parameter B and each machine in every unit length time interval can process up to B different jobs. The goal function we consider is the makespan minimization and we develop an EPTAS for this problem. Prior to our work a PTAS was known only for the case of one machine and constant values of B, and even the case of non-constant values of B on one machine was not known to admit a PTAS. [ABSTRACT FROM AUTHOR]

The energy-harvesting sensor network is a new network architecture to further prolong the lifetime of sensor networks and enhance the quality of IoT services. Due to the inherent problems of energy-harvesting sensor networks, it is really hard to collect fresh and useful sensory data. To solve the above problems, we investigate the data collection scheme in edge-assisted energy-harvesting sensor networks and try to collect fresh and useful sensory data from such networks. Enlightened by the concept of the age of information, we define a new metric, the age of useful information (AoUI), to measure the usefulness and freshness of the sensory data. Furthermore, we define the Minimizing the Maximum Age of Useful Information problem (Min-AoUI) to construct a sensory data collection method to minimize the AoUI of the sensory data. We prove that the Min-AoUI problem is NP-Hard, and approximation algorithms are proposed to solve this problem. The time complexity and the approximation ratio of this algorithm are analyzed. The performance of the algorithm is also verified by extensive experimental results. [ABSTRACT FROM AUTHOR]

A collection of graphs is nearly disjoint if every pair of them intersects in at most one vertex. We prove that if $G_1, \dots, G_m$ are nearly disjoint graphs of maximum degree at most $D$ , then the following holds. For every fixed $C$ , if each vertex $v \in \bigcup _{i=1}^m V(G_i)$ is contained in at most $C$ of the graphs $G_1, \dots, G_m$ , then the (list) chromatic number of $\bigcup _{i=1}^m G_i$ is at most $D + o(D)$. This result confirms a special case of a conjecture of Vu and generalizes Kahn's bound on the list chromatic index of linear uniform hypergraphs of bounded maximum degree. In fact, this result holds for the correspondence (or DP) chromatic number and thus implies a recent result of Molloy and Postle, and we derive this result from a more general list colouring result in the setting of 'colour degrees' that also implies a result of Reed and Sudakov. [ABSTRACT FROM AUTHOR]

In this paper, we consider the copositive optimization problem with high-order copositive tensors, which can be used to estimate the coclique number of uniform hypergraphs. Firstly, we present a checkable equivalent condition for the Slater constraint qualification. Then, based on the standard simplex, we focus on solving a new kind of CTOP from hypergraph theory. To do that, two approximation problems are established and a linear approximation algorithm is proposed for the original CTOP. It is proven that the optimal value of the original problem lies between the optimal values of the two approximation problems. Furthermore, relationships between the optimal solutions are considered. Finally, the proposed algorithm is applied to estimate the coclique number of uniform hypergraphs, and numerical results show its efficiency. [ABSTRACT FROM AUTHOR]

Multiobjective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multiobjective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve multiobjective combinatorial optimization problems. We study the application of this scheme to the network routing problem in detail, by first mapping it to the multiobjective shortest-path problem. Focusing on an implementation based on the quantum approximate optimization algorithm (QAOA)—the go-to approach for tackling optimization problems on near-term quantum computers—we examine the Pareto plot that results from the scheme and qualitatively analyze its ability to produce Pareto-optimal solutions. We further provide theoretical and numerical scaling analyses of the resource requirements and performance of QAOA and identify key challenges associated with this approach. Finally, through Amazon Braket, we execute small-scale implementations of our scheme on the IonQ Harmony 11-qubit quantum computer.

In this paper, we study the regular sensory data collection of Points of Interest (PoIs) with multiple Unmanned Aerial Vehicles (UAVs) during an extended monitoring period, where each PoI is visited multiple times before its data update deadline to keep the data fresh. We observe that most existing studies ignored the important differences in the data stored in the PoIs, scheduled a plan that dispatched UAVs to visit all PoIs before the same deadline, and simply repeated the plan during the monitoring period, which undoubtedly increased the service cost of the UAVs. Considering the specific data update deadline of each PoI, we formulate a novel UAV cost minimization problem to collect the data stored in each PoI before its deadline by finding a series of plans for UAVs such that the service cost of the UAVs during the monitoring period is minimized; the service cost of the UAVs is composed of the consumed energy of the UAVs utilized for hovering for data collection and the consumed energy of the UAVs utilized for flying. To deal with the above NP-hard problem, we devise an approximation algorithm by grouping the PoIs and accessing them in batches. Then, we analyze the proposed algorithm and evaluate the performance of the algorithm through experimental simulations. The experimental results show that the proposed algorithm is very promising. [ABSTRACT FROM AUTHOR]

In this paper we give a quantitative analysis of an explicit iteration method due to C.E. Chidume for the approximation of a zero of an m-accretive operator A : X → 2 X in Banach spaces which does not involve the computation of the resolvent of A. [ABSTRACT FROM AUTHOR]

This paper constructs an interval partition linearization algorithm for solving minimax linear fractional programming (MLFP) problem. In this algorithm, MLFP is converted and decomposed into a series of linear programs by dividing the outer 1-dimensional space of the equivalent problem (EP) into polynomially countable intervals. To improve the computational efficiency of the algorithm, two new acceleration techniques are introduced, in which the regions in outer space where the optimal solution of EP does not exist are largely deleted. In addition, the global convergence of the proposed algorithm is summarized, and its computational complexity is illustrated to reveal that it is a fully polynomial time approximation scheme. Finally, the numerical results demonstrate that the proposed algorithm is feasible and effective. [ABSTRACT FROM AUTHOR]

The local linear approximation algorithm is an effective algorithm for computing a global solution of the folded concave penalization problem. However, the effectiveness of this method is highly dependent on a reasonably good initial estimator. It will lose efficacy when the correlation among predictors is high. In this paper, we propose a new local linear approximation ridge algorithm designed to deal with highly correlated predictors. The ridge estimator is chosen as an initial estimator, the local linear approximation ridge algorithm is stable and effective. Simulation studies and a real data analysis show that the proposed algorithm has better performance than the local linear approximation algorithm in the presence of highly correlated predictors. [ABSTRACT FROM AUTHOR]

Solving combinatorial problems on complex networks represents a primary issue which, on a large scale, requires the use of heuristics and approximate algorithms. Recently, neural methods have been proposed in this context to find feasible solutions for relevant computational problems over graphs. However, such methods have some drawbacks: (1) they use the same neural architecture for different combinatorial problems without introducing customizations that reflects the specificity of each problem; (2) they only use a nodes local information to compute the solution; (3) they do not take advantage of common heuristics or exact algorithms. Following this interest, in this research we address these three main points by designing a customized attention-based mechanism that uses both local and global information from the adjacency matrix to find approximate solutions for the Minimum Vertex Cover Problem. We evaluate our proposal with respect to a fast two-factor approximation algorithm and a widely adopted state-of-the-art heuristic both on synthetically generated instances and on benchmark graphs with different scales. Experimental results demonstrate that, on the one hand, the proposed methodology is able to outperform both the two-factor approximation algorithm and the heuristic on the test datasets, scaling even better than the heuristic with harder instances and, on the other hand, is able to provide a representation of the nodes which reflects the combinatorial structure of the problem. [ABSTRACT FROM AUTHOR]

This paper considers several two-machine open shop problems with two agents. Each agent has an independent set of nonpreemptive jobs, and the objective is to find either a schedule minimizing a linear combination of the makespans of both agents, a schedule minimizing the makespan of one agent with the makespan of the other agent not exceeding a threshold, or all Pareto-optimal schedules with respect to the makespans of both agents. We present a number of results for the problems above, including a polynomial algorithm and a pseudo-polynomial algorithm for special cases, non-approximability, two approximation algorithms, and a fully polynomial-time approximation scheme. Finally, we run numerical experiments to show the effectiveness of the pseudo-polynomial algorithm and the approximation algorithms. [ABSTRACT FROM AUTHOR]

Numerical algorithms for calculating the left- and right-sided Riemann–Liouville fractional integrals and the left- and right-sided fractional derivatives in the Caputo sense using spline interpolation techniques are derived. The spline of the fifth degree (the so-called quintic spline) is mainly taken into account, but the linear and cubic splines are also considered to compare the quality of the developed method and numerical calculations. The estimation of errors for the derived approximation algorithms is presented. Examples of the numerical evaluation of the fractional integrals and derivatives are executed using 128-bit floating-point numbers and arithmetic routines. For each derived algorithm, the experimental orders of convergence are calculated. Also, an illustrative computational example showing the action of the considered fractional operators on the symmetric function in the interval is presented. [ABSTRACT FROM AUTHOR]

In this paper, we study the following robust optimization problem. Given a set family representing feasibility and candidate objective functions, we choose a feasible set, and then an adversary chooses one objective function, knowing our choice. The goal is to find a randomized strategy (i.e., a probability distribution over the feasible sets) that maximizes the expected objective value in the worst case. This problem is fundamental in wide areas such as artificial intelligence, machine learning, game theory, and optimization. To solve the problem, we provide a general framework based on the dual linear programming problem. In the framework, we utilize the ellipsoid algorithm with the approximate separation algorithm. We prove that there exists an α -approximation algorithm for our robust optimization problem if there exists an α -approximation algorithm for finding a (deterministic) feasible set that maximizes a nonnegative linear combination of the candidate objective functions. Using our result, we provide approximation algorithms for the max–min fair randomized allocation problem and the maximum cardinality robustness problem with a knapsack constraint. [ABSTRACT FROM AUTHOR]

In the general max–min fair allocation problem, there are m players and n indivisible resources, each player has his/her own utilities for the resources, and the goal is to find an assignment that maximizes the minimum total utility of resources assigned to a player. The problem finds many natural applications such as bandwidth distribution in telecom networks, processor allocation in computational grids, and even public-sector decision making. We introduce an over-estimation strategy to design approximation algorithms for this problem. When all utilities are positive, we obtain an approximation ratio of c 1 - ϵ , where c is the maximum ratio of the largest utility to the smallest utility of any resource. When some utilities are zero, we obtain an approximation ratio of (1 + 3 c ^ + O (δ c ^ 2)) , where c ^ is the maximum ratio of the largest utility to the smallest positive utility of any resource. [ABSTRACT FROM AUTHOR]

Bayesian optimization algorithms are widely used for solving problems with a high computational complexity in terms of objective function evaluation. The efficiency of Bayesian optimization is strongly dependent on the quality of the surrogate models of an objective function, which are built and refined at each iteration. The quality of surrogate models, and hence the performance of an optimization algorithm, can be greatly improved by selecting the appropriate hyperparameter values of the approximation algorithm. The common approach to finding good hyperparameter values for each iteration of Bayesian optimization is to build surrogate models with different hyperparameter values and choose the best one based on some estimation of the approximation error, for example, a cross-validation score. Building multiple surrogate models for each iteration of Bayesian optimization is computationally demanding and significantly increases the time required to solve an optimization problem. This paper suggests a new approach, called exploratory landscape validation, to find good hyperparameter values with less computational effort. Exploratory landscape validation metrics can be used to predict the best hyperparameter values, which can improve both the quality of the solutions found by Bayesian optimization and the time needed to solve problems. [ABSTRACT FROM AUTHOR]

Network modeling characterizes the underlying principles of structural properties and is of vital significance for simulating dynamical processes in real world. However, bridging structure and dynamics is always challenging due to the multiple complexities in real systems. Here, through introducing the individual's activity rate and the possibility of group interaction, we propose a probabilistic activity-driven (PAD) model that could generate temporal higher-order networks with both power-law and high-clustering characteristics, which successfully links the two most critical structural features and a basic dynamical pattern in extensive complex systems. Surprisingly, the power-law exponents and the clustering coefficients of the aggregated PAD network could be tuned in a wide range by altering a set of model parameters. We further provide an approximation algorithm to select the proper parameters that can generate networks with given structural properties, the effectiveness of which is verified by fitting various real-world networks. Finally, we construct the co-evolution framework of the PAD model and higher-order contagion dynamics and derive the critical conditions for phase transition and bistable phenomenon using theoretical and numerical methods. Results show that tendency of participating in higher-order interactions can promote the emergence of bistability but delay the outbreak under heterogeneous activity rates. Our model provides a basic tool to reproduce complex structural properties and to study the widespread higher-order dynamics, which has great potential for applications across fields. [ABSTRACT FROM AUTHOR]

In this paper we analyze the links between the agent's reservation utility, bargaining power, and risk aversion in terms of their simultaneous effects on the structure of optimal static contracts. We compare the following principal-agent models in the symmetric and asymmetric information environments: the standard approach, which includes a participation constraint, and a multi-objective (MO) optimization approach in which the objective function is a convex combination of the expected utilities of the principal and the agent. The MO model does not include a participation constraint, but it includes a parameter for the agent's bargaining power. We also study an Evolutionary Algorithm implementation of the static principal-agent model to support and extend our analytical results. We show that the numerical solution approximated by our implementation of an evolutionary algorithm is in line with the analytical solutions mentioned before. That is, for every admissible value of the agent's reservation utility, there is a corresponding admissible value of the agent's bargaining parameter, both in the MO approach and the EA implementation. [ABSTRACT FROM AUTHOR]

Identifying shortest paths between nodes in a network is a common graph analysis problem that is important for many applications involving routing of resources. An adversary that can manipulate the graph structure could alter traffic patterns to gain some benefit (e.g., make more money by directing traffic to a toll road). This article presents the Force Path Cut problem, in which an adversary removes edges from a graph to make a particular path the shortest between its terminal nodes. We prove that the optimization version of this problem is APX-hard but introduce PATHATTACK, a polynomial-time approximation algorithm that guarantees a solution within a logarithmic factor of the optimal value. In addition, we introduce the Force Edge Cut and Force Node Cut problems, in which the adversary targets a particular edge or node, respectively, rather than an entire path. We derive a nonconvex optimization formulation for these problems and derive a heuristic algorithm that uses PATHATTACK as a subroutine. We demonstrate all of these algorithms on a diverse set of real and synthetic networks, illustrating where the proposed algorithms provide the greatest improvement over baseline methods. [ABSTRACT FROM AUTHOR]

We consider a single machine rescheduling problem where a set of original jobs have been scheduled to minimize the total weighted completion time. However, before formal processing begins, a new set of jobs arrives and creates a disruption. The decision maker can reject a subset of the new jobs by paying certain rejection penalties, and reschedule the original and the remaining new jobs without excessively disrupting the original schedule, which is measured by the maximum completion time deviation for any original jobs between the original and adjusted schedules. The objective is to minimize the sum of total weighted completion time of the original jobs and the accepted new jobs in the adjusted schedule, the weighted maximum completion time deviation and the total rejection cost. We first provide a dynamic programming-based exact algorithm running in pseudo-polynomial time, and then propose a fully polynomial time approximation scheme. Given the NP-hardness for the studied problem, our result is the best possible from the approximation algorithm perspective. In addition, we conduct extensive computational experiments to evaluate the performance of our proposed methods, and provide some managerial insights on their applicability under different situations. [ABSTRACT FROM AUTHOR]

Aiming to address problems such as low sampling success rate and long computation time in the motion planning of a dual-arm cooperative system with multiple constraints, this paper proposes an Informed-Bi-Quick RRT* algorithm based on offline sampling. First, in the process of pre-sampling, the new algorithm relaxes the approximation of constrained manifolds by introducing the idea of incremental construction, and it incorporates the stochastic gradient descent method to replace global random sampling with local random sampling, which enriches the data set and shortens the offline sampling time of the data set. Second, the new algorithm improves the original Quick-RRT* algorithm by combining the two-tree idea and the multi-target bias expansion strategy, and it improves the adaptability of the algorithm to different obstacle environments. In addition, the loosely constrained motion and tightly constrained motion in the two-arm cooperative system are analyzed, and the adaptive planning of the two-arm trajectory in different motions is described in detail. In this paper, the two-arm cooperative model constructed with UR5 and UR10 robot arms is studied, and the ability of the proposed algorithm to deal with multiple constraints is verified by simulating assembly and handling tasks. The experimental results show that compared with other methods, the proposed algorithm has obvious advantages in path quality and planning efficiency. [ABSTRACT FROM AUTHOR]