首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
Xiao-Shan Chen  Wen Li 《Calcolo》2008,45(2):99-109
In this paper, the variations of both subunitary polar factors and Hermitian positive semidefinite polar factors in the polar decomposition are studied. New perturbation bounds of both polar factors are given without the restriction that A and its perturbed matrix à have the same rank. These improve recent results.  相似文献   

2.
Given a graph with a source and a sink node, the NP-hard maximum k-splittable s,t-flow (M k SF) problem is to find a flow of maximum value from s to t with a flow decomposition using at most k paths. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values for the paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Usually the routing is considered before the packing. Our main contributions are as follows: (i) We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal M k SF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we can guarantee that, for any fixed ε>0, the computed set of alternatives contains a packing used by a (1−ε)-approximate solution. The latter result is based on the observation that (1−ε)-approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. (ii) Based on (i), we prove that, for constant k, the M k SF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it.  相似文献   

3.
The question of the contemporary relevance of Heidegger’s reflections on technology to today’s advanced technology is here explored with reference to the notion of “entanglement” towards a review of Heidegger’s understanding of technology and media, including the entertainment industry and modern digital life. Heidegger’s reflections on Gelassenheit have been connected with the aesthetics of the tea ceremony, disputing the material aesthetics of porcelain versus plastic. Here by approaching the art of wabi-sabi as the art of Verfallenheit, I argue that Gelassenheit may be understood in these terms.  相似文献   

4.
We propose a non-iterative solution to the PnP problem—the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences—whose computational complexity grows linearly with n. This is in contrast to state-of-the-art methods that are O(n 5) or even O(n 8), without being more accurate. Our method is applicable for all n≥4 and handles properly both planar and non-planar configurations. Our central idea is to express the n 3D points as a weighted sum of four virtual control points. The problem then reduces to estimating the coordinates of these control points in the camera referential, which can be done in O(n) time by expressing these coordinates as weighted sum of the eigenvectors of a 12×12 matrix and solving a small constant number of quadratic equations to pick the right weights. Furthermore, if maximal precision is required, the output of the closed-form solution can be used to initialize a Gauss-Newton scheme, which improves accuracy with negligible amount of additional time. The advantages of our method are demonstrated by thorough testing on both synthetic and real-data.  相似文献   

5.
The corepresentation of a Sylow p-subgroup of a symmetric group in the form of generating relations is investigated, and a Sylow subgroup of a group , i.e., an n-fold wreath product of regular cyclic groups of prime order, that is isomorphic to the group of automorphisms of a spherically homogeneous root tree is also studied. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 27–41, January–February 2009.  相似文献   

6.
The concept of intuitionistic fuzzy subhyperquasigroups in a hyperquasigroup with respect to an s-norm and a t-norm on intuitionistic fuzzy sets is introduced and their properties of such hyperquasigroups are studied. Intuitionistic (S, T)-fuzzy relations on a hyperquasigroup G are discussed. In particular, we investigate connections hyperquasigroups with binary quasigroups.  相似文献   

7.
A particular class of incomplete factorizations is proposed as preconditioners for the linear system Ax = b where A is a symmetric, large and sparse matrix. The ILDL T< (p) factorization (p = 1,2,3, …) determines the density of the lower triangular matrix L selecting the p largest off-diagonal entries of each column during the Gaussian elimination process. This selection may be computationally expensive, but the effectiveness of the preconditioner allows us to choose very low-density factors to reduce both work time and storage requirements. This incomplete factorization can be performed reliably on H-matrices. When A is a positive definite matrix, but not an H-matrix, one can perform an incomplete factorization if positive off-diagonal entries are removed or reduced and diagonally compensated. Numerical results for a variety of problems and comparisons with other incomplete factorizations are presented. Received: August 2002 / Accepted: December 2002 RID="*" ID="*"This work was supported by the Spanish grant BFM 2001-2641.  相似文献   

8.
In spite of significant improvements in video data retrieval, a system has not yet been developed that can adequately respond to a user’s query. Typically, the user has to refine the query many times and view query results until eventually the expected videos are retrieved from the database. The complexity of video data and questionable query structuring by the user aggravates the retrieval process. Most previous research in this area has focused on retrieval based on low-level features. Managing imprecise queries using semantic (high-level) content is no easier than queries based on low-level features due to the absence of a proper continuous distance function. We provide a method to help users search for clips and videos of interest in video databases. The video clips are classified as interesting and uninteresting based on user browsing. The attribute values of clips are classified by commonality, presence, and frequency within each of the two groups to be used in computing the relevance of each clip to the user’s query. In this paper, we provide an intelligent query structuring system, called I-Quest, to rank clips based on user browsing feedback, where a template generation from the set of interesting and uninteresting sets is impossible or yields poor results.
Ramazan Savaş Aygün (Corresponding author)Email:
  相似文献   

9.
We analyze the necessary existence conditions for (a, d)-distance antimagic labeling of a graph G = (V, E) of order n. We obtain theorems that expand the family of not (a, d) -distance antimagic graphs. In particular, we prove that the crown P n P 1 does not admit an (a, 1)-distance antimagic labeling for n ≥ 2 if a ≥ 2. We determine the values of a at which path P n can be an (a, 1)-distance antimagic graph. Among regular graphs, we investigate the case of a circulant graph.  相似文献   

10.
We consider a multiline queueing system with joint or single queries. The number of queries in a connection is random and is not known when the connection is established. Queries arriving during each connection are described by the phase type input steam. Accepting a connection in the system is restricted by tokens. Connections arriving when no free tokens are present are refused. Single queries arrive without tokens. If the number of free slots in the system is not enough, the system is blocked.  相似文献   

11.
This paper proposes a strengthening of the author’s core-accessibility theorem for balanced TU-cooperative games. The obtained strengthening relaxes the influence of the nontransitivity of classical domination αv on the quality of the sequential improvement of dominated imputations in a game v. More specifically, we establish the k-accessibility of the core C v ) of any balanced TU-cooperative game v for all natural numbers k: for each dominated imputation x, there exists a converging sequence of imputations x0, x1,..., such that x0 = x, lim x r C v ) and xr?m is dominated by any successive imputation x r with m ∈ [1, k] and rm. For showing that the TU-property is essential to provide the k-accessibility of the core, we give an example of an NTU-cooperative game G with a ”black hole” representing a nonempty closed subset B ? G(N) of dominated imputations that contains all the α G -monotonic sequential improvement trajectories originating at any point xB.  相似文献   

12.
Most modern database applications involve a significant amount of time dependent data and a significant portion of this data is now-relative. Now-relative data are a natural and meaningful part of every temporal database as well as being the focus of most queries. Previous studies indicate that the choice of the representation of now significantly influences the efficiency of accessing bitemporal data. In this paper we propose and experimentally evaluate a novel approach to represent now that we termed the POINT approach, in which now-relative facts are represented as points on the transaction-time and/or valid-time line. Furthermore, in the POINT approach we propose a logical query transformation that relies on the above representation and on the geometry features of spatial access methods. Such a logical query transformation enables off-the-shelf spatial indexes to be used. We empirically prove that the POINT approach is efficient on now-relative bitemporal data, outperforming the maximum timestamp approach that has been proven to the best approach to now-relative data in the literature, independently of the indexing methodology (B  + - tree vs R *- tree) being used. Specifically, if spatial indexing is used, the POINT approach outperforms the maximum timestamp approach to the extent of factor more than 10, both in number of disk accesses and CPU usage.  相似文献   

13.
Scheduling is one of the most successful application areas of constraint programming mainly thanks to special global constraints designed to model resource restrictions. Among these global constraints, edge-finding and not-first/not-last are the most popular filtering algorithms for unary resources. In this paper we introduce new O(n log n) versions of these two filtering algorithms and one more O(n log n) filtering algorithm called detectable precedences. These algorithms use a special data structures Θ-tree and Θ-Λ-tree. These data structures are especially designed for “what-if” reasoning about a set of activities so we also propose to use them for handling so called optional activities, i.e. activities which may or may not appear on the resource. In particular, we propose new O(n log n) variants of filtering algorithms which are able to handle optional activities: overload checking, detectable precedences and not-first/not-last.  相似文献   

14.
It is argued that F(R) modified gravity generically leads to high frequency curvature oscillations in astrophysical systems with rising mass/energy density. Potentially observational manifestations of such oscillations are discussed. In particular, gravitational repulsion in finite-size objects, forbidden in standard General Relativity, is shown to exist. Also an alternation of density perturbation evolution is found out. The latter is induced by excitation of a parametric resonance and by the so-called antifriction phenomenon. These new features could lead to strong reshaping of the usual Jeans instability.  相似文献   

15.
Recently, some authors considered the origin of a type-IV singular bounce in modified gravity and obtained the explicit form of F(R) which can produce this type of cosmology. In this paper, we show that during the contracting branch of type-IV bouncing cosmology, the sign of gravity changes, and antigravity emerges. In our model, M0 branes get together and shape a universe, an anti-universe, and a wormhole which connects them. As time passes, this wormhole is dissolved in the universes, F(R) gravity emerges, and the universe expands. When the brane universes become close to each other, the squared energy of their system becomes negative, and some tachyonic states are produced. To remove these states, universes are assumed to be compact, the sign of compacted gravity changes, and anti-F(R) gravity arises, which causes getting away of the universes from each other. In this theory, a Type-IV singularity occurs at t = t s , which is the time of producing tachyons between expansion and contraction branches.  相似文献   

16.
A variation of first order logic with variables for exponents is developed to solve some problems in the setting of rational languages on the free monoid, implying in particular algorithms for purity and p-purity. This same problem is addressed for the case of rational free group languages, and characterizations of the rational subsets of involved are also obtained.Received: 5 December 2002, Pedro V. Silva: http://www.fc.up.pt/cmup  相似文献   

17.
Ranking queries, also known as top-k queries, produce results that are ordered on some computed score. Typically, these queries involve joins, where users are usually interested only in the top-k join results. Top-k queries are dominant in many emerging applications, e.g., multimedia retrieval by content, Web databases, data mining, middlewares, and most information retrieval applications. Current relational query processors do not handle ranking queries efficiently, especially when joins are involved. In this paper, we address supporting top-k join queries in relational query processors. We introduce a new rank-join algorithm that makes use of the individual orders of its inputs to produce join results ordered on a user-specified scoring function. The idea is to rank the join results progressively during the join operation. We introduce two physical query operators based on variants of ripple join that implement the rank-join algorithm. The operators are nonblocking and can be integrated into pipelined execution plans. We also propose an efficient heuristic designed to optimize a top-k join query by choosing the best join order. We address several practical issues and optimization heuristics to integrate the new join operators in practical query processors. We implement the new operators inside a prototype database engine based on PREDATOR. The experimental evaluation of our approach compares recent algorithms for joining ranked inputs and shows superior performance.Received: 23 December 2003, Accepted: 31 March 2004, Published online: 12 August 2004Edited by: S. AbiteboulExtended version of the paper published in the Proceedings of the 29th International Conference on Very Large Databases, VLDB 2003, Berlin, Germany, pp 754-765  相似文献   

18.
19.
The theory of finite pseudo-random binary sequences was built by C. Mauduit and A. Sárközy and later extended to sequences of k symbols (or k-ary sequences). Certain constructions of pseudo-random sequences of k symbols were presented over finite fields in the literature. In this paper, two families of sequences of k symbols are constructed by using the integers modulo pq for distinct odd primes p and q. The upper bounds on the well-distribution measure and the correlation measure of the families sequences are presented in terms of certain character sums over modulo pq residue class rings. And low bounds on the linear complexity profile are also estimated.  相似文献   

20.
The single-server queuing system with finite buffer was considered. The customers may arrive one-by-one or in batches. Arrivals of single customers and their batches obey the Markov input processes. The customers from a batch taken for servicing come one at a time at the exponentially distributed time intervals. The numbers of customers in batches are distributed geometrically. The time of customer servicing has a phase-type distribution. The numbers of batches and single customers that may be simultaneously accepted by the system are controllable parameters. The joint distribution of the number of batches and the number of customers in system, loss probabilities, distribution of the time of batch sojourn, and problems of optimization were analyzed.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号