共查询到20条相似文献,搜索用时 31 毫秒
1.
Let F(x,y) be a polynomial over a field K and m a nonnegative integer. We call a polynomial g over K an m-near solution of F(x,y) if there exists a c∈K such that F(x,g)=cxm, and the number c is called an m-value of F(x,y) corresponding to g. In particular, c can be 0. Hence, by viewing F(x,y)=0 as a polynomial equation over K[x] with variable y, every solution of the equation F(x,y)=0 in K[x] is also an m-near solution. We provide an algorithm that gives all m-near solutions of a given polynomial F(x,y) over K, and this algorithm is polynomial time reducible to solving one variable equations over K. We introduce approximate solutions to analyze the algorithm. We also give some interesting properties of approximate solutions. 相似文献
2.
A real x is called h-bounded computable , for some function h:N→N, if there is a computable sequence (xs) of rational numbers which converges to x such that, for any n∈N, at most h(n) non-overlapping pairs of its members are separated by a distance larger than 2-n. In this paper we discuss properties of h-bounded computable reals for various functions h. We will show a simple sufficient condition for a class of functions h such that the corresponding h-bounded computable reals form an algebraic field. A hierarchy theorem for h-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h-bounded computability for special functions h. 相似文献
3.
4.
The most natural and perhaps most frequently used method for testing membership of an individual tuple in a conjunctive query is based on searching trees of partial solutions, or search-trees. We investigate the question of evaluating conjunctive queries with a time-bound guarantee that is measured as a function of the size of the optimal search-tree. We provide an algorithm that, given a database D, a conjunctive query Q, and a tuple a, tests whether Q(a) holds in D in time bounded by a polynomial in (sn)logk(sn)loglogn and nr, where n is the size of the domain of the database, k is the number of bound variables of the conjunctive query, s is the size of the optimal search-tree, and r is the maximum arity of the relations. In many cases of interest, this bound is significantly smaller than the nO(k) bound provided by the naive search-tree method. Moreover, our algorithm has the advantage of guaranteeing the bound for any given conjunctive query. In particular, it guarantees the bound for queries that admit an equivalent form that is much easier to evaluate, even when finding such a form is an NP-hard task. Concrete examples include the conjunctive queries that can be non-trivially folded into a conjunctive query of bounded size or bounded treewidth. All our results translate to the context of constraint-satisfaction problems via the well-publicized correspondence between both frameworks. 相似文献
5.
We consider time-space tradeoffs for static data structure problems in the cell probe model with word size 1 (the bit probe model). In this model, the goal is to represent n-bit data with s=n+r bits such that queries (of a certain type) about the data can be answered by reading at most t bits of the representation. Ideally, we would like to keep both s and t small, but there are tradeoffs between the values of s and t that limit the possibilities of keeping both parameters small. 相似文献
6.
The most effective way to maximize the lifetime of a wireless sensor network (WSN) is to allocate initial energy to sensors such that they exhaust their energy at the same time. The lifetime of a WSN as well as an optimal initial energy allocation are determined by a network design. The main contribution of the paper is to show that the lifetime of a WSN can be maximized by an optimal network design. We represent the network lifetime as a function of the number m of annuli and show that m has significant impact on network lifetime. We prove that if the energy consumed by data transmission is proportional to dα+c, where d is the distance of data transmission and α and c are some constants, then for a circular area of interest with radius R, the optimal number of annuli that maximizes the network lifetime is m=R((α−1)/c)1/α for an arbitrary sensor density function. 相似文献
7.
We prove an explicit bound on the radius of a ball centered at the origin which is guaranteed to contain all bounded connected components of a semi-algebraic set S⊂Rk defined by a weak sign condition involving s polynomials in Z[X1,…,Xk] having degrees at most d, and whose coefficients have bitsizes at most τ. Our bound is an explicit function of s,d,k and τ, and does not contain any undetermined constants. We also prove a similar bound on the radius of a ball guaranteed to intersect every connected component of S (including the unbounded components). While asymptotic bounds of the form 2τdO(k) on these quantities were known before, some applications require bounds which are explicit and which hold for all values of s,d,k and τ. The bounds proved in this paper are of this nature. 相似文献
8.
9.
10.
11.
We consider a two-edge connected, undirected graph G=(V,E), with n nodes and m non-negatively real weighted edges, and a single source shortest paths tree (SPT) T of G rooted at an arbitrary node r. If an edge in T is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge , instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(mlog2n) time and O(m) space algorithm to find a best swap edge for every edge of T, thus improving for m=o(n2/log2n) the previously known O(n2) time and space complexity algorithm. 相似文献
12.
14.
Given a graph G, an integer k, and a demand set D={(s1,t1),…,(sl,tl)}, the k-Steiner Forest problem finds a forest in graph G to connect at least k demands in D such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n2/3logl). We give a simpler and faster approximation algorithm to this problem with performance ratio O(n2/3logk) via greedy approach, improving the previously best known ratio in the literature. 相似文献
15.
Taisuke Izumi Akinori Saitoh Toshimitsu Masuzawa 《Journal of Parallel and Distributed Computing》2007
The Δ-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Δ (Δ-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Δ-timed uniform consensus problem in presence of fc crash processes and ft timing-faulty processes, and propose a Δ-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Δ-timed uniform consensus when at least ft+1 correct processes exist in the system. If the system has less than ft+1 correct processes, the algorithm cannot solve the Δ-timed uniform consensus. However, as long as ft+1 processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ-timed uniform consensus algorithm tolerating up to ft timing-faulty processes requires that the system has at least ft+1 correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any Δ-timed uniform consensus algorithm tolerating up to ft timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than ft+1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness. 相似文献
16.
This paper concerns construction of additive stretched spanners with few edges for n-vertex graphs having a tree-decomposition into bags of diameter at most δ, i.e., the tree-length δ graphs. For such graphs we construct additive 2δ-spanners with O(δn+nlogn) edges, and additive 4δ-spanners with O(δn) edges. This provides new upper bounds for chordal graphs for which δ=1. We also show a lower bound, and prove that there are graphs of tree-length δ for which every multiplicative δ-spanner (and thus every additive (δ−1)-spanner) requires Ω(n1+1/Θ(δ)) edges. 相似文献
17.
18.
We present algorithmic lower bounds on the size sd of the largest independent sets of vertices in random d-regular graphs, for each fixed d≥3. For instance, for d=3 we prove that, for graphs on n vertices, sd≥0.43475n with probability approaching one as n tends to infinity. 相似文献
19.
We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lgn) memory for a list of size n, the i’th back-step from the farthest point reached so far takes O(lgi) time in the worst case, while the overhead per forward step is at most ? for arbitrary small constant ?>0. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: k vs. kn1/k and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n1/k-ary, tree that can only be traversed in a pre-order fashion. 相似文献