Search

This paper explores the concept of proportional lumpability as an extension of the original definition of lumpability, addressing the challenges posed by the state space explosion problem in computing performance indices for large stochastic models. Lumpability traditionally relies on state aggregation techniques and is applicable to Markov chains demonstrating structural regularity. Proportional lumpability extends this idea, proposing that the transition rates of a Markov chain can be modified by certain factors, resulting in a lumpable new Markov chain. This concept facilitates the derivation of precise performance indices for the original process. This paper establishes the well-defined nature of the problem of computing the coarsest proportional lumpability that refines a given initial partition, ensuring a unique solution exists. Additionally, a polynomial time algorithm is introduced to solve this problem, offering valuable insights into both the concept of proportional lumpability and the broader realm of partition refinement techniques. The effectiveness of proportional lumpability is demonstrated through a case study that consists of designing a model to investigate selfish mining behaviors on public blockchains. This research contributes to a better understanding of efficient approaches for handling large stochastic models and highlights the practical applicability of proportional lumpability in deriving exact performance indices. [ABSTRACT FROM AUTHOR]

Quantum computing has made many important achievements in the field of cryptanalysis. However, due to the limitations of current physical system and technology, the realization of large-scale universal quantum computers is a long way off. Currently, small-scale quantum computers are easier to implement than large-scale universal quantum computers. Distributed quantum computing proposes an implementation architecture, which attempts to break down large-scale tasks into many sub-tasks distributed across multiple small-scale quantum computers. How to use small-scale quantum computers with fewer qubits and shallower quantum depths to complete large-scale tasks and improve the success rate of attacking symmetric cryptosystems is our concern. In this paper, we propose a distributed exact Simon's algorithm, apply it to achieve quantum key recovery attacks on single-permutation-based pseudorandom cryptographic schemes with classical birthday bound security, and estimate the quantum resources of quantum circuits. Furthermore, we combine distributed exact Grover's algorithm and distributed exact Simon's algorithm to achieve quantum key recovery attacks on two-permutation-based pseudorandom cryptographic schemes with classical beyond birthday bound security and estimate the corresponding quantum resources. Our results show that (1) our algorithms are exact which means that the theoretical success probability of attacking pseudorandom cryptographic schemes is 100%; (2) the depth of circuit is in polynomial time which means that the theoretical depth of attacking symmetric cryptosystems is exponentially accelerated relative to the previous results; (3) the qubits of circuit don't increase significantly. Our work is of great importance. It could lead to the rapid realization of effective quantum attacks against symmetric cryptosystems on small-scale quantum computers. [ABSTRACT FROM AUTHOR]

In this paper we provide a tetrahedra-free algorithm to compute low-cardinality quadrature rules with a given degree of polynomial exactness, positive weights and interior nodes on a polyhedral element with arbitrary shape. The key tools are the notion of Tchakaloff discretization set and the solution of moment-matching equations by Lawson-Hanson iterations for NonNegative Least-Squares. Several numerical tests are presented. The method is implemented in Matlab as open-source software. [ABSTRACT FROM AUTHOR]

Virtual Machine Placement (VMP) plays a significant role in improving efficiency of Cloud Data Center (CDC). With the dramatic increase in the use of cloud computing, it seems necessary to apply effective algorithms to reduce the power consumption of CDC. VMP is known as a NP-Hard problem that cannot be solved by deterministic algorithms in polynomial time. In this paper, an algorithm named Combinated Random Best First Fit (CRBFF) is proposed with the aim of increasing the Quality of Service (QoS), in which Virtual Machines (VMs) are optimally placed on heterogeneous Physical Machines (PMs). The effectiveness of CRBFF is evaluated by different metrics on Google Compute Engine (GCE), Amazon Web Service Elastic Compute Cloud (AWS EC2) and Microsoft Azure scenarios and the results show that CRBFF performs better than other common algorithms. [ABSTRACT FROM AUTHOR]

In this paper we consider the fundamental scheduling problem of minimizing the weighted number of tardy jobs on a single machine. We present a simple pseudo polynomial-time algorithm for this problem that improves upon the classical Lawler and Moore algorithm from the late 60's under certain scenarios and parameter settings. Our algorithm uses (max,+)-convolutions as its main tool, exploiting recent improved algorithms for computing such convolutions, and obtains several different running times depending on the specific improvement used. We also provide a related lower bound for the problem under a variant of the well-known Strong Exponential Time Hypothesis (SETH). History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This work was supported by the Israel Science Foundation [Grant 1070/20]. [ABSTRACT FROM AUTHOR]

This is the second paper in a series of two. The goal of the series is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial time-algorithm that starts with a 4-precoloring of a graph with no induced six-vertex path and outputs a polynomial-sized collection of so-called excellent precolorings. Excellent precolorings are easier to handle than general ones, and, in addition, in order to determine whether the initial precoloring can be extended to the whole graph, it is enough to answer the same question for each of the excellent precolorings in the collection. The first paper in the series deals with excellent precolorings, thus providing a complete solution to the problem. [ABSTRACT FROM AUTHOR]

This is the first paper in a series whose goal is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial-time algorithm that determines if a special kind of precoloring of a P6-free graph has a precoloring extension, and constructs such an extension if one exists. Combined with the main result of the second paper of the series, this gives a complete solution to the problem. [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]

This study focuses on the load balancing of the transactions in the blockchain. The problem is how to assign these transactions to the blocks. The objective is to guarantee a load balancing of the workload in the time of blocks. The proposed problem is an NP-hard one. To face the hardness of the studied problem, the challenge is to develop algorithms that solve the problem approximately. Finding an approximate solution is a real challenge. In this paper, nine algorithms are proposed. These algorithms are based on the dispatching-rules method, randomization approach, clustering algorithms, and iterative method. The proposed algorithms return approximate solutions in a remarkable time. In addition, in this paper, a novel architecture composed of blocks is proposed. This architecture adds the component "Balancer". This component is responsible to call the best-proposed algorithm and solve the scheduling problem in a polynomial time. In addition, the proposed work helps users to solve the problem of big data concurrency. These algorithms are coded and compared. The performance of these algorithms is tested over three classes of instances. These classes are generated based on uniform distribution. The total number of instances tested is 1350. The average gap, execution time, and the percentage of the best-reached value are used as metrics to measure the performance of the proposed algorithms. Experimental results show the performance of these algorithms and a comparison between them is discussed. The experimental results show that the best algorithm is best-mi-transactions iterative multi-choice with 93.9% in an average running time of 0.003 s. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , an L (2 , 1) -labeling of the graph is an assignment ℓ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u , v) , | ℓ (u) − ℓ (v) | ≥ 2 if u and v are adjacent, and ℓ (u) ≠ ℓ (v) if u and v are at distance 2. The L (2 , 1) -labeling problem is to minimize the range of ℓ (i.e., max u ∈ V (ℓ (u)) − min u ∈ V (ℓ (u)) + 1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L (2 , 1) -labeling of unit disk graphs. • An 8-approximation algorithm of L(2,1)-labeling for unit disk graphs with geometric representations is presented. • The previously known bound is 10.67. • The presented algorithm gives a simple periodic labeling based on a new way of partitioning the plane into squares. [ABSTRACT FROM AUTHOR]

Finding all the roots of a nonlinear equation is an important and difficult task that arises naturally in numerous scientific and engineering applications. Sequential iterative algorithms frequently use a deflating strategy to compute all the roots of the nonlinear equation, as rounding errors have the potential to produce inaccurate results. On the other hand, simultaneous iterative parallel techniques require an accurate initial estimation of the roots to converge effectively. In this paper, we propose a new class of global neural network-based root-finding algorithms for locating real and complex polynomial roots, which exploits the ability of machine learning techniques to learn from data and make accurate predictions. The approximations computed by the neural network are used to initialize two efficient fractional Caputo-inverse simultaneous algorithms of convergence orders ς + 2 and 2 ς + 4 , respectively. The results of our numerical experiments on selected engineering applications show that the new inverse parallel fractional schemes have the potential to outperform other state-of-the-art nonlinear root-finding methods in terms of both accuracy and elapsed solution time. [ABSTRACT FROM AUTHOR]

This paper proposes an optimized mobile robot navigation strategy using a functional firefly algorithm (FFA) and choice function. This approach has two key advantages: first, the linear objective function performs efficiently with the single degree and finite-order polynomial time operation, and second, the cartesian constraint performs compactly with the chosen degree of freedom on the finite interval. This functional approach optimizes the size of operational parameters in context with key size, operation time, and a finite range of verification. The choice function achieves parameter order (size) reduction. The attraction characteristic of fireflies is represented by the choice function for optimizing the choice between low and high intensities of fireflies. In 2D and 3D environments, the proposed robot navigation performs well in an uncertain environment with static and dynamic obstacles. This efficiency includes the robot's speed as determined by the choice function's minimum path lengths. The collision-free path is achieved by the non-void family of non-void sets. The obtained results are optimal in terms of path length and navigational time. The proposed controller is also compared with the other existing controllers, and it is observed that the FFA gives the shortest path in less time for the same environmental condition. [ABSTRACT FROM AUTHOR]

In a graph, G = (V , E) without an isolated vertex, a dominating set D ⊆ V , is called a semitotal dominating set if for every vertex u ∈ D there is another vertex v ∈ D such that distance between u and v is at most two in G. Given a graph G = (V , E) without an isolated vertex, the Minimum Semitotal Domination problem is to find a minimum cardinality semitotal dominating set of G. The semitotal domination number , denoted by γ t 2 (G) , is the minimum cardinality of a semitotal dominating set of G. It is known that the decision version of the problem remains NP-complete even when restricted to chordal graphs, chordal bipartite graphs, and planar graphs. Galby et al. (2020) proved that the problem can be solved in polynomial time for bounded MIM-width graphs, which include many well known graph classes, but left the complexity of the problem in strongly chordal graphs unresolved. Henning and Pandey (2019) also asked to resolve the complexity status of the problem in strongly chordal graphs. In this paper, we resolve the complexity of the problem in strongly chordal graphs by designing a linear-time algorithm for the problem. [ABSTRACT FROM AUTHOR]

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of optimization problems solvable by dynamic programming algorithms, and for certain types of equivalence relations between solutions. [ABSTRACT FROM AUTHOR]

The model of superposition queries in symmetric cryptanalysis has yielded remarkable results, such as Simon's period-finding algorithm, which can break many constructions in polynomial time. However, due to limitations of current physical devices, quantum circuits with long depths are often noisy and difficult to realize in practice. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits. In this paper, we propose an offline algorithm model that combines distributed Simon's and Grover's algorithms. This model enables us to perform key recovery attacks on different rounds Feistel structures, Even Mansour construction, and the FX construction, while minimizing the quantum query complexity. Despite being limited to classical queries and offline quantum computations, we leverage the algebraic structure of cryptosystems to achieve successful key recovery attacks. [ABSTRACT FROM AUTHOR]

In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3-manifold is in NP. We emphasize that the manifold and the curve are both inputs to the problem. Moreover, our algorithm also works if the curve is given as a compressed word. Previously, such an algorithm was known for simple (non-compressed) curves, and, in very limited cases, for curves with self-intersections. Furthermore, our algorithm is fixed-parameter tractable in the size of the input 3-manifold. As part of our proof, we obtain new polynomial-time algorithms for compressed curves on surfaces, which we believe are of independent interest. We provide a polynomial-time algorithm which, given an orientable surface and a compressed loop on the surface, computes a canonical form for the loop as a compressed word. In particular, contractibility of compressed curves on surfaces can be decided in polynomial time; prior published work considered only constant genus surfaces. More generally, we solve the following normal subgroup membership problem in polynomial time: given an arbitrary orientable surface, a compressed closed curve γ , and a collection of disjoint normal curves Δ , there is a polynomial-time algorithm to decide if γ lies in the normal subgroup generated by components of Δ in the fundamental group of the surface after attaching the curves to a basepoint. [ABSTRACT FROM AUTHOR]

We study a class of rearrangement problems under a novel pick-n-swap prehensile manipulation model, in which a robotic manipulator, capable of carrying an item and making item swaps, is tasked to sort items stored in lattices of variable dimensions in a time-optimal manner. We systematically analyze the intrinsic optimality structure, which is fairly rich and intriguing, under different levels of item distinguishability (fully-labeled, where each item has a unique label, or partially-labeled, where multiple items may be of the same type) and different lattice dimensions. Focusing on the most practical setting of one and two dimensions, we develop low polynomial time cycle-following-based algorithms that optimally perform rearrangements on 1D lattices under both fully- and partially-labeled settings. On the other hand, we show that rearrangement on 2D and higher-dimensional lattices become computationally intractable to optimally solve. Despite their NP-hardness, we prove that efficient cycle-following-based algorithms remain optimal in the asymptotic sense for 2D fully- and partially-labeled settings, in expectation, using the interesting fact that random permutations induce only a small number of cycles. We further improve these algorithms to provide 1. x -optimality when the number of items is small. Simulation studies corroborate the effectiveness of our algorithms. The implementation of the algorithms from the paper can be found at github.com/arc-l/lattice-rearrangement. [ABSTRACT FROM AUTHOR]

Weighted model counting (WMC) is the task of computing the weighted sum of all satisfying assignments (i.e., models) of a propositional formula. Similarly, weighted model sampling (WMS) aims to randomly generate models with probability proportional to their respective weights. Both WMC and WMS are hard to solve exactly, falling under the # P -hard complexity class. However, it is known that the counting problem may sometimes be tractable, if the propositional formula can be compactly represented and expressed in first-order logic. In such cases, model counting problems can be solved in time polynomial in the domain size, and are known as domain-liftable. The following question then arises: Is it also the case for WMS? This paper addresses this question and answers it affirmatively. Specifically, we prove the domain-liftability under sampling for the two-variables fragment of first-order logic with counting quantifiers in this paper, by devising an efficient sampling algorithm for this fragment that runs in time polynomial in the domain size. We then further show that this result continues to hold even in the presence of cardinality constraints. To empirically validate our approach, we conduct experiments over various first-order formulas designed for the uniform generation of combinatorial structures and sampling in statistical-relational models. The results demonstrate that our algorithm outperforms a state-of-the-art WMS sampler by a substantial margin, confirming the theoretical results. • Model sampling in first-order logic can be liftable, without the need of grounding. • Sampling from two-variable logic with counting is tractable. • Domain recursion is crucial for designing first-order model sampling algorithms. [ABSTRACT FROM AUTHOR]

The fair k -center problem has been paid lots of attention recently. In the fair k -center problem, we are given a set X of points in a metric space and a parameter k ∈ Z + , where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k -center problem objective is minimized. In this paper, we consider the fair k -center problem with outliers and capacity constraints, denoted as the fair k -center with outliers (F k CO) problem and the capacitated fair k -center (CF k C) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + ϵ) -approximations with FPT time for the F k CO and CF k C problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the F k CO problem with some reasonable assumptions. [ABSTRACT FROM AUTHOR]

For many algorithmic problems on graphs of treewidth t, a standard dynamic programming approach gives algorithms with time and space complexity 2O(t)\cdot nO(1). It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form 2O(d)\cdot nO(1), where d is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity 2O(t)...nO(1) on graphs of treewidth t, but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. [ACM Trans. Algorithms, 18 (2022), 17] introduced the Cut\&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity 2O(t) · nO(1). Recently, Hegerfeld and Kratsch (STACS'20) showed that, for some of those problems, the Cut\&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time 2O(d) · nO(1) and polynomial space usage. However, several important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper, we clarify the situation by showing that Hamiltonian cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit 5d · nO(1)-time and polynomial space algorithms on graphs of treedepth d. The algorithms are randomized Monte Carlo with only false negatives. [ABSTRACT FROM AUTHOR]

To address the problem of expensive computation in traditional two-dimensional (2D) direction of arrival (DOA) estimation, in this paper, we propose a 2D DOA estimation method based on a reduced dimension and root-finding MUSIC algorithm for nested planar arrays (NPAs). Specifically, the algorithm proposed in this paper transforms the problem based on 2D spectral peak search into two one-dimensional estimation problems by reducing the dimension, and then transforms the one-dimensional estimation problem into a problem of polynomial root finding. Finally the parameters are paired to realize the 2D DOA estimation. The proposed algorithm not only performs two root finding operations directly according to the 2D spectral function transformation, avoiding the performance degradation caused by intermediate operations, but can also fully exploit the enlarged array aperture offered by NPAs with reduced computational complexity and no need for virtualization. The superiorities of the proposed algorithm in terms of estimation accuracy and complexity are verified by simulations. [ABSTRACT FROM AUTHOR]

In a recent paper, Avis, Bremner, Tiwary and Watanabe gave a method for constructing linear programs (LPs) based on algorithms written in a simple programming language called Sparks. If an algorithm produces the solution x to a problem in polynomial time and space then the LP constructed is also of polynomial size and its optimum solution contains x as well as a complete execution trace of the algorithm. Their method led us to the construction of a compiler called sparktope which we describe in this paper. This compiler allows one to generate polynomial sized LPs for problems in P that have exponential extension complexity, such as matching problems in non-bipartite graphs. In this paper, we describe sparktope, the language Sparks, and the assembler instructions and LP constraints it produces. This is followed by two concrete examples, the makespan problem and the problem of testing if a matching in a graph is maximum, both of which are known to have exponential extension complexity. Computational results are given. In discussing these examples, we make use of visualization techniques included in sparktope that may be of independent interest. The extremely large linear programs produced by the compiler appear to be quite challenging to solve using currently available software. Since the optimum LP solutions can be computed independently they may be useful as benchmarks. Further enhancements of the compiler and its application are also discussed. [ABSTRACT FROM AUTHOR]

The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e. There is a polynomial time 4-approximation for the problem (Bar-Noy et al. STOC 2001) and also a QPTAS (Höhn et al. ICALP 2018). In this paper we study fixed-parameter algorithms for the problem. We show that it is W[1]-hard but it becomes FPT if we can slighly violate the edge demands (resource augmentation) and also if there are at most k different task sizes. Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of f (k) ⋅ n O 휖 (1) that outputs a solution with at most (1 + 휖)k tasks or asserts that there is no solution with at most k tasks. In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times. We show that the other two algorithms extend also to the weighted case of the problem, at the expense of losing a factor of 1 + 휖 in the cost of the selected tasks. [ABSTRACT FROM AUTHOR]

With the increasing maturity of wireless charging technology, especially the development of magnetic resonance wireless charging technology, the employment of mobile charging vehicles and wireless charging technology to replenish sensors' energy to ensure the continuous operation of wireless sensor networks has become a new research hotspot. This paper focused on how to schedule multiple charging vehicles to replenish energy to the sensors in a large-scale wireless sensor network. In order to balance the charging tasks of multiple charging vehicles and reduce the completion time of the whole charging task, the paper proposed the charging task completion time minimization problem, hoping to find K closed charging circles for K charging vehicles, so that the longest completion time among these K vehicles was the shortest. Since the charging task completion time minimization problem was an NP-hard problem and it was difficult to find an optimal solution in polynomial time, this paper proposed an approximation algorithm with a ratio of 5 for this problem. Finally, it demonstrated the performance of the algorithm by simulation experiments, and the experiments show that the actual approximation ratio of the proposed algorithm is less than 2. [ABSTRACT FROM AUTHOR]

In this paper, we propose several algorithms for determining an optimal length tree-like refutation of linear feasibility in systems of Unit Two Variable Per Inequality (UTVPI) constraints. Given an infeasible UTVPI constraint system (UCS), a refutation certifies its infeasibility. The problem of finding refutations in a UCS finds applications in domains such as program verification and operations research. In general, there exist several types of refutations of feasibility in constraint systems. In this paper, we focus on a specific type of refutation called a tree-like refutation. Tree-like refutations are complete , in the sense that if a system of linear constraints is infeasible, then it must have a tree-like refutation. Associated with a refutation is its length, which equals the total number of constraints (accounting for the reuse of constraints) that are used to establish the infeasibility of the corresponding linear constraint system. Our goal in this paper is to find an optimal length tree-like refutation (OTLR) of an infeasible UCS. We describe two deterministic algorithms that find an OTLR of a UCS. If m is the number of constraints, n is the number of variables in the system, and k is the length of an OTLR, then our two algorithms run in O (n 3 ⋅ log k) time and O (m ⋅ n ⋅ k) time respectively. We also propose a true-biased, randomized algorithm for this problem. This algorithm runs in O (m ⋅ n ⋅ log n) time, and returns the length of an OTLR with probability (1 − 1 e). We extend our work to weighted UTVPI constraint systems (WUCS), where a positive weight is associated with each UTVPI constraint. The weight of a tree-like refutation is defined as the sum of the weights of the constraints used by the refutation. The problem of finding a minimum weight refutation in a WUCS is called the weighted optimal length tree-like refutation (WOTLR) problem and is known to be NP-hard. We propose a pseudo-polynomial time algorithm for the WOTLR problem and convert it into a fully polynomial time approximation scheme (FPTAS). [ABSTRACT FROM AUTHOR]

Counting and sampling directed acyclic graphs from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper we show that these tasks can be performed in polynomial time, solving a long-standing open problem in this area. Our algorithms are effective and easily implementable. As we show in experiments, these breakthroughs make thought-to-be-infeasible strategies in active learning of causal structures and causal effect identification with regard to a Markov equivalence class practically applicable. [ABSTRACT FROM AUTHOR]

A crucial research problem in the field of wireless sensor network is to maximize its lifetime. One approach to solve this problem is to group the nodes in clusters or chains. One of the nodes in a cluster or chain takes the responsibility of collecting data from the other sensors in its group and sends the data to the base station or sink. As the energy spent per round is comparatively higher for a cluster head(CH)/chain leader (CL), the lifetime of the network can increase if we rotate the role of CH/CL among the nodes in the cluster/chain. In this paper, we have proposed several algorithms to select CH/CL at different rounds to maximize the lifetime of the WSN. We have shown that maximizing lifetime measured as first node die, can be solved optimally using an integer linear program. Then we have given a polynomial-time algorithm to solve this problem by relaxing to a linear programming problem. We have also given algorithms to maximize the lifetimes measured as half of the nodes die and last node dies. Simulation results indicate significant improvement in the performance of our proposed algorithms compared to BP-DCA, NEECP and naive Bayesian-based algorithm. [ABSTRACT FROM AUTHOR]

Summary of Contribution: Big data analytics has become essential for modern operations research and operations management applications. Statistics methods, such as nonparametric density and function estimation, play important roles in predictive and exploratory data analysis for economics and operations management problems. In this paper, we concentrate on efficiently computing local polynomial regression estimates. We significantly accelerate the computation of such local polynomial estimates by novel applications of multidimensional binary indexed trees (Fenwick 1994) and lazy memory allocation via hashing. Both time and space complexity of our proposed algorithm are nearly linear in the number of inputs. Simulation results confirm the efficiency and effectiveness of our proposed methods. Local polynomial regression is an important class of methods for nonparametric density estimation and regression problems. However, straightforward implementation of local polynomial regression has quadratic time complexity which hinders its applicability in large-scale data analysis. In this paper, we significantly accelerate the computation of local polynomial estimates by novel applications of multidimensional binary indexed trees. Both time and space complexity of our proposed algorithm is nearly linear in the number of input data points. Simulation results confirm the efficiency and effectiveness of our proposed approach. Summary of Contribution. Big data analytics has become essential for modern operations research and operations management applications. Statistics methods, such as nonparametric density and function estimation, play important roles in predictive and exploratory data analysis for economics and operations management problems. In this paper, we concentrate on efficiently computing local polynomial regression estimates. We significantly accelerate the computation of such local polynomial estimates by novel applications of multidimensional binary indexed trees and lazy memory allocation via hashing. Both time and space complexity of our proposed algorithm are nearly linear in the number of inputs. Simulation results confirm the efficiency and effectiveness of our proposed methods. [ABSTRACT FROM AUTHOR]

Wireless sensor networks usually adopt a tree structure for routing, where each node sends and forwards messages to its parent. However, lifetime maximization with tree routing structure is NP-hard, and all algorithms attempting to find the optimal solution run in exponential time unless P = NP . This paper revisits the problem of non-tree routing structure, where a node can send different messages to different neighbors. Though lifetime maximization with non-tree routing can be solved in polynomial time, the existing method transforms it into a series of maximum flow problems, which are either complicated or with high running time. This paper proposes an algorithm with O(mn) running time, where m is the number of edges and n is the number of nodes. The heart of the algorithm is a method to find a routing path from any node to the sink in O(m) time without disconnecting existing routing paths. The proposed algorithm is also suitable for distributed implementation. When a node fails, each influenced node can establish a new routing path in O(m) time. Simulations are conducted to compare the optimal lifetimes of tree structure and non-tree structure on random networks. The results verify the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The uncapacitated transportation problem (UTP) deals with minimizing the transportation costs related to the delivery of a homogeneous product from multi-suppliers to multi-consumers. The application of the UTP can be extended to other areas of operations research, including inventory control, personnel assignment, signature matching, product distribution with uncertainty, multi-period production and inventory planning, employment scheduling, and cash management. Such a UTP with interval-defined demands and suppliers capacities (UTPIDS) is investigated in this paper. In UTPIDS, the demands and suppliers capacities may not be known exactly but vary within an interval due to variation in the economic conditions of the global economy. Following the variation, the minimal total cost of the transportation can also be varied within an interval and thus, the cost bounds can be obtained. Here, although the lower bound solution can be attained methodologically, the correct estimation of the worst case realization (the exact upper bound) on the minimal total transportation cost of the UTPIDS is an NP-hard problem. So, the decision-makers seek for minimizing the transportation costs and they are interested in the estimation of the worst case realization on these minimal costs for better decision making especially, for proper investment and return. In literature very few approaches are available to find this estimation of the worst case realization with some shortcomings. First, we demonstrate that the available heuristic methods fail to obtain the correct estimation of the worst case realization always. In this situation, development of a better heuristic method to find the better near optimal estimation of the worst case realization on the minimal total costs of the UTPIDS is desirable. Then this paper provides a new polynomial time algorithm that runs in O (N2) time (N, higher of the numbers of source and destination nodes) for better estimation. A comparative assessment on solutions of available benchmark instances, some randomly generated numerical example problems and a real-world application shows promising performance of the current technique. So, our new finding would definitely be benefited to practitioners, academics and decision makers who deal with such type of decision making instances. [ABSTRACT FROM AUTHOR]

Waiting at the right location at the right time can be critically important in certain variants of time-dependent shortest path problems. We investigate the computational complexity of time-dependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the nodes. We show that some cases are nondeterministic polynomial-time hard, and others can be solved in polynomial time, depending on the choice of the subset of nodes, on whether waiting is penalized or constrained, and on the magnitude of the penalty/waiting limit parameter. Summary of Contributions: This paper addresses simple yet relevant extensions of a fundamental problem in Operations Research: the Shortest Path Problem (SPP). It considers time-dependent variants of SPP, which can account for changing traffic and/or weather conditions. The first variant that is tackled allows for waiting at certain nodes but at a cost. The second variant instead places a limit on the total waiting. Both variants have applications in transportation, e.g., when it is possible to wait at certain locations if the benefits outweigh the costs. The paper investigates these problems using complexity analysis and algorithm design, both tools from the field of computing. Different cases are considered depending on which of the nodes contribute to the waiting cost or waiting limit (all nodes, all nodes except the origin, a subset of nodes...). The computational complexity of all cases is determined, providing complexity proofs for the variants that are NP-Hard and polynomial time algorithms for the variants that are in P. [ABSTRACT FROM AUTHOR]

• We study the heterogeneous weighted delivery (HWD) problem, which was introduced in [Bärtschi et al., STACS'17]. • We efficiently 8-approximate HWD with k = O (log ⁡ n) agents, closing an open problem in [Bärtschi et al., ATMOS'17]. • We design a O (k) -approximation algorithm that runs in polynomial time regardless of the value of k. • We design a polynomial-time O ˜ (log 3 ⁡ n) -approximation algorithm. • We show that the HWD problem is 36-approximable in polynomial time when each agent has one of two possible consumption rates. We study the heterogeneous weighted delivery (HWD) problem introduced in [Bärtschi et al., STACS'17] where k heterogeneous mobile agents (e.g., robots, vehicles, etc.), initially positioned on vertices of an n -vertex edge-weighted graph G , have to deliver m messages. Each message is initially placed on a source vertex of G and needs to be delivered to a target vertex of G. Each agent can move along the edges of G and carry at most one message at any time. Each agent has a rate of energy consumption per unit of traveled distance and the goal is that of delivering all messages using the minimum overall amount of energy. This problem has been shown to be NP-hard even when k = 1 , and is 4 ρ -approximable where ρ is the ratio between the maximum and minimum energy consumption of the agents. In this paper, we provide approximation algorithms with approximation ratios independent of the energy consumption rates. First, we design a polynomial-time 8-approximation algorithm for k = O (log ⁡ n) , closing a problem left open in [Bärtschi et al., ATMOS'17]. This algorithm can be turned into an O (k) -approximation algorithm that always runs in polynomial-time, regardless of the values of k. Then, we show that HWD problem is 36-approximable in polynomial-time when each agent has one of two possible consumption rates. Finally, we design a polynomial-time O ˜ (log 3 ⁡ n) -approximation algorithm for the general case. [ABSTRACT FROM AUTHOR]

Motivated by the design of cost-efficient communication networks, the problem about Maximum Internal Spanning Tree that arises in a connected graph, is proposed to find a spanning tree with the maximum number of internal vertices. In 2018, Xingfu Li et al. presented a polynomial algorithm to find a maximum internal spanning tree in a connected interval graph. Based on the structure of normal orderings on interval graphs, we present a simple linear time algorithm that solve the problem when restricted to connected interval graphs in this paper. The proof provides additional insight about the linear time algorithm on interval graphs. • The MIST problem is solvable in a simple linear time algorithm under the restriction of connected interval graphs. • The structure of normal orderings on interval graphs is proposed to solve the Maximum Internal Spanning Tree problem. • The proof of the main results is more easy to understand with proper cases to prove. [ABSTRACT FROM AUTHOR]

Dynamic Time Warping (DTW algorithm) provides an effective method to obtain the similarity between unequal-sized signals. However, it cannot directly deal with high-dimensional samples such as matrices. Expanding a matrix to one dimensional vector as the input data of DTW will decrease the measure accuracy because of the losing of position information in the matrix. Aiming at this problem, a two-dimensional dynamic time warping algorithm (2D-DTW) is proposed in this paper to directly measure the similarity between matrices. In 2D-DTW algorithm, a three dimensional distance-cuboid is constructed, and its mapped distance matrix is defined by cutting and compressing the distance-cuboid. By introducing the dynamic programming theory to search the shortest warping path in the mapped matrix, the corresponding shortest distance can be obtained as the expected similarity measure. The experimental results suggest that the performance of 2D-DTW distance is superior to the traditional Euclidean distance and can improve the similarity accuracy between matrices by introducing the warping alignment mechanisms. 2D-DTW algorithm extends the application ranges of traditional DTW and is especially suitable for high-dimensional data. [ABSTRACT FROM AUTHOR]

The longest common palindromic subsequence (LCPS) problem is a variant of the longest common subsequence (LCS) problem. Given two input sequences A and B , the LCPS problem is to find the common subsequence of A and B such that the answer is a palindrome with the maximal length. The LCPS problem was first proposed by Chowdhury et al. (2014) [9] , who proposed a dynamic programming algorithm with O (m 2 n 2) time, where m and n denote the lengths of A and B , respectively. This paper proposes a diagonal-based algorithm for solving the LCPS problem with O (L (m − L) R log ⁡ n) time and O (R L) space, where R denotes the number of match pairs between A and B , and L denotes the LCPS length. In our algorithm, the 3-dimensional minima finding algorithm is invoked to overcome the domination problem. As experimental results show, our algorithm is efficient practically compared with some previously published algorithms. [ABSTRACT FROM AUTHOR]

Gathering is a key task in distributed and mobile systems, which becomes significantly harder if some agents are subject to Byzantine faults, known as being the worst ones. We propose here to study the task of Byzantine gathering in an arbitrary graph: despite the presence of Byzantine agents, the goal is to ensure that all the other (good) agents, executing the same algorithm, eventually meet at the same node and stop. Initially, each agent gets as input a different label and some global knowledge that is common to all agents. The agents move in synchronous rounds and communicate with each other only when located at the same node. There are f Byzantine agents. These agents act in an unpredictable way, e.g., they may convey arbitrary informations or forge any label. In the literature, the gathering algorithms working in such a context all have an exponential time complexity in the number n of nodes and the labels of the good agents. In this paper, we design a deterministic algorithm to solve Byzantine gathering in time polynomial in n and the logarithm ℓ of the smallest label of a good agent, provided the agents are a strong team i.e., a team where the number of good agents is at least some quadratic polynomial in f. Our algorithm requires global knowledge that can be coded in O (log log log n) bits: we prove this size is of optimal order of magnitude to obtain a polynomial time complexity in n and ℓ with strong teams. [ABSTRACT FROM AUTHOR]

This paper studies the following variant of clustering or laying out problems for directed acyclic graphs (DAG for short), called the minimum block transfer problem. The objective of this problem is to find a partition of a node set which satisfies the following two conditions: (i) Each element (called a block) of the partition has a size that is at most B and (ii) the maximum number of external arcs among directed paths from the roots to the leaves is minimized. Here, an external arc is defined as an arc connecting two distinct blocks. This paper mainly studies the case B = 2. First, we show that the problem is NP-hard even if the height of DAGs is three and its maximum indegree and outdegree are two and three, respectively. Then, we design (i) linear-time optimal algorithms for DAGs of height at most two, (ii) a very simple 2-approximation algorithm, and moreover, (iii) a (2 − 2 ∕ h) -approximation algorithm for the case that the height h of the input DAG is even and the other one for odd h , whose approximation ratio is 2 − 2 ∕ (h + 1). As for the inapproximability of the problem, for any ε > 0 and unless P = NP, we show that the problem does not admit any polynomial time (3 ∕ 2 − ε) -approximation ((4 ∕ 3 − ε) -approximation, resp.) algorithm if the height of the input DAGs is restricted to at most five (at least six, resp.). Also, in the case B ≥ 3 , we show the NP-hardness and prove a (3 ∕ 2 − ε) -inapproximability of this case. [ABSTRACT FROM AUTHOR]

Various quantum computing simulation platforms have developed rapidly in the last 3 years. However, few quantum image processing algorithms are simulated in these platforms. In this paper, we design a dual-threshold quantum image segmentation algorithm and simulate it in IBM Q Experience platform through Qiskit extension. The NEQR quantum image representation model is firstly optimized and simulated, which is found that the number of the auxiliary qubits will not increase as the image's size increases. Then, an efficient quantum comparator to realize the comparison of two numbers is designed. And finally, the high parallelism image segmentation algorithm is proposed and simulated. Suppose the size of an image is 2 n × 2 n and the gray-scale scope is [0, 2 q - 1 ], the time complexity analysis for the quantum image segmentation algorithm shows that the number of basic quantum gate required is proportional to q and will not increase as image's size increases. Thus, the proposed quantum segmentation algorithm is highly parallelism and has polynomial time complexity. In addition, the simulation part of this paper will provide reference for other quantum image processing algorithms. [ABSTRACT FROM AUTHOR]

Let G = (V (G);E(G)) be a graph and S be a subset of vertices of G. Let us denote by [u; v] a geodesic between u and v. Let (S) = f [vi; vj ] j vi; vj 2 Sg be a set of exactly jSj(jSj1)=2 geodesics, one for each pair of distinct vertices in S. Let V (1(S)) = S [x;y]2(S) V ([x; y]) be the set of all vertices contained in all the geodesics in (S). If V (1(S)) = V (G) for some (S), then we say that S is a strong geodetic set of G. The cardinality of a minimum strong geodetic set of a graph is the strong geodetic number of G. It is known that it is NP-hard to determine the strong geodetic number of a general graph. In this paper we show that the strong geodetic number of an outerplanar graph can be computed in polynomial time. [ABSTRACT FROM AUTHOR]

The paper attempts to address the robustness issues in circular–circular regression. The Möbius transformation-based link function for circular–circular regression is considered. Defining the concept of breakdown point in this context, the robustness issues of the estimators in this model are discussed. Maximum trimmed cosine estimator in this context is considered and the breakdown point of the estimator is calculated. An exact polynomial time algorithm is then proposed for the computation of the estimator which makes the methodology useful and readily applicable for empirical datasets. Simulation studies show that the estimator is robust with respect to the outliers. An analysis of real data is performed to illustrate the proposed methodology. [ABSTRACT FROM AUTHOR]

A neighbor-sum-distinguishing W -edge-weighting of a graph G = (V , E) is an assignment ω of weights from a set of integers W to the set of edges E of G such that for every pair of adjacent vertices, the incident sums induced by the edge-weighting are different, where the incident sum of a vertex v induced by the edge-weighting ω is σ (v) = ∑ u ∈ N (v) ω (u v) , where N (v) is the set of neighbors of v in G. Whereas, a neighbor-sum- 2 -distinguishing W-edge-weighting of G is a neighbor-sum-distinguishing W -edge-weighting such that the incident sums of every pair of adjacent vertices differ by at least 2. A recently proposed conjecture about neighbor-sum-2-distinguishing { 1 , 3 , 5 } -edge-weighting states that any graph with no component isomorphic to K 2 admits a neighbor-sum-2-distinguishing { 1 , 3 , 5 } -edge-weighting. In this paper, we prove that deciding whether there exists a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting is NP-complete for bipartite graphs. We present an algorithm that computes a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting of the central graph of any graph in polynomial time and thus proves the above conjecture for the central graph of any graph. Further, we establish that if any pair of graphs G and H admit neighbor-sum-2-distinguishing edge-weightings, then so does their Cartesian product, G □ H. We study another aspect of neighbor-sum-2-distinguishing edge-weighting of a graph G , namely, the minimum number of incident sums used by a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting, which is denoted by γ Σ > 1 , { 1 , 3 } (G). We prove that the problems of deciding whether there exists a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting of G from a given set of sums, and deciding whether γ Σ > 1 , { 1 , 3 } (G) ≤ k are NP-complete for bipartite graphs. On the positive side, we provide both upper and lower bounds on γ Σ > 1 , { 1 , 3 } (C (G)) for central graphs of bipartite graphs and split graphs. We also propose an algorithm that computes the optimal neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting of the central graphs of cycles and paths in polynomial time. [ABSTRACT FROM AUTHOR]

The deterministic permutation flow shop scheduling problem with makespan criterion is not solvable in polynomial time. Therefore, researchers have thought about heuristic algorithms. There are many heuristic algorithms for solving it that is a very important combinatorial optimization problem. In this paper, a new algorithm is proposed for solving the mentioned problem. The presented algorithm chooses the weighted path that starts from the up-left corner and reaches the down-right in the matrix of jobs processing times and calculates the biggest sum of the times in the footprints of this path. The row with the biggest sum permutes among all the rows of the matrix for locating the minimum of makespan. This method was run on Taillards standard benchmark and the solutions were compared with the optimum or the best ones as well as 14 famous heuristics. The validity and effectiveness of the algorithm are shown with tables and statistical evaluation. [ABSTRACT FROM AUTHOR]

System diagnosis is process of identifying faulty nodes in a system. An efficient diagnosis is crucial for a multiprocessor system. The BGM diagnosis model is a modification of the PMC diagnosis model, which is a test-based diagnosis. In this paper, we present a specific structure and propose an algorithm for diagnosing a node in a system under the BGM model. We also give a polynomial-time algorithm that a node in a hypercube-like network can be diagnosed correctly in three test rounds under the BGM diagnosis model. [ABSTRACT FROM AUTHOR]

This paper integrates, from a tactical perspective, berth allocation and quay-crane assignment, two important, closely related decisions in container terminal operations in a single model. To obtain optimal solutions, a branch-and-price algorithm is sought in this paper under the framework of Dantzig–Wolfe decomposition. The algorithm decomposes the original problem to a master problem that links all vessels competing for the shared resources of berths and quay cranes and multiple per-vessel pricing subproblems that can be solved efficiently in polynomial time. Specifically, in the stage of generating promising initial feasible columns, three heuristics are adopted; during the column-updating stage, the subgradient-based Lagrangian relaxation is introduced to tackle the possibly encountered degeneracy phenomenon; the branching strategy is implemented in the pricing subproblem rather than in the master problem as reported in the literature with the benefit of avoiding incurring new dual prices, simplifying the branching process; and both breadth- and depth-first searching policies are tested to select the next node to explore. With real-life data, extensive numerical experiments are conducted to select the best choice for each stage with the strengths and drawbacks of each choice provided. And then the superiority of the branch-and-price algorithm configured with the selected combination of strategies is verified by comparing it with both CPLEX, a general-purpose solver, and a set-partitioning model, a dedicated algorithm reported in the literature. In addition, the decomposition by vessels adopted in this paper is also verified numerically by comparing it with the decomposition by berths reported in the literature, and the performance of the algorithm for other problem settings has also been tested. In conclusion, the numerical experiments show that our method outperforms the commercial solver and state-of-the-art solution methods reported in the literature in terms of both solution quality and computational time. [ABSTRACT FROM AUTHOR]

The Restricted Subset Feedback Vertex Set problem (R-SFVS) takes a graph G = (V , E) , a terminal set T ⊆ V , and an integer k as the input. The task is to determine whether there exists a subset S ⊆ V ∖ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP -complete even when the input graph is restricted to split graphs. In this paper, we mainly show that R-SFVS in chordal and split graphs can be solved in O (1.1550 | V |) time and exponential space or in O (1.1605 | V |) time and polynomial space, significantly improving all previous results. As a by-product, we show that the Maximum Independent Set problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to Vertex Cover , we obtain an O ⁎ (1.2738 k) -time parameterized algorithm and a tight O (k 2) -kernel for R-SFVS in chordal and split graphs. [ABSTRACT FROM AUTHOR]

We study the generalized minimum Manhattan network (GMMN) problem: given a set P of pairs of points in the Euclidean plane R 2 , we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the L 1 metric (a so-called Manhattan path) for each pair in P . This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in P , and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach. [ABSTRACT FROM AUTHOR]

In this paper, we propose an improved Harris hawk optimizer (IHHO) to overcome the shortcomings of Harris hawk optimizer (HHO) that there is aimless search in the global search process. IHHO is different from HHO in that during the global search process, the position of the Harris hawks is not random but moves according to the position of the best several Harris hawks in the population. The advantage of the new global search process in the IHHO is that it effectively improves the quality of candidate solutions. We use the proposed algorithm to solve job-shop scheduling problem, which is an NP-hard problem and also a very challenging optimization problem, because it is difficult to find a reasonable candidate solution in polynomial time. Many researchers have tried various methods to solve it, but failed to get an effective result. Therefore, we use it to verify the performance of the proposed algorithm. The experimental results of IHHO are compared with those of improved genetic algorithm, differential evolution and HHO. It can be seen from the experimental results that IHHO has obvious advantages compared with the results of other comparison algorithms in terms of convergence accuracy, convergence speed, stability and running time. The experimental results of Wilcoxon's rank sum test also show that the IHHO is essentially different from other comparison algorithms, which shows that the optimization performance of the IHHO is meaningful. [ABSTRACT FROM AUTHOR]