共查询到20条相似文献,搜索用时 46 毫秒
1.
We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobás, and Sorkin (J. Comb. Theory Ser. B 92(2):199–233,
2004) and by Aigner and van der Holst (Linear Algebra Appl., 2004). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle, Electron. J. Comb. 15(1), 2008) employs a general logical framework and leads to an algorithm with running time f(k)⋅n, where f(k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm
uses 23k2+O(k)·n2^{3k^{2}+O(k)}\cdot n arithmetic operations and can be efficiently implemented in parallel. 相似文献
2.
Comparison theorems between the spectral radii of different matrices are a useful tool for judging the efficiency of preconditioners.
For single splittings of different monotone matrices, Elsner et al. (Linear Algebra Appl. 363:65–80, 2003) gave out comparison theorems for spectral radii. For double splittings, some convergence and comparison theorems of a monotone
matrix are presented by Shen et al. (Comput. Math. Appl. 51:1751–1760, 2006). In this note we give the comparison theorem for the spectral radii of matrices arising from double splittings of different
monotone matrices. 相似文献
3.
A class of spaces of matrices, calledh-spaces, is considered, extending previous results in [R. Bevilacqua, P. Zellini,Closure, commutativity and minmal complexity of some space of matrices, Linear and Multilinear Algebra,25, (1989) 1–25]. These spaces include several known classes of matrix algebras, such as group matrix algebras and Hessenberg
algebras and, in particular, certain symmetric closed 1-spaces, which are structurally related to Toeplitz plus Hankel-like
matrices. Following the displacement rank technique, these spaces are involved in general displacement decomposition formulas
of an arbitrary matrixA. These decompositions lead to a significant representation formula for the inverse of a centrosymmetric Toeplitz plus Hankel
matrix. 相似文献
4.
Ilias Diakonikolas Homin K. Lee Kevin Matulef Rocco A. Servedio Andrew Wan 《Algorithmica》2011,61(3):580-605
We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function f:{0,1}
n
→{−1,1} is an s-sparse GF(2) polynomial versus ε-far from every such polynomial. Our algorithm makes poly(s,1/ε) black-box queries to f and runs in time n⋅poly(s,1/ε). The only previous algorithm for this testing problem (Diakonikolas et al. in Proceedings of the 48th Annual Symposium on
Foundations of Computer Science, FOCS, pp. 549–558, 2007) used poly(s,1/ε) queries, but had running time exponential in s and super-polynomial in 1/ε. 相似文献
5.
The standard way of solving numerically a polynomial eigenvalue problem (PEP) is to use a linearization and solve the corresponding generalized eigenvalue problem (GEP). In addition, if the PEP possesses one of the structures arising very often in applications, then the use of a linearization that preserves such structure combined with a structured algorithm for the GEP presents considerable numerical advantages. Block-symmetric linearizations have proven to be very useful for constructing structured linearizations of structured matrix polynomials. In this scenario, we analyze the eigenvalue condition numbers and backward errors of approximated eigenpairs of a block symmetric linearization that was introduced by Fiedler (Linear Algebra Appl 372:325–331, 2003) for scalar polynomials and generalized to matrix polynomials by Antoniou and Vologiannidis (Electron J Linear Algebra 11:78–87, 2004). This analysis reveals that such linearization has much better numerical properties than any other block-symmetric linearization analyzed so far in the literature, including those in the well known vector space \(\mathbb {DL}(P)\) of block-symmetric linearizations. The main drawback of the analyzed linearization is that it can be constructed only for matrix polynomials of odd degree, but we believe that it will be possible to extend its use to even degree polynomials via some strategies in the near future. 相似文献
6.
Timothy M. Chan 《Algorithmica》2008,50(2):236-243
We describe an O(n
3/log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (SIAM J. Comput. 5:49–60,
1976), Takaoka (Inform. Process. Lett. 43:195–199, 1992), Dobosiewicz (Int. J. Comput. Math. 32:49–60, 1990), Han (Inform. Process. Lett. 91:245–250, 2004), Takaoka (Proc. 10th Int. Conf. Comput. Comb., Lect. Notes Comput. Sci., vol. 3106, pp. 278–289, Springer, 2004), and Zwick (Proc. 15th Int. Sympos. Algorithms and Computation, Lect. Notes Comput. Sci., vol. 3341, pp. 921–932, Springer,
2004). The new algorithm is surprisingly simple and different from previous ones.
A preliminary version of this paper appeared in Proc. 9th Workshop Algorithms Data Struct. (WADS), Lect. Notes Comput. Sci.,
vol. 3608, pp. 318–324, Springer, 2005. 相似文献
7.
Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics
86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block
is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n
5) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n
11) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block
is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case.
Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong. 相似文献
8.
In this paper we introduce a minimax model unifying several classes of single facility planar center location problems. We
assume that the transportation costs of the demand points to the serving facility are convex functions {Q
i
}, i=1,…,n, of the planar distance used. Moreover, these functions, when properly transformed, give rise to piecewise quadratic functions
of the coordinates of the facility location. In the continuous case, using results on LP-type models by Clarkson (J. ACM 42:488–499,
1995), Matoušek et al. (Algorithmica 16:498–516, 1996), and the derandomization technique in Chazelle and Matoušek (J. Algorithms 21:579–597, 1996), we claim that the model is solvable deterministically in linear time. We also show that in the separable case, one can
get a direct O(nlog n) deterministic algorithm, based on Dyer (Proceedings of the 8th ACM Symposium on Computational Geometry, 1992), to find an optimal solution. In the discrete case, where the location of the center (server) is restricted to some prespecified
finite set, we introduce deterministic subquadratic algorithms based on the general parametric approach of Megiddo (J. ACM
30:852–865, 1983), and on properties of upper envelopes of collections of quadratic arcs. We apply our methods to solve and improve the complexity
of a number of other location problems in the literature, and solve some new models in linear or subquadratic time complexity. 相似文献
9.
Consider the robust network design problem of finding a minimum cost network with enough capacity to route all traffic demand
matrices in a given polytope. We investigate the impact of different routing models in this robust setting: in particular,
we compare oblivious routing, where the routing between each terminal pair must be fixed in advance, to dynamic routing, where routings may depend arbitrarily on the current demand. Our main result is a construction that shows that the
optimal cost of such a network based on oblivious routing (fractional or integral) may be a factor of Ω(log n) more than the cost required when using dynamic routing. This is true even in the important special case of the asymmetric
hose model. This answers a question in (Chekuri, SIGACT News 38(3):106–128, 2007), and is tight up to constant factors. Our proof technique builds on a connection between expander graphs and robust design
for single-sink traffic patterns (Chekuri et al., Networks 50(1):50–54, 2007). 相似文献
10.
We present a deterministic Logspace procedure, which, given a bipartite planar graph on n vertices, assigns O(log n) bits long weights to its edges so that the minimum weight perfect matching in the graph becomes unique. The Isolation Lemma as described in Mulmuley et al. (Combinatorica 7(1):105–131, 1987) achieves the same for general graphs using randomness, whereas we can do it deterministically when restricted to bipartite
planar graphs. As a consequence, we reduce both decision and construction versions of the perfect matching problem in bipartite
planar graphs to testing whether a matrix is singular, under the promise that its determinant is 0 or 1, thus obtaining a
highly parallel
SPL\mathsf{SPL}
algorithm for both decision and construction versions of the bipartite perfect matching problem. This improves the earlier
known bounds of non-uniform
SPL\mathsf{SPL}
by Allender et al. (J. Comput. Syst. Sci. 59(2):164–181, 1999) and
NC\mathsf{NC}
2 by Miller and Naor (SIAM J. Comput. 24:1002–1017, 1995), and by Mahajan and Varadarajan (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp.
351–357, 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite
planar graphs, which has been open for a long time. Further we try to find the lower bound on the number of bits needed for
deterministically isolating a perfect matching. We show that our particular method for isolation will require Ω(log n) bits. Our techniques are elementary. 相似文献
11.
This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed
k-TSP problem: given an asymmetric metric (V,d), a root r∈V and a target k≤|V|, compute the minimum length tour that contains r and at least k other vertices. We present a polynomial time
O(\fraclog2 nloglogn·logk)O(\frac{\log^{2} n}{\log\log n}\cdot\log k)-approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an
O(\fraclog2 nloglogn)O(\frac{\log^{2} n}{\log\log n})-approximation algorithm for the directed orienteering problem. This answers positively, the question of poly-logarithmic approximability of directed orienteering, an open problem
from Blum et al. (SIAM J. Comput. 37(2):653–670, 2007). The previously best known results were quasi-polynomial time algorithms with approximation guarantees of O(log 2
k) for directed k-TSP, and O(log n) for directed orienteering (Chekuri and Pal in IEEE Symposium on Foundations in Computer Science, pp. 245–253, 2005). Using the algorithm for directed orienteering within the framework of Blum et al. (SIAM J. Comput. 37(2):653–670, 2007) and Bansal et al. (ACM Symposium on Theory of Computing, pp. 166–174, 2004), we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSP and vehicle
routing problem with time-windows. 相似文献
12.
The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem
are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian
path problem. Motivated by the work of Uehara and Uno (Proc. of the 15th Annual International Symp. on Algorithms and Computation
(ISAAC), LNCS, vol. 3341, pp. 871–883, 2004), where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem
can be solved in polynomial time on interval graphs. The proposed algorithm uses a dynamic programming approach and runs in
O(n
4) time, where n is the number of vertices of the input graph. 相似文献
13.
Modeling the dependence of credit ratings is an important issue for portfolio credit risk analysis. Multivariate Markov chain
models are a feasible mathematical tool for modeling the dependence of credit ratings. Here we develop a flexible multivariate
Markov chain model for modeling the dependence of credit ratings. The proposed model provides a parsimonious way to capture
both the cross-sectional and temporal associations among ratings of individual entities. The number of model parameters is
of the magnitude O(sm
2 + s
2
m), where m is the number of ratings categories and s is the number of entities in a credit portfolio. The proposed model is also easy to implement. The estimation method is formulated
as a set of s linear programming problems and the estimation algorithm can be implemented easily in a Microsoft EXCEL worksheet, see Ching
et al. Int J Math Educ Sci Eng 35:921–932 (2004). We illustrate the practical implementation of the proposed model using real ratings data. We evaluate risk measures, such
as Value at Risk and Expected Shortfall, for a credit portfolio using the proposed model and compare the risk measures with
those arising from Ching et al. IMRPreprintSeries (2007), Siu et al. Quant Finance 5:543–556 (2005). 相似文献
14.
The class of alternating group networks was introduced in the late 1990’s as an alternative to the alternating group graphs
as interconnection networks. Recently, additional properties for the alternating group networks have been published. In particular,
Zhou et al., J. Supercomput (2009), doi:, was published very recently in this journal. We show that this so-called new interconnection topology is in fact isomorphic
to the (n,n−2)-star, a member of the well-known (n,k)-stars, 1≤k≤n−1, a class of popular networks proposed earlier for which a large amount of work have already been done. Specifically, the
problem in Zhou et al., J. Supercomput (2009), doi:, was addressed in Lin and Duh, Inf. Sci. 178(3), 788–801, 2008, when k = n−2. 相似文献
15.
We study the on-line minimum weighted bipartite matching problem in arbitrary metric spaces. Here, n not necessary disjoint points of a metric space M are given, and are to be matched on-line with n points of M revealed one by one. The cost of a matching is the sum of the distances of the matched points, and the goal is to find or
approximate its minimum. The competitive ratio of the deterministic problem is known to be Θ(n), see (Kalyanasundaram, B., Pruhs, K. in J. Algorithms 14(3):478–488, 1993) and (Khuller, S., et al. in Theor. Comput. Sci. 127(2):255–267, 1994). It was conjectured in (Kalyanasundaram, B., Pruhs, K. in Lecture Notes in Computer Science, vol. 1442, pp. 268–280, 1998) that a randomized algorithm may perform better against an oblivious adversary, namely with an expected competitive ratio
Θ(log n). We prove a slightly weaker result by showing a o(log 3
n) upper bound on the expected competitive ratio. As an application the same upper bound holds for the notoriously hard fire
station problem, where M is the real line, see (Fuchs, B., et al. in Electonic Notes in Discrete Mathematics, vol. 13, 2003) and (Koutsoupias, E., Nanavati, A. in Lecture Notes in Computer Science, vol. 2909, pp. 179–191, 2004).
The authors were partially supported by OTKA grants T034475 and T049398. 相似文献
16.
We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of $O(\sqrt{\log n}\log\log n)We design approximation algorithms for the vertex ordering problems Minimum Linear Arrangement, Minimum Containing Interval Graph, and Minimum Storage-Time Product, achieving approximation factors of
O(?{logn}loglogn)O(\sqrt{\log n}\log\log n)
,
O(?{logn}loglogn)O(\sqrt{\log n}\log\log n)
, and
O(?{logT}loglogT)O(\sqrt{\log T}\log\log T)
, respectively, the last running in time polynomial in T (T being the sum of execution times). The technical contribution of our paper is to introduce “ℓ
22 spreading metrics” (that can be computed by semidefinite programming) as relaxations for both undirected and directed “permutation
metrics,” which are induced by permutations of {1,2,…,n}. The techniques introduced in the recent work of Arora, Rao and Vazirani (Proc. of 36th STOC, pp. 222–231, 2004) can be adapted to exploit the geometry of such ℓ
22 spreading metrics, giving a powerful tool for the design of divide-and-conquer algorithms. In addition to their applications
to approximation algorithms, the study of such ℓ
22 spreading metrics as relaxations of permutation metrics is interesting in its own right. We show how our results imply that,
in a certain sense we make precise, ℓ
22 spreading metrics approximate permutation metrics on n points to a factor of
O(?{logn}loglogn)O(\sqrt{\log n}\log\log n)
. 相似文献
17.
Hans L. Bodlaender Fedor V. Fomin Arie M. C. A. Koster Dieter Kratsch Dimitrios M. Thilikos 《Theory of Computing Systems》2012,50(3):420-432
In this note, we give a proof that several vertex ordering problems can be solved in O
∗(2
n
) time and O
∗(2
n
) space, or in O
∗(4
n
) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply. 相似文献
18.
J. H. Reif 《Algorithmica》2001,29(3):487-510
{This paper is concerned with the problem of computing the characteristic polynomial of a matrix. In a large number of applications,
the matrices are symmetric and sparse : with O(n) non-zero entries. The problem has an efficient sequential solution in this case, requiring O(n
2
) work by use of the sparse Lanczos method. A major remaining open question is: to find a polylog time parallel algorithm with matching work bounds. Unfortunately, the sparse Lanczos method cannot be parallelized to faster than time Ω (n) using n processors. Let M(n) be the processor bound to multiply two n \times n matrices in O(log n) parallel time. Giesbrecht [G2] gave the best previous polylog time parallel algorithms for the characteristic polynomial
of a dense matrix with O (M(n)) processors. There is no known improvement to this processor bound in the case where the matrix is sparse. Often, in addition
to being symmetric and sparse, the matrix has a sparsity graph (which has edges between indices of the matrix with non-zero
entries) that has small separators. This paper gives a new algorithm for computing the characteristic polynomial of a sparse
symmetric matrix, assuming that the sparsity graph is s(n) -separable and has a separator of size s(n)=O(n
γ
) , for some γ , 0 < γ < 1 , that when deleted results in connected components of ≤α n vertices, for some 0 < α < 1 , with the same property. We derive an interesting algebraic version of Nested Dissection, which constructs a sparse factorization of the matrix A-λ I
n
where A is the input matrix and I
n
is the n \times n identity matrix. While Nested Dissection is commonly used to minimize the fill-in in the solution of sparse linear systems,
our innovation is to use the separator structure to bound also the work for manipulation of rational functions in the recursively
factored matrices. The matrix elements are assumed to be over an arbitrary field. We compute the characteristic polynomial of a sparse symmetric
matrix in polylog time using P(n)(n+M(s(n)))
≤ P(n)(n+ s(n)
2.376
) processors, where P(n) is the processor bound to multiply two degree n polynomials in O(log n) parallel time using a PRAM (P(n) = O(n) if the field supports an FFT of size n but is otherwise O(nlog log n) [CK]. Our method requires only that a matrix be symmetric and non-singular (it need not be positive definite as usual for
Nested Dissection techniques). For the frequently occurring case where the matrix has small separator size, our polylog parallel
algorithm has work bounds competitive with the best known sequential algorithms (i.e., the Ω(n
2
) work of sparse Lanczos methods), for example, when the sparsity graph is a planar graph, s(n) ≤ O( \sqrt n ) , and we require polylog time with only P(n)n
1.188
processors.
}
Received September 26, 1997; revised June 5, 1999. 相似文献
19.
L. B. Avgul' 《Cybernetics and Systems Analysis》1996,32(6):794-803
Conclusion The proposed method for polynomial expansion of SBF based on construction of the triangular tableT
n(π(F)) of local codes of its derivatives has the lowest computational complexity among known methods. Constructing the table only
once, the method easily determines all the “residual” functions ϑ
rl
km
for various expansion parametersk andm.
Another advantage of the method is its applicability for polynomial expansion of arbitrary BF and partially symmetric BF.
In this case, the base of the “triangle” is the truth table of the arbitrary BF or the local code (including convolved local
code) of the partially symmetric BF.
The method can be successfully used for the synthesis of a wide class of digital networks.
Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 59–71, November–December, 1996. 相似文献
20.
Alexander N. Rybalov 《Theory of Computing Systems》2010,46(1):2-8
Fischer and Rabin proved in (Proceedings of the SIAM-AMS Symposium in Applied Mathematics, vol. 7, pp. 27–41, 1974) that the decision problem for Presburger Arithmetic has at least double exponential worst-case complexity (for deterministic
and for nondeterministic Turing machines). In Kapovich et al. (J. Algebra 264(2):665–694, 2003) a theory of generic-case complexity was developed, where algorithmic problems are studied on “most” inputs instead of set
of all inputs. A question rises about existing of more efficient (say, polynomial) generic algorithm deciding Presburger Arithmetic
on a set of closed formulas of asymptotic density 1. We prove in this paper that there is not an exponential generic decision
algorithm working correctly on an input set of asymptotic density exponentially converging to 1 (so-called strongly generic
sets). 相似文献