We improve the approximation ratio for the Asymmetric TSP to less than 15. We also obtain improved ratios for the special case of unweighted digraphs and the generalization where we ask for a minimum-cost tour with given (distinct) endpoints. Moreover, we prove better upper bounds on the integrality ratios of the natural LP relaxations.
Since AVL trees were invented in 1962, two major open questions about rebalancing operations, which found positive answers in other balanced binary search trees, were left open: can these operations be performed top-down (with a fixed look-ahead), and can they use an amortised constant number of write operations per update? We propose an algorithm that answers both questions positively.
Antioxidants remove free radicals and inhibit the oxidation of oxygen-sensitive substances, which are of great significance in disease prevention and food preservative. Therefore, it is of great significance to establish a convenient, efficient and universal method for screening and evaluating antioxidant activity. In this study, Nitrogen-doped Graphene (N-G) with high conductivity and Chitosan (CS) with good film forming and stability were used as electrode substrate materials. And a ds-DNA/N-G@CS/GCE electrochemical biosensor for rapid evaluation of antioxidant activity was constructed by assembling ds-DNA and taking advantage of the signal difference between pre- and post-damage ds-DNA loading in Ru(NH3)6 3+ probe solution. N-G@CS with good electro-catalysis and high capacitance significantly improved the response signal of the sensor. At the same time, Square Wave Voltammetry (SWV) was used to optimize the conditions affecting the evaluation results of biosensors. The results showed that under the Fenton solution system with pH 7.0 and the ratio of Fe2+ to OH− 1:4, the biosensor has a high oxidation ds-DNA damage within 30 min The system can inhibit the damage of ds-DNA by adding antioxidants. Under optimized experimental conditions, composite yogurt and plain yogurt with weak antioxidant activity difference were evaluated by the constructed biosensor, and compared with L-ascorbic acid, the activity order was L-ascorbic acid > composite yogurt > plain yogurt. The results were consistent with the results of hydroxyl radical scavenging and ABTS+ radical scavenging experiments, and there was no significant difference between the three methods. This study not only provides a convenient and efficient method for the evaluation of antioxidant activity, but also provides strategies and technical support for the development of low-cost, highly sensitive and universal portable activity evaluation techniques.
The first worst-case linear-time algorithm for selection was discovered in 1973; however, linear-time binary heap construction was first published in 1964. Here we describe another worst-case linear selection algorithm,which is simply implemented and uses binary heap construction as its principal engine. The algorithm is implemented in place, and shown to perform similarly to in-place median of medians.
Sylvia Boyd, Joseph Cheriyan, Arash Haddadan
et al.
We present a $2$-approximation algorithm for the Flexible Graph Connectivity problem [AHM20] via a reduction to the minimum cost $r$-out $2$-arborescence problem.
A new run length encoding algorithm for lossless data compression that exploits positional redundancy by representing data in a two-dimensional model of concentric circles is presented. This visual transform enables detection of runs (each of a different character) in which runs need not be contiguous and hence, is a generalization of run length encoding. Its advantages and drawbacks are characterized by comparing its performance with TurboRLE.
We show how a collection of Euler-tour trees for a forest on $n$ vertices can be stored in $2 n + o (n)$ bits such that simple queries take constant time, more complex queries take logarithmic time and updates take polylogarithmic amortized time.
For online matching with the line metric, we present a lower bound of $Ω(\log n)$ on the approximation ratio of any online (possibly randomized) algorithm. This beats the previous best lower bound of $Ω(\sqrt{\log n})$ and matches the known upper bound of $O(\log n)$.
We initiate the study of sorting permutations using prefix block-interchanges, which exchange any prefix of a permutation with another non-intersecting interval. The goal is to transform a given permutation into the identity permutation using as few such operations as possible. We give a 2-approximation algorithm for this problem, show how to obtain improved lower and upper bounds on the corresponding distance, and determine the largest possible value for that distance.
In the Connected Dominating Set problem we are given a graph $G=(V,E)$ and seek a minimum size dominating set $S \subseteq V$ such that the subgraph $G[S]$ of $G$ induced by $S$ is connected. In the $2$-Edge-Connected Dominating Set problem $G[S]$ should be $2$-edge-connected. We give the first non-trivial approximation algorithm for this problem, with expected approximation ratio $\tilde{O}(\log^2n)$.
In the Cluster Deletion problem the input is a graph $G$ and an integer $k$, and the goal is to decide whether there is a set of at most $k$ edges whose removal from $G$ results a graph in which every connected component is a clique. In this paper we give an algorithm for Cluster Deletion whose running time is $O^*(1.404^k)$.
This paper is devoted to the complexity of the quantified boolean formula problem. We describe a simple deterministic algorithm that, for a given quantified boolean formula $F$, stops in time bounded by $O(|F|^4)$ and answers yes if $F$ is true and no otherwise.
Achieving the goals in the title (and others) relies on a cardinality-wise scanning of the ideals of the poset. Specifically, the relevant numbers attached to the k+1 element ideals are inferred from the corresponding numbers of the k-element (order) ideals. Crucial in all of this is a compressed representation (using wildcards) of the ideal lattice. The whole scheme invites distributed computation.
In this paper, we introduce a so-called Multistage graph Simple Path (MSP) problem and show that the Hamilton Circuit (HC) problem can be polynomially reducible to the MSP problem. To solve the MSP problem, we propose a polynomial algorithm and prove its NP-completeness. Our result implies NP=P.
The problem of finding a longest common subsequence of two main sequences with some constraint that must be a substring of the result (STR-IC-LCS) was formulated recently. It is a variant of the constrained longest common subsequence problem. As the known algorithms for the STR-IC-LCS problem are cubic-time, the presented quadratic-time algorithm is significantly faster.
This entry for the SIGSPATIAL Special July 2010 issue on Similarity Searching in Metric Spaces discusses the notion of intrinsic dimensionality of data in the context of similarity search.
We study policy iteration for infinite-horizon Markov decision processes. It has recently been shown policy iteration style algorithms have exponential lower bounds in a two player game setting. We extend these lower bounds to Markov decision processes with the total reward and average-reward optimality criteria.
We consider a somehow peculiar Token/Bucket problem which at first sight looks confusing and difficult to solve. The winning approach to solve the problem consists in going back to the simple and traditional methods to solve computer science problems like the one taught to us by Knuth. Somehow the main trick is to be able to specify clearly what needs to be achieved, and then the solution, even if complex, appears almost by itself.
Let X[0..n-1] and Y[0..m-1] be two sorted arrays, and define the mxn matrix A by A[j][i]=X[i]+Y[j]. Frederickson and Johnson gave an efficient algorithm for selecting the k-th smallest element from A. We show how to make this algorithm IO-efficient. Our cache-oblivious algorithm performs O((m+n)/B) IOs, where B is the block size of memory transfers.