共查询到20条相似文献,搜索用时 529 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
Deok Gyu Lee Jong Hyuk Park Tai-Hoon Kim Laurence T. Yang 《The Journal of supercomputing》2008,45(1):88-104
In the last few years, intelligent secured multimedia services play a vital role along with ubiquitous home environment (Park
et al. in Lecture Notes in Computer Science, vol. 4097, pp. 660–670, [2006]; Lecture Notes in Computer Science, vol. 4159, pp. 893–901, [2006]; IEICE Trans. Inf. Syst. E89-D(12):2831–2837, [2006]; Lecture Notes in Artificial Intelligence, vol. 4252, pp. 777–784, [2006]; Lecture Notes in Artificial Intelligence, vol. 3801, pp. 313–320, [2005]). There are certain constrains and limitations in providing effective and efficient services in U-home. The mechanism and
applications are integrated to realize such services. Three different kinds of ubiquitous multimedia services are proposed
in the framework. Based on the temporal and spatial context information, the surrounding situations are recognized. The contexts
are collected and well analyzed with the preconditions to provide the final services. The proposed framework provides efficient
services in the multimedia based deices based on the current context information.
相似文献
Laurence T. YangEmail: |
4.
Huaming Zhang 《Algorithmica》2010,57(2):381-397
We study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik, Freie Universität Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph with n vertices in a grid of size bounded by W×H, where $W\leq\lfloor\frac{2n-2}{3}\rfloorWe study the problem of transforming plane triangulations into irreducible triangulations, which are plane graphs with a quadrangular
exterior face, triangular interior faces and no separating triangles. Our linear time transformation reveals important relations
between the minimum Schnyder’s realizers of plane triangulations (Bonichon et al., Proceedings of the 20th Annual Symposium
on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2607, pp. 499–510, Springer, Berlin, 2003; Research Report RR-1279-02, LaBRI, University of Bordeaux, France; Brehm, Diploma thesis, FB Mathematik und Informatik,
Freie Universit?t Berlin, 2000) and the transversal structures of irreducible triangulations (Fusy, Proceedings of 13th International Symposium on Graph
Drawing, Lecture Notes in Computer Science, vol. 3843, pp. 177–188, Springer, Berlin, 2005; He, SIAM J. Comput. 22:1218–1226, 1993). The transformation morphs a 3-connected plane graph into an internally 4-connected plane graph. Therefore some of the graph
algorithms designed specifically for 4-connected plane graphs can be applied to 3-connected plane graphs indirectly. As an
example of such applications, we present a linear time algorithm that produces a planar polyline drawing for a plane graph
with n vertices in a grid of size bounded by W×H, where
W £ ?\frac2n-23?W\leq\lfloor\frac{2n-2}{3}\rfloor
, and
W+H £ ?\frac4n-43?W+H\leq\lfloor \frac{4n-4}{3}\rfloor
. It uses at most
?\frac2n-53?\lfloor\frac{2n-5}{3}\rfloor
bends, and each edge uses at most one bend. Our algorithm is area optimal. Compared with the existing area optimal polyline
drawing algorithm proposed in Bonichon et al. (Proceedings of the 28th International Workshop on Graph-Theoretic Concepts
in Computer Science, Lecture Notes in Computer Science, vol. 2573, pp. 35–46, Springer, Berlin, 2002), our algorithm uses a smaller number of bends. Their bend bound is (n−2). 相似文献
5.
In this paper we continue the study, which was initiated in (Ben-Artzi et al. in Math. Model. Numer. Anal. 35(2):313–303,
2001; Fishelov et al. in Lecture Notes in Computer Science, vol. 2667, pp. 809–817, 2003; Ben-Artzi et al. in J. Comput. Phys. 205(2):640–664, 2005 and SIAM J. Numer. Anal. 44(5):1997–2024, 2006) of the numerical resolution of the pure streamfunction formulation of the time-dependent two-dimensional Navier-Stokes equation.
Here we focus on enhancing our second-order scheme, introduced in the last three afore-mentioned articles, to fourth order
accuracy. We construct fourth order approximations for the Laplacian, the biharmonic and the nonlinear convective operators.
The scheme is compact (nine-point stencil) for the Laplacian and the biharmonic operators, which are both treated implicitly
in the time-stepping scheme. The approximation of the convective term is compact in the no-leak boundary conditions case and
is nearly compact (thirteen points stencil) in the case of general boundary conditions. However, we stress that in any case
no unphysical boundary condition was applied to our scheme. Numerical results demonstrate that the fourth order accuracy is
actually obtained for several test-cases. 相似文献
6.
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. 相似文献
7.
Paola Bonizzoni Gianluca Della Vedova Riccardo Dondi Giancarlo Mauri 《Algorithmica》2010,58(2):282-303
The problem of clustering fingerprint vectors with missing values is an interesting problem in Computational Biology that
has been proposed in Figueroa et al. (J. Comput. Biol. 11(5):887–901, 2004). In this paper we show some improvements in closing the gaps between the known lower bounds and upper bounds on the approximability
of variants of the biological problem. Moreover, we have studied two additional variants of the original problem proposed
in Figueroa et al. (Proc. 11th Computing: The Australasian Theory Symposium (CATS), CRPIT, vol. 41, pp. 57–60, 2005). We prove that all such problems are APX-hard even when each fingerprint contains only two unknown positions and we present
a greedy algorithm that has constant approximation factors for these variants. Despite the hardness of these restricted versions
of the problem, we show that the general clustering problem on an unbounded number of missing values such that they occur
for every fixed position of an input vector in at most one fingerprint is polynomial time solvable. 相似文献
8.
This paper explores interoperability for data represented using the Graph Annotation Framework (GrAF) (Ide and Suderman, 2007) and the data formats utilized by two general-purpose annotation systems: the General Architecture for Text Engineering (GATE)
(Cunningham et al., 2002) and the Unstructured Information Management Architecture (UIMA) (Ferrucci and Lally in Nat Lang Eng 10(3–4):327–348, 2004). GrAF is intended to serve as a “pivot” to enable interoperability among different formats, and both GATE and UIMA are at
least implicitly designed with an eye toward interoperability with other formats and tools. We describe the steps required
to perform a round-trip rendering from GrAF to GATE and GrAF to UIMA CAS and back again, and outline the commonalities as
well as the differences and gaps that came to light in the process. 相似文献
9.
Mitsuhiro T. Nakao Yoshitaka Watanabe Nobito Yamamoto Takaaki Nishida Myoung-Nyoung Kim 《Journal of scientific computing》2010,43(3):388-401
In previous works (Nakao et al., Reliab. Comput., 9(5):359–372, 2003; Watanabe et al., J. Math. Fluid Mech., 6(1):1–20, 2004), the authors considered the numerical verification method of solutions for two-dimensional heat convection problems known
as Rayleigh-Bénard problem. In the present paper, to make the arguments self-contained, we first summarize these results including
the basic formulation of the problem with numerical examples. Next, we will give a method to verify the bifurcation point
itself, which should be an important information to clarify the global bifurcation structure, and show a numerical example.
Finally, an extension to the three dimensional case will be described. 相似文献
10.
Preventing micro-channels from clogging is a major issue in most micro and nanofluidic systems (Gravesen et al., J Micromech
Microeng 3(4):168–182, 1993; Jensen et al., In: Proc. of MicroTAS 2002, Nara, Japan, pp 733–735, 2002; Wong et al., J Fluid Mech 292:71–94, 1995). The T-shaped channel first reported by Kohnle et al. (In: IEEE MEMS, the 15th international IEEE micro electro mechanical
conference (ed), Las Vegas, pp 77–80, 2002) prevents micro-channels from clogging by the aid of the equilibrium bubble position in such a geometry. This work is concerned
with the static and dynamic behaviour of bubbles in such T-shaped micro-channels. The aspect ratio of a rectangle enclosing
the T-shaped channel and the contact angle of the walls are the main parameters influencing the static and dynamic bubble
behaviour. It is investigated in this article how these parameters relate to the equilibrium bubble shape and how optimum
bubble velocities can be achieved inside the channel. An analytical model depending on the contact angle and the channel geometry
is presented that allows to determine the bubble configuration inside the channel by minimizing the bubble’s surface energy.
A second model is derived to predict the velocity of gas bubbles driven by buoyancy in vertical T-shaped channels. The model
is applied to design T-shaped channels with a maximum mobility of gas bubbles. Experiments with MEMS fabricated devices and
CFD simulations are used to verify the models. Furthermore design rules for an optimum non-clogging channel geometry which
provides the highest gas bubble mobility are given. 相似文献
11.
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. 相似文献
12.
This work deliberately introduces collective-rotation noise into quantum states to prevent an intercept-resend attack on Zhang’s
quantum secret sharing scheme over a collective-noise quantum channel (Zhang in Phys A 361:233–238, 2006). The noise recovering capability of the scheme remains intact. With this design, the quantum bit efficiency of the protocol
is doubled when compared to Sun et al.’s improvement on Zhang’s scheme (Sun et al. in Opt Commun 283:181–183, 2010). 相似文献
13.
Transaction-level modeling is used in hardware design for describing designs at a higher level compared to the register-transfer
level (RTL) (e.g. Cai and Gajski in CODES+ISSS ’03: proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software
codesign and system synthesis, pp. 19–24, 2003; Chen et al. in FMCAD ’07: proceedings of the formal methods in computer aided design, pp. 53–61, 2007; Mahajan et al. in MEMOCODE ’07: proceedings of the 5th IEEE/ACM international conference on formal methods and models for
codesign, pp. 123–132, 2007; Swan in DAC ’06: proceedings of the 43rd annual conference on design automation, pp. 90–92, 2006). Each transaction represents a unit of work, which is also a useful unit for design verification. In such models, there
are many properties of interest which involve interactions between multiple transactions. Examples of this are ordering relationships
in sequential processing and hazard checking in pipelined circuits. Writing such properties on the RTL design requires significant
expertise in understanding the higher-level computation being done in a given RTL design and possible instrumentation of the
RTL to express the property of interest. This is a barrier to the easy use of such properties in RTL designs. 相似文献
14.
Many different constructions of proofreading tile sets have been proposed in the literature to reduce the effect of deviations
from ideal behaviour of the dynamics of the molecular tile self-assembly process. In this paper, we consider the effect on
the tile assembly process of a different kind of non-ideality, namely, imperfections in the tiles themselves. We assume a
scenario in which some small proportion of the tiles in a tile set are “malformed”. We study, through simulations, the effect
of such malformed tiles on the self-assembly process within the kinetic Tile Assembly Model (kTAM). Our simulation results
show that some tile set constructions show greater error-resilience in the presence of malformed tiles than others. For example,
the 2- and 3-way overlay compact proofreading tile sets of Reif et al. (DNA Computing 10, Lecture Notes in Computer Science,
vol 3384. Springer, 2005) are able to handle malformed tiles quite well. On the other hand, the snaked proofreading tile set of Chen and Goel (DNA
Computing 10, Lecture Notes in Computer Science, vol 3384. Springer, 2005) fails to form even moderately sized tile assemblies when malformed tiles are present. We show how the Chen–Goel construction
may be modified to yield new snaked proofreading tile sets that are resilient not only to errors intrinsic to the assembly
process, but also to errors caused by malformed tiles. 相似文献
15.
Harry Buhrman Benjamin Hescott Steven Homer Leen Torenvliet 《Theory of Computing Systems》2010,47(2):317-341
We study properties of non-uniform reductions and related completeness notions. We strengthen several results of Hitchcock
and Pavan (ICALP (1), Lecture Notes in Computer Science, vol. 4051, pp. 465–476, Springer, 2006) and give a trade-off between the amount of advice needed for a reduction and its honesty on NEXP. We construct an oracle
relative to which this trade-off is optimal. We show, in a more systematic study of non-uniform reductions, among other things
that non-uniformity can be removed at the cost of more queries. In line with Post’s program for complexity theory (Buhrman
and Torenvliet in Bulletin of the EATCS 85, pp. 41–51, 2005) we connect such ‘uniformization’ properties to the separation of complexity classes. 相似文献
16.
We propose a new model of restricted branching programs specific to solving GEN problems, which we call incremental branching programs. We show that syntactic incremental branching programs capture previously studied models of computation for the problem GEN, namely marking machines
(Cook, S.A. in J. Comput. Syst. Sci. 9(3):308–316, 1974) and Poon’s extension (Proc. of the 34th IEEE Symp. on the Foundations of Computer Science, pp. 218–227, 1993) of jumping automata on graphs (Cook, S.A., Rackoff, C.W. in SIAM J. Comput. 9:636–652, 1980). We then prove exponential size lower bounds for our syntactic incremental model, and for some other variants of branching
program computation for GEN. We further show that nondeterministic syntactic incremental branching programs are provably stronger
than their deterministic counterpart when solving a natural NL-complete GEN sub-problem. It remains open if syntactic incremental
branching programs are as powerful as unrestricted branching programs for GEN problems.
A preliminary version of this paper appears as (Gál, A., Koucky, M., McKenzie, P., Incremental branching programs, in Proc.
of the 2006 Computer Science in Russia Conference CSR06. Lecture Notes in Computer Science, vol. 3967, pp. 178–190, 2006).
A. Gal supported in part by NSF Grant CCF-0430695 and an Alfred P. Sloan Research Fellowship. M. Koucky did part of this work
while being a postdoctoral fellow at McGill University, Canada and at CWI, Amsterdam, Netherlands. Supported in part by NWO
vici project 2004–2009, project No. 1M0021620808 of MŠMT ČR, grants 201/07/P276, 201/05/0124 of GA ČR, and Institutional Research
Plan No. AV0Z10190503.
P. McKenzie supported by the NSERC of Canada and the (Québec) FQRNT. 相似文献
17.
Susanne Albers 《Algorithmica》2010,58(2):461-477
We study web caching with request reordering. The goal is to maintain a cache of web documents so that a sequence of requests
can be served at low cost. To improve cache hit rates, a limited reordering of requests is allowed. Feder et al. (Proceedings
of the 13th ACM–SIAM Symposium on Discrete Algorithms, pp. 104–105, 2002), who recently introduced this problem, considered caches of size 1, i.e. a cache can store one document. They presented
an offline algorithm based on dynamic programming as well as online algorithms that achieve constant factor competitive ratios.
For arbitrary cache sizes, Feder et al. (Theor. Comput. Sci. 324:201–218, 2004) gave online strategies that have nearly optimal competitive ratios in several cost models. 相似文献
18.
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. 相似文献
19.
In this paper, we study two variants of the bin packing and covering problems called Maximum Resource Bin Packing (MRBP) and Lazy Bin Covering (LBC) problems, and present new approximation algorithms for them. For the offline MRBP problem, the previous best known approximation
ratio is
\frac65\frac{6}{5}
(=1.2) achieved by the classical First-Fit-Increasing (FFI) algorithm (Boyar et al. in Theor. Comput. Sci. 362(1–3):127–139, 2006). In this paper, we give a new FFI-type algorithm with an approximation ratio of
\frac8071\frac{80}{71}
(≈1.12676). For the offline LBC problem, it has been shown in Lin et al. (COCOON, pp. 340–349, 2006) that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of
\frac7160\frac{71}{60}
(≈1.18333). In this paper, we present a new FFD-type algorithm with an approximation ratio of
\frac1715\frac{17}{15}
(≈1.13333). Our algorithms are based on a pattern-based technique and a number of other observations. They run in near linear
time (i.e., O(nlog n)), and therefore are practical. 相似文献
20.
This paper provides a corrigendum to resolve a couple of minor issues in the algorithm presented in Sarkar et al. (Real-Time
Syst., 2011). The first issue relates to the postponement of execution of a task when its own ‘deadline of postponement’ have not been
crossed. The second issue concerns the updation of certain scheduler data structures. 相似文献