共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
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. 相似文献
5.
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. 相似文献
6.
In this paper we consider the p-ary transitive reduction (TR
p
) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of
experimental observations with a goal to minimize false positive inferences even if risking false negatives. Special cases
of TR
p
have been investigated before in different contexts; the best previous results are as follows:
In this paper, our contributions are as follows:
R. Albert’s research was partly supported by a Sloan Research Fellowship in Science and Technology.
B. DasGupta’s research was partly supported by NSF grants DBI-0543365, IIS-0612044 and IIS-0346973.
E. Sontag’s research was partly supported by NSF grants EIA 0205116 and DMS-0504557. 相似文献
(1) | The minimum equivalent digraph problem, that correspond to a special case of TR1 with no critical edges, is known to be MAX-SNP-hard, admits a polynomial time algorithm with an approximation ratio of 1.617+ε for any constant ε>0 (Chiu and Liu in Sci. Sin. 4:1396–1400, 1965) and can be solved in linear time for directed acyclic graphs (Aho et al. in SIAM J. Comput. 1(2):131–137, 1972). |
(2) | A 2-approximation algorithm exists for TR1 (Frederickson and JàJà in SIAM J. Comput. 10(2):270–283, 1981; Khuller et al. in 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 937–938, 1999). |
• | We observe that TR p , for any integer p>0, can be solved in linear time for directed acyclic graphs using the ideas in Aho et al. (SIAM J. Comput. 1(2):131–137, 1972). |
• | We provide a 1.78-approximation for TR1 that improves the 2-approximation mentioned in (2) above. |
• | We provide a 2+o(1)-approximation for TR p on general graphs for any fixed prime p>1. |
7.
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. 相似文献
8.
We present an exact algorithm that decides, for every fixed r≥2 in time O(m)+2O(k2)O(m)+2^{O(k^{2})} whether a given multiset of m clauses of size r admits a truth assignment that satisfies at least ((2
r
−1)m+k)/2
r
clauses. Thus Max-r-Sat is fixed-parameter tractable when parameterized by the number of satisfied clauses above the tight lower bound (1−2−r
)m. This solves an open problem of Mahajan et al. (J. Comput. Syst. Sci. 75(2):137–153, 2009). 相似文献
9.
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/ε. 相似文献
10.
The notion of ε-kernel was introduced by Agarwal et al. (J. ACM 51:606–635, 2004) to set up a unified framework for computing various extent measures of a point set P approximately. Roughly speaking, a subset Q⊆P is an ε-kernel of P if for every slab W containing Q, the expanded slab (1+ε)W contains P. They illustrated the significance of ε-kernel by showing that it yields approximation algorithms for a wide range of geometric optimization problems.
We present a simpler and more practical algorithm for computing the ε-kernel of a set P of points in ℝ
d
. We demonstrate the practicality of our algorithm by showing its empirical performance on various inputs. We then describe
an incremental algorithm for fitting various shapes and use the ideas of our algorithm for computing ε-kernels to analyze the performance of this algorithm. We illustrate the versatility and practicality of this technique by
implementing approximation algorithms for minimum enclosing cylinder, minimum-volume bounding box, and minimum-width annulus.
Finally, we show that ε-kernels can be effectively used to expedite the algorithms for maintaining extents of moving points.
A preliminary version of the paper appeared in Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 2004, pp. 263–272. Research by the first two authors is supported by NSF under grants CCR-00-86013, EIA-98-70724, EIA-01-31905,
and CCR-02-04118, and by a grant from the US–Israel Binational Science Foundation. Research by the fourth author is supported
by NSF CAREER award CCR-0237431. 相似文献
11.
We consider the problem of packing rectangles into bins that are unit squares, where the goal is to minimize the number of
bins used. All rectangles have to be packed non-overlapping and orthogonal, i.e., axis-parallel. We present an algorithm with
an absolute worst-case ratio of 2 for the case where the rectangles can be rotated by 90 degrees. This is optimal provided
P 1 NP\mathcal{P}\not=\mathcal{NP}
. For the case where rotation is not allowed, we prove an approximation ratio of 3 for the algorithm Hybrid First Fit which was introduced by Chung et al. (SIAM J. Algebr. Discrete Methods 3(1):66–76, 1982) and whose running time is slightly better than the running time of Zhang’s previously known 3-approximation algorithm (Zhang
in Oper. Res. Lett. 33(2):121–126, 2005). 相似文献
12.
Florentina Tone 《Journal of scientific computing》2009,38(3):331-348
Pursuing our work in Tone (Asymptot. Analysis 51:231–245, 2007) and Tone and Wirosoetisno (SIAM J. Number. Analysis 44:29–40, 2006), we consider in this article the two-dimensional magnetohydrodynamics equations, we discretize these equations in time using
the implicit Euler scheme and with the aid of the classical and uniform discrete Gronwall lemma, we prove that the scheme
is H
2-uniformly stable in time. 相似文献
13.
An earlier time for inserting and/or accelerating tasks 总被引:1,自引:0,他引:1
Qian Guangming 《Real-Time Systems》2009,41(3):181-194
In a periodic real-time system scheduled by the EDF (Earliest Deadline First) algorithm (Liu and Layland, J. ACM 20(1), 40–61,
1973; Barauh, Proc. of the 27th IEEE International Real-Time Systems Symposium, 379–387, 2006; Buttazzo, J. Real-Time Syst. 29(1), 5–26, 2005), when new tasks have to be inserted into the system at run-time and/or current tasks request to increase their rates in
response to internal or external events, the new sum of the utilizations after the insertion and/or acceleration should be
limited, otherwise, one or more current tasks should usually be compressed (their periods being prolonged) in order to avoid
overload. Buttazzo offered a time from which on this kind of adjustment can be done without causing any deadline miss in the
system (Buttazzo et al., IEEE Trans. Comput. 51(3), 289–302, 2002). It is, however, not early enough. In this paper, an earlier time is given and formally proved.
相似文献
Qian GuangmingEmail: |
14.
Winfree’s pioneering work led the foundations in the area of error-reduction in algorithmic self-assembly (Winfree and Bekbolatov
in DNA Based Computers 9, LNCS, vol. 2943, pp. 126–144, [2004]), but the construction resulted in increase of the size of assembly. Reif et al. (Nanotechnol. Sci. Comput. 79–103, [2006]) contributed further in this area with compact error-resilient schemes that maintained the original size of the assemblies,
but required certain restrictions on the Boolean functions to be used in the algorithmic self-assembly. It is a critical challenge
to improve these compact error resilient schemes to incorporate arbitrary Boolean functions, and to determine how far these
prior results can be extended under different degrees of restrictions on the Boolean functions. In this work we present a
considerably more complete theory of compact error-resilient schemes for algorithmic self-assembly in two and three dimensions.
In our error model, ε is defined to be the probability that there is a mismatch between the neighboring sides of two juxtaposed tiles and they
still stay together in the equilibrium. This probability is independent of any other match or mismatch and hence we term this
probabilistic model as the independent error model. In our model all the error analysis is performed under the assumption of kinetic equilibrium. First we consider two-dimensional
algorithmic self-assembly. We present an error correction scheme for reduction of errors from ε to ε
2 for arbitrary Boolean functions in two dimensional algorithmic self-assembly. Then we characterize the class of Boolean functions
for which the error can be reduced from ε to ε
3, and present an error correction scheme that achieves this reduction. Then we prove ultimate limits on certain classes of
compact error resilient schemes: in particular we show that they can not provide reduction of errors from ε to ε
4 is for any Boolean functions. Further, we develop the first provable compact error resilience schemes for three dimensional
tiling self-assemblies. We also extend the work of Winfree on self-healing in two-dimensional self-assembly (Winfree in Nanotechnol.
Sci. Comput. 55–78, [2006]) to obtain a self-healing tile set for three-dimensional self-assembly. 相似文献
15.
In a recent paper Boykov et al. (LNCS, Vol. 3953, pp. 409–422, 2006) propose an approach for computing curve and surface evolution using a variational approach and the geo-cuts method of Boykov and Kolmogorov (International conference on computer vision, pp. 26–33, 2003). We recall in this paper how this is related to well-known approaches for mean curvature motion, introduced by Almgren et al.
(SIAM Journal on Control and Optimization 31(2):387–438, 1993) and Luckhaus and Sturzenhecker (Calculus of Variations and Partial Differential Equations 3(2):253–271, 1995), and show how the corresponding problems can be solved with sub-pixel accuracy using Parametric Maximum Flow techniques. This provides interesting algorithms for computing crystalline curvature motion,
possibly with a forcing term.
A. Chambolle’s research supported by ANR project “MICA”, grant ANR-08-BLAN-0082.
J. Darbon’s research supported by ONR grant N000140710810. 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
Suppose that we are given n persistent tasks (jobs) that need to be executed in an equitable way on m processors (machines). Each machine is capable of performing one unit of work in each integral time unit and each job may
be executed on at most one machine at a time. The schedule needs to specify which job is to be executed on each machine in
each time window. The goal is to find a schedule that minimizes job migrations between machines while guaranteeing a fair
schedule. We measure the fairness by the drift d defined as the maximum difference between the execution times accumulated by any two jobs. As jobs are persistent we measure
the quality of the schedule by the ratio of the number of migrations to time windows. We show a tradeoff between the drift
and the number of migrations. Let n = qm + r with 0 < r < m (the problem is trivial for n ≤ m and for r = 0). For any d ≥ 1, we show a schedule that achieves a migration ratio less than r(m − r)/(n(q(d − 1)) + ∊ > 0; namely, it asymptotically requires r(m − r) job migrations every n(q(d − 1) + 1) time windows. We show how to implement the schedule efficiently. We prove that our algorithm is almost optimal
by proving a lower bound of r(m − r)/(nqd) on the migration ratio. We also give a more complicated schedule that matches the lower bound for a special case when 2q ≤ d and m = 2r. Our algorithms can be extended to the dynamic case in which jobs enter and leave the system over time. 相似文献
19.
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. 相似文献
20.
The basic scheduling problem we are dealing with in this paper is the following one. A set of jobs has to be scheduled on
a set of parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing
at its release date. All jobs have the same execution requirement and arbitrary due dates. Each machine has a known speed.
The processing of any job may be interrupted arbitrarily often and resumed later on any machine. The goal is to find a schedule
that minimizes the sum of tardiness, i.e., we consider problem Q∣r
j
,p
j
=p, pmtn∣∑T
j
whose complexity status was open. Recently, Tian et al. (J. Sched. 9:343–364, 2006) proposed a polynomial algorithm for problem 1∣r
j
,p
j
=p, pmtn∣∑T
j
. We show that both the problem P∣ pmtn∣∑T
j
of minimizing total tardiness on a set of parallel machines with allowed preemptions and the problem P∣r
j
,p
j
=p, pmtn∣∑T
j
of minimizing total tardiness on a set of parallel machines with release dates, equal processing times and allowed preemptions
are NP-hard. Moreover, we give a polynomial algorithm for the case of uniform machines without release dates, i.e., for problem
Q∣p
j
=p, pmtn∣∑T
j
. 相似文献