共查询到20条相似文献,搜索用时 31 毫秒
1.
Michal Koucký 《Theory of Computing Systems》2009,45(4):865-879
We survey the current state of knowledge on the circuit complexity of regular languages and we prove that regular languages
that are in AC0 and ACC0 are all computable by almost linear size circuits, extending the result of Chandra et al. (J. Comput. Syst. Sci. 30:222–234,
1985). As a consequence we obtain that in order to separate ACC0 from NC1 it suffices to prove for some ε>0 an Ω(n
1+ε
) lower bound on the size of ACC0 circuits computing certain NC1-complete functions.
Partially supported by grant GA ČR 201/07/P276, project No. 1M0021620808 of MŠMT ČR and Institutional Research Plan No. AV0Z10190503. 相似文献
2.
It is proved that an optimal {ε, 1}
n
solution to a “ε-perturbed” discrete minimum weight problem with constraints on compliance, von Mises stresses and strain energy densities,
is optimal, after rounding to {0, 1}
n
, to the corresponding “unperturbed” discrete problem, provided that the constraints in the perturbed problem are carefully
defined and ε > 0 is sufficiently small. 相似文献
3.
Alexander D. Healy 《Computational Complexity》2008,17(1):3-37
We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in uniform AC
0[⊕]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply
a variety expander-based techniques within NC
1. For example, we obtain the following results:
Our sampler is based on the zig-zag graph product of Reingold, Vadhan & Wigderson (Annals of Math 2002) and as part of our analysis we givean elementary proof of a generalization of Gillman’s Chernoff Bound for Expander Walks (SIAM Journal on Computing 1998).
相似文献
• | Randomness-efficient error-reduction for uniform probabilistic NC 1, TC 0, AC 0[⊕] and AC 0: Any function computable by uniform probabilistic circuits with error 1/3 using r random bits is computable by circuits of the same type with error δ using r + O(log(1/δ)) random bits. |
• | An optimal bitwise ϵ-biased generator in AC 0[⊕]: There exists a 1/2Ω(n)-biased generator G : {0, 1} O(n) → {0, 1}2n for which poly(n)-size uniform AC 0[⊕] circuits can compute G(s) i given (s, i) ∈ {0, 1} O(n) × {0, 1} n . This resolves question raised by Gutfreund and Viola (Random 2004). |
• | uniform BP · AC 0 ⊆ uniform AC 0/O(n). |
4.
5.
In this paper we address several issues arising from a singularly perturbed fourth order problem with small parameter ε. First, we introduce a new family of non-conforming elements. We then prove that the corresponding finite element method is robust with respect to the parameter ε and uniformly convergent to order h 1/2. In addition, we analyze the effect of treating the Neumann boundary condition weakly by Nitsche’s method. We show that such treatment is superior when the parameter ε is smaller than the mesh size h and obtain sharper error estimates. Such error analysis is not restricted to the proposed elements and can easily be carried out to other elements as long as the Neumann boundary condition is imposed weakly. Finally, we discuss the local error estimates and the pollution effect of the boundary layers in the interior of the domain. 相似文献
6.
Liu 《Theory of Computing Systems》2008,35(5):559-564
A modified fast approximation algorithm for the 0-1 knapsack problem with improved complexity is presented, based on the
schemes of Ibarra, Kim and Babat. By using a new partition of items, the algorithm solves the n -item 0-1 knapsack problem to any relative error tolerance ε > 0 in the scaled profit space P
*
/K = O ( 1/ ε
1+δ
) with time O(n log(1/ ε )+1/ ε^{2+2δ}) and space O(n +1/ ɛ^{2+δ}), where P^{*} and b are the maximal profit and the weight capacity of the knapsack problem, respectively, K is a problem-dependent scaling factor, δ={α}/(1+α) and α=O( log b ). This algorithm reduces the exponent of the complexity bound in [5]. 相似文献
7.
Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC1 . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for
this problem requires depth. This would separate AC1 from NC1. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using
communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem
which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d
2(k log k)1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function
on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof
will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds.
Received: July 30, 1999. 相似文献
8.
A 0-1 matrix has the Consecutive Ones Property (C1P) if there is a permutation of its columns that leaves the 1's consecutive
in each row. The Consecutive Ones Submatrix (C1S) problem is, given a 0-1 matrix A, to find the largest number of columns
of A that form a submatrix with the C1P property. Such a problem finds application
in physical mapping with hybridization data in genome sequencing. Let (a, b)-matrices be the 0-1 matrices in which there are
at most a 1's in each column and at most b 1's in each row. This paper proves that the C1S problem remains NP-hard for (i)
(2, 3)-matrices and (ii) (3, 2)-matrices. This solves an open problem posed in a recent paper of Hajiaghayi and Ganjali. We
further prove that the C1S problem is polynomial-time 0.8-approximatable for (2, 3)-matrices in which no two columns are identical
and 0.5-approximatable for (2, ∞)-matrices in general. We also show that the C1S problem is polynomial-time 0.5-approximatable
for (3, 2)-matrices. However, there exists an ε > 0 such that approximating the C1S problem for (∞, 2)-matrices within a factor
of nε (where n is the number of columns of the input matrix) is NP-hard. 相似文献
9.
Ricardo H. Nochetto 《Calcolo》1985,22(4):501-534
In this paper we derive L2-error estimates for multidimensional two-phase Stefan problems involving further non-linearities such as non-linear flux
conditions. We approximate the enthalpy formulation by a regularization procedure combined with a C0-piecewise linear finite element scheme in space, and the implicit Euler scheme in time.
Under some restrictions on the initial datum and on the finite element mesh, we obtain an L2-rate of convergence of order ε1/2 for regularized problems, and an L2-rate of convergence of order (h|log h|k+τ+ε)1/2 for the discrete problems (k=0,1). These estimates lead to the choice h∼ε∼τ and yeild a global L2-rate essentially of order h1/2.
The a priori relationship between the approximation parameters allows the discrete problem to satisfy a maximum principle
(without a lumping procedure); from which a priori bounds and monotonicity properties of the discrete solutions are shown.
This work was supported by the “Consejo Nacional de Investigaciones Científicas y Técnicas de la República Argentina”. 相似文献
10.
We study local, distributed algorithms for the capacitated minimum dominating set (CapMDS) problem, which arises in various
distributed network applications. Given a network graph G=(V,E), and a capacity cap(v)∈ℕ for each node v∈V, the CapMDS problem asks for a subset S⊆V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S, and every node v∈S covers at most cap(v) of its neighbors. We prove that in general graphs and even with uniform capacities, the problem is inherently non-local, i.e., every distributed algorithm achieving a non-trivial approximation ratio must have a time complexity that essentially
grows linearly with the network diameter. On the other hand, if for some parameter ε>0, capacities can be violated by a factor of 1+ε, CapMDS becomes much more local. Particularly, based on a novel distributed randomized rounding technique, we present a distributed
bi-criteria algorithm that achieves an O(log Δ)-approximation in time O(log 3
n+log (n)/ε), where n and Δ denote the number of nodes and the maximal degree in G, respectively. Finally, we prove that in geometric network graphs typically arising in wireless settings, the uniform problem
can be approximated within a constant factor in logarithmic time, whereas the non-uniform problem remains entirely non-local. 相似文献
11.
The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism
problem can be solved by efficient parallel algorithms, it is in the class AC
1. In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to UL∩coUL. As a consequence of our method we get that the isomorphism problem for oriented graphs is in NL. We also show that the problems are hard for L. 相似文献
12.
On approximating the longest path in a graph 总被引:6,自引:0,他引:6
We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable
performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a
simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs
that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian
graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible.
Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively
long path can be obtained, thereby partially answering an open problem of Broderet al.
To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any ε<1, the
problem of finding a path of lengthn-n
ε in ann-vertex Hamiltonian graph isNP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem
unlessP=NP. We conjecture that the result can be strengthened to say that, for some constant δ>0, finding an approximation of ration
δ is alsoNP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path
to a ratio of
, for any ε>0, thenNP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input
consists of bounded degree graphs.
D. Karger was supported by an NSF Graduate Fellowship, NSF Grant CCR-9010517, and grants from the Mitsubishi Corporation and
OTL. R. Motwani was supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award, grants from Mitsubishi
and OTL, NSF Grant CCR-9010517, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, the Schlumberger
Foundation, the Shell Foundation, and the Xerox Corporation, G. D. S. Ramkumar was supported by a grant from the Toshiba Corporation.
Communicated by M. X. Goemans. 相似文献
13.
Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems.
In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present algorithms that compute, for any fixed ε>0, a (1−ε)-approximation to the optimal solution in O(nlog n) time.
In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that computes, for any fixed ε>0, in O(nlog 2
n) expected time a disk that is, with high probability, a (1+ε)-approximation to the optimal solution.
A preliminary version of this work has appeared in Approximation and Online Algorithms—WAOA 2006, LNCS, vol. 4368. 相似文献
14.
Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The k-Facility Location problem further requires that the number of opened facilities is at most k, where k is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant > 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 + ω + 1 + ε, which significantly improves the previous best known ratio (ω + 1)/α for some 1≤α≤2, and a polynomial-time approximation algorithm for the ω-constrained k- Facility Location problem with approximation ratio ω+1+ε. On the aspect of approximation hardness, we prove that unless NP■DTIME(nO(loglogn)), the ω-constrained Facility Location problem cannot be approximated within 1 + lnω - 1, which slightly improves the previous best known hardness result 1.243 + 0.316ln(ω - 1). The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice. 相似文献
15.
Ricardo H. Nochetto 《Calcolo》1985,22(4):457-499
The enthalpy formulation of two-phase Stefan problems, with linear boundary conditions, is approximated by C0-piecewise linear finite elements in space and backward-differences in time combined with a regularization procedure. Error
estimates of L2-type are obtained. For general regularized problems an order ε1/2 is proved, while the order is shown to be ε for non-degenerate cases. For discrete problems an order h2ε−1+h+τε−1/2+τ2/3 is obtained. These orders impose the relations ε∼τ∼h4/3 for the general case and ε∼h∼τ2/3 for non-degenerate problems, in order to obtain rates of convergence h2/3 or h respectively. Besides, an order h|log h|+τ1/2 is shown for finite element meshes with certain approximation property. Also continuous dependence of discrete solutions
upon the data is proved.
This work was supported by the “Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET)” of Argentina. 相似文献
16.
Liming Cai Michael Fellows David Juedes Frances Rosamond 《Theory of Computing Systems》2007,41(3):459-477
In 1996 Khanna and Motwani proposed three logic-based optimization problems constrained by planar structure, and offered the
hypothesis that these putatively fundamental problems might provide insight into
characterizing the class of optimization problems that admit a polynomial-time approximation scheme (PTAS). The main contribution
of this paper is to explore this program from the point of view of parameterized complexity. Problems of optimization are
naturally parameterized by the parameter k = 1/ε. An optimization problem admits a PTAS if and only if there is an algorithm
Φ, that, given an input of size n, and a parameter value k = 1/ε, produces a solution that is within a multiplicative factor
of (1+ ε) of optimal, in a running time that is polynomial for every fixed value of ε. This definition admits the possibility
that the degree of the polynomial that bounds the running time of Φ may increase, even quite dramatically, as a function of
k = 1/ε. In fact, amongst the PTASs that are currently known, for an error of 20%, polynomial-time bounds no better than
O(n2000) are quite common. Viewing k = 1/ε as a problem parameter, in the sense of parameterized complexity, leads naturally to the
question of whether an efficient PTAS (EPTAS) might be possible for a given optimization problem. An EPTAS is simply a fixed-parameter
tractable algorithm with respect to this parameter. We offer a number of results concerning the problems Planar TMIN, Planar
TMAX and Planar MPSAT defined by Khanna and Motwani: (1) We show that each of these problems of approximation, naturally parameterized
by k = 1/ε, is hard for W[1], and thus it is highly unlikely that they admit EPTASs. (One could also interpret this as indicating
that PTASs for these problems are unlikely to be a useful way of coping with intractability in the sense of Garey and Johnson.)
(2) We show that there are EPTASs for some subproblems described by syntactic restrictions, and establish some limits on how
far these positive results can be extended. 相似文献
17.
The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis
Heribert Vollmer 《Theory of Computing Systems》2009,44(1):82-90
We study the complexity of the following algorithmic problem: Given a Boolean function f and a finite set of Boolean functions B, decide if there is a circuit with basis B that computes f. We show that if both f and all functions in B are given by their truth-table, the problem is in quasipolynomial-size AC0, and thus cannot be hard for AC0(2) or any superclass like NC1, L, or NL. This answers an open question by Bergman and Slutzki (SIAM J. Comput., 2000). Furthermore we show that, if the input functions are not given by their truth-table but in a succinct way, i.e., by circuits
(over any complete basis), the above problem becomes complete for the class coNP.
Supported in part by DFG Grant Vo 630/5-2 and EPSRC Grant 531174. 相似文献
18.
In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error
algorithm with updates and queries in O(n
ω(1,1,ε)−ε
) time given a lookahead of n
ε
operations, where ω(1,1,ε) is the exponent of multiplication of n×n matrix by n×n
ε
matrix. For ε≤0.294 we obtain an algorithm with queries and updates in O(n
2−ε
) time, whereas for ε=1 the time is O(n
ω−1). This is essentially optimal as it implies an O(n
ω
) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this
problem, we show an algorithm that requires
O(n\fracw2)O(n^{\frac{\omega}{2}})
time to process
n\frac12n^{\frac{1}{2}}
operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms
for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error.
All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest. 相似文献
19.
Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time 总被引:1,自引:1,他引:0
Marius Zimand 《Computational Complexity》2008,17(2):220-253
20.
A pair (T,C) of a tree T and a coloring C is called a colored tree. Given a colored tree (T,C) any coloring C′ of T is called a recoloring of T. Given a weight function on the vertices of the tree the recoloring distance of a recoloring is the total weight of recolored vertices. A coloring of a tree is convex if for any two vertices u and v that are colored by the same color c, every vertex on the path from u to v is also colored by c. In the minimum convex recoloring problem we are given a colored tree and a weight function and our goal is to find a convex recoloring of minimum recoloring distance.
The minimum convex recoloring problem naturally arises in the context of phylogenetic trees. Given a set of related species the goal of phylogenetic reconstruction is to construct a tree that would best describe the
evolution of this set of species. In this context a convex coloring corresponds to perfect phylogeny. Since perfect phylogeny is not always possible the next best thing is to find a tree which is as close to convex as possible,
or, in other words, a tree with minimum recoloring distance.
We present a (2+ε)-approximation algorithm for the minimum convex recoloring problem, whose running time is O(n
2+n(1/ε)241/ε
). This result improves the previously known 3-approximation algorithm for this NP-hard problem. We also present an algorithm
for computing an optimal convex recoloring whose running time is
, where n
* is the number of colors that violate convexity in the input tree, and Δ is the maximum degree of vertices in the tree. The
parameterized complexity of this algorithm is O(n
2+n⋅k⋅2
k
). 相似文献