共查询到20条相似文献,搜索用时 427 毫秒
1.
We offer evidence in the disproof of the continuity of the length of minimum inner spanning trees with respect to a parameter
vector having a zero component. The continuity property is the key step of the proof of the conjecture in Du and Hwang (Proc.
Nat. Acad. Sci. U.S.A. 87:9464–9466, 1990; Algorithmica 7(1):121–135, 1992). Therefore the Steiner ratio conjecture proposed by Gilbert-Pollak (SIAM J. Appl. Math. 16(1):1–29, 1968) has not been proved yet. The Steiner ratio of a round sphere has been discussed in Rubinstein and Weng (J. Comb. Optim.
1:67–78, 1997) by assuming the validity of the conjecture on a Euclidean plane in Du and Hwang (Proc. Nat. Acad. Sci. U.S.A. 87:9464–9466,
1990; Algorithmica 7(1):121–135, 1992). Hence the results in Rubinstein and Weng (J. Comb. Optim. 1:67–78, 1997) have not been proved yet. 相似文献
2.
Tak-Wah Lam Lap-Kei Lee Isaac K. K. To Prudence W. H. Wong 《Journal of Scheduling》2012,15(1):105-116
Energy usage has been an important concern in recent research on online scheduling. In this paper, we study the tradeoff between
flow time and energy (Albers and Fujiwara in ACM Trans. Algorithms 3(4), 2007; Bansal et al. in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 805–813, 2007b, Bansal et al. in Proceedings of International Colloquium on Automata, Languages and Programming, pp. 409–420, 2008; Lam et al. in Proceedings of European Symposium on Algorithms, pp. 647–659, 2008b) in the multi-processor setting. Our main result is an enhanced analysis of a simple non-migratory online algorithm called
CRR (classified round robin) on m≥2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. The result
still holds even if the comparison is made against the optimal migratory offline algorithm. This improves previous analysis
that CRR is O(log P)-competitive where P is the ratio of the maximum job size to the minimum job size. 相似文献
3.
q-Families of CVD(MPFA) Schemes on General Elements: Numerical Convergence and the Maximum Principle
In this paper, families of flux-continuous, locally conservative, finite-volume schemes are presented for solving the general
geometry-permeability tensor pressure equation on structured and unstructured grids in two and three dimensions. The schemes
are applicable to the general tensor pressure equation with discontinuous coefficients and remove the O(1) errors introduced by standard reservoir simulation (two-point flux) schemes when applied to full anisotropic permeability
tensor flow approximation (Edwards and Rogers in Multigrids Methods, vol. 1, pp. 190–200, 1993; Edwards and Rogers in Proceedings: 4th European Conference on the Mathematics of Oil Recovery, 1994; Edwards and Rogers in Comput. Geom. 2:259–290, 1998). Full tensors arise when the local orientation of the grid is non-aligned with the principal axes of the tensor field. Full
tensors may also arise when fine scale permeability distributions are upscaled to obtain gridblock-scale permeability distributions.
In general full tensors arise when using any structured or unstructured grid type that departs from K-orthogonality. 相似文献
4.
Tofigh Allahviranloo M. Adabitabar Firozja 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2010,14(7):773-782
In this paper, a new approach for comparison among fuzzy numbers based on new metric distance (D
TM) is proposed. All reasonable properties of ranking function are proved. At first, the distance on the interval numbers based
on convex hall of endpoints is proposed. The existing distance measures for interval numbers, (Bardossy and Duckstein in
Fuzzy rule-based modeling with applications to geophysical, biological and engineering systems. CRC press, Boca Raton, 1995; Diamond in Info Sci 46:141–157, 1988; Diamond and Korner in Comput Math Appl 33:15–32, 1997; Tran and Duckstein in Fuzzy Set Syst 130:331–341, 2002; Diamond and Tanaka Fuzzy regression analysis. In: Slowinski R (ed) Fuzzy sets in decision analysis, operations research
and statistics. Kluwer, Boston, pp 349–387, 1998) do not satisfy the properties of a metric distance, while the proposed distance does. It is extended to fuzzy numbers and
its properties are proved in detail. Finally, we compare the proposed definition with some of the known ones. 相似文献
5.
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. 相似文献
6.
In this paper, we propose a unified primal-dual algorithm framework for two classes of problems that arise from various signal
and image processing applications. We also show the connections to existing methods, in particular Bregman iteration (Osher
et al., Multiscale Model. Simul. 4(2):460–489, 2005) based methods, such as linearized Bregman (Osher et al., Commun. Math. Sci. 8(1):93–111, 2010; Cai et al., SIAM J. Imag. Sci. 2(1):226–252, 2009, CAM Report 09-28, UCLA, March 2009; Yin, CAAM Report, Rice University, 2009) and split Bregman (Goldstein and Osher, SIAM J. Imag. Sci., 2, 2009). The convergence of the general algorithm framework is proved under mild assumptions. The applications to ℓ
1 basis pursuit, TV−L
2 minimization and matrix completion are demonstrated. Finally, the numerical examples show the algorithms proposed are easy
to implement, efficient, stable and flexible enough to cover a wide variety of applications. 相似文献
7.
In this paper, we study digital versions of some properties of covering spaces from algebraic topology. Among our results
are some that correct or improve upon the presentation of assertions in earlier papers (Boxer and Karaca in J. Math. Imaging
Vis. 32:23–29, 2008; Han in Inf. Sci. 177:3731–3748, 2007; Han in Inf. Sci. 178:550–561, 2008). 相似文献
8.
We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with n nodes into a disjoint set of connected clusters with radius at most k−1 and having O(n
1+1/k
) intercluster edges. We show how to implement our algorithms in the distributed
CONGEST\mathcal{CONGEST}
model of computation, i.e., limited message size, which improves the time complexity of previous algorithms (Moran and Snir
in Theor. Comput. Sci. 243(1–2):217–241, 2000; Awerbuch in J. ACM 32:804–823, 1985; Peleg in Distributed Computing: A Locality-Sensitive Approach, 2000) from O(n) to O(n
1−1/k
). We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic
time in the
CONGEST\mathcal{CONGEST}
model. 相似文献
9.
Harald Fecher Sharon Shoham 《International Journal on Software Tools for Technology Transfer (STTT)》2011,13(4):289-306
A key technique for the verification of programs is counterexample-guided abstraction–refinement (CEGAR). Grumberg et al.
(LNCS, vol 3385, pp. 233–249. Springer, Berlin, 2005; Inf Comput 205(8):1130–1148, 2007) developed a CEGAR-based algorithm for the modal μ-calculus. There, every abstract state is split in a refinement step. In this paper, the work of Grumberg et al. is generalized
by presenting a new CEGAR-based algorithm for the μ-calculus. It is based on a more expressive abstract model and applies refinement only locally (at a single abstract state),
i.e., the lazy abstraction technique for safety properties is adapted to the μ-calculus. Furthermore, it separates refinement determination from the (3-valued based) model checking. Three different heuristics
for refinement determination are presented and illustrated. 相似文献
10.
We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized
problems under the hypothesis P≠NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results
in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563–574, Springer, Berlin, 2008; Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), ACM, New York, pp. 133–142,
2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that
the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a “linear OR”
and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with |y|=k
O(1)⋅|x|1−ε
(here ε is any given real number greater than zero). We give various applications of these results. On the structural side we prove
several results clarifying the relationship between the different notions of preprocessing procedures, namely the various
notions of kernelizations, self-reductions and compressions. 相似文献
11.
In 2003, Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) published a paper describing an algorithm that computes the exact distance transform in linear time (with respect to image
size) for the rectangular binary images in the k-dimensional space ℝ
k
and distance measured with respect to L
p
-metric for 1≤p≤∞, which includes Euclidean distance L
2. In this paper we discuss this algorithm from theoretical and practical points of view. On the practical side, we concentrate
on its Euclidean distance version, discuss the possible ways of implementing it as signed distance transform, and experimentally
compare implemented algorithms. We also describe the parallelization of these algorithms and discuss the computational time
savings associated with them. All these implementations will be made available as a part of the CAVASS software system developed
and maintained in our group (Grevera et al. in J. Digit. Imaging 20:101–118, 2007). On the theoretical side, we prove that our version of the signed distance transform algorithm, GBDT, returns the exact value of the distance from the geometrically defined object boundary. We provide a complete proof (which was not given of Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270, 2003) that all these algorithms work correctly for L
p
-metric with 1<p<∞. We also point out that the precise form of the algorithm from Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265–270,
2003) is not well defined for L
1 and L
∞ metrics. In addition, we show that the algorithm can be used to find, in linear time, the exact value of the diameter of an object, that is, the largest possible distance between any two of its elements. 相似文献
12.
In this paper we consider the case of nonlinear convection-diffusion problems with a dominating convection term and we propose
exponential integrators based on the composition of exact pure convection flows. These methods can be applied to the numerical
integration of the considered PDEs in a semi-Lagrangian fashion. Semi-Lagrangian methods perform well on convection dominated
problems (Pironneau in Numer. Math. 38:309–332, 1982; Hockney and Eastwood in Computer simulations using particles. McGraw-Hill, New York, 1981; Rees and Morton in SIAM J. Sci. Stat. Comput. 12(3):547–572, 1991; Baines in Moving finite elements. Monographs on numerical analysis. Clarendon Press, Oxford, 1994).
In these methods linear convective terms can be integrated exactly by first computing the characteristics corresponding to the gridpoints of the adopted discretization, and then producing
the numerical approximation via an interpolation procedure. 相似文献
13.
Lavinia Corina Ciungu Anatolij Dvurečenskij Marek Hyčko 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2010,15(4):619-634
The concept of a state MV-algebra was firstly introduced by Flaminio and Montagna (An algebraic approach to states on MV-algebras.
In: Novák V (ed) Fuzzy logic 2, proceedings of the 5th EUSFLAT conference, September 11–14, Ostrava, vol II, pp 201–206, 2007; Int J Approx Reason 50:138–152, 2009) as an MV-algebra with internal state as a unary operation. Di Nola and Dvurečenskij (Ann Pure Appl Logic 161:161–173, 2009a; Math Slovaca 59:517–534, 2009b) gave a stronger version of a state MV-algebra. In the present paper, we introduce the notion of a state BL-algebra, or more
precisely, a BL-algebra with internal state. We present different types of state BL-algebras, like strong state BL-algebras
and state-morphism BL-algebras, and we study some classes of state BL-algebras. In addition, we give a sample of important
examples of state BL-algebras and present some open problems. 相似文献
14.
Mark S. Hickman 《Journal of Mathematical Imaging and Vision》2012,43(3):206-213
It is well known that two planar curves that are related by a Euclidean transformation possess the same signature curve. Recently
Musso and Nicolodi (J. Math. Imaging Vis. 35:68–85, 2009) gave examples of non-congruent curves that possess the same Euclidean signature curve. In this paper we show how to construct all planar curves of class C
3 that have a given signature curve. 相似文献
15.
S. Vologiannidis E. N. Antoniou 《Mathematics of Control, Signals, and Systems (MCSS)》2011,22(4):317-342
In Antoniou and Vologiannidis (Electron J Linear Algebra 11:78–87, 2004; 15:107–114, 2006), a new family of companion forms associated with a regular polynomial matrix T (s) has been presented, using products of permutations of n elementary matrices, generalizing similar results presented in Fiedler (Linear Algebra Its Appl 371:325–331, 2003) where the scalar case was considered. In this paper, extending this “permuted factors” approach, we present a broader family
of companion-like linearizations, using products of up to n(n−1)/2 elementary matrices, where n is the degree of the polynomial matrix. Under given conditions, the proposed linearizations can be shown to consist of block
entries where the coefficients of the polynomial matrix appear intact. Additionally, we provide a criterion for those linearizations
to be block symmetric. We also illustrate several new block symmetric linearizations of the original polynomial matrix T (s), where in some of them the constraint of nonsingularity of the constant term and the coefficient of maximum degree are not
a prerequisite. 相似文献
16.
Predicting air damping is crucial in the design of high Q microelectromechanical systems. In the past, air damping of rigid microbeam in free space at molecular regime is usually
estimated using the free molecular model proposed by Christian (Vacuum 16:175–178, 1966), air damping of flexible microbeam is estimated using the model proposed by Blom (J Vac Sci Technol B 10:19–26, 1992). The relation between the two models is Q
Blom = 3Q
Christian. In this paper, a general proof is presented that shows the Christian’s model is valid for the air damping of flexible microbeam
in free space at molecular regime. By comparing with the experimental results available in the literatures (Blom et al. in
J Vac Sci Technol B 10:19–26, 1992; Yasumura et al. in J Micromech Syst 9:117–125, 2000), we conclude that the Christian’s model is the best choice in predicting the air damping of flexible microbeam in free space
at the molecular regime. 相似文献
17.
We present a posteriori-residual analysis for the approximate time-dependent Stokes model Chorin-Temam projection scheme (Chorin
in Math. Comput. 23:341–353, 1969; Temam in Arch. Ration. Mech. Appl. 33:377–385, 1969). Based on the multi-step approach introduced in Bergam et al. (Math. Comput. 74(251):1117–1138, 2004), we derive error estimators, with respect to both time and space approximations, related to diffusive and incompressible
parts of Stokes equations. Using a conforming finite element discretization, we prove the equivalence between error and estimators
under specific conditions. 相似文献
18.
Katarína Čunderlíková 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2010,14(3):229-234
The ergodic theory and particularly the individual ergodic theorem were studied in many structures. Recently the individual
ergodic theorem has been proved for MV-algebras of fuzzy sets (Riečan in Czech Math J 50(125):673–680, 2000; Riečan and Neubrunn in Integral, measure, and ordering. Kluwer, Dordrecht, 1997) and even in general MV-algebras (Jurečková in Int J Theor Phys 39:757–764, 2000). The notion of almost everywhere equality of observables was introduced by Riečan and Jurečková (Int J Theor Phys 44:1587–1597,
2005). They proved that the limit of Cesaro means is an invariant observable for P-observables. In Lendelová (Int J Theor Phys 45(5):915–923, 2006c) showed that the assumption of P-observable can be omitted. In this paper we prove the individual ergodic theorem on family of IF-events and show that each
P {\mathcal{P}} -preserving transformation in this family can be expressed by two corresponding
P\flat,P\sharp {\mathcal{P}}^\flat,{\mathcal{P}}^\sharp -preserving transformations in tribe T. {\mathcal{T}}. 相似文献
19.
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. 相似文献
20.
Jussi Jylkkä 《Minds and Machines》2011,21(1):41-56
It has been argued that prototypes cannot compose, and that for this reason concepts cannot be prototypes (Osherson and Smith
in Cognition 9:35–58, 1981; Fodor and Lepore in Cognition 58:253–270, 1996; Connolly et al. in Cognition 103:1–22, 2007). In this paper I examine the intensional and extensional approaches to prototype compositionality, arguing that neither
succeeds in their present formulations. I then propose a hybrid extensional theory of prototype compositionality, according
to which the extension of a complex concept is determined as a function of what triggers its constituent prototypes. I argue
that the theory escapes the problems traditionally raised against extensional theories of compositionality. 相似文献