共查询到20条相似文献,搜索用时 15 毫秒
1.
V. S. Anil Kumar Madhav V. Marathe Srinivasan Parthasarathy Aravind Srinivasan 《Algorithmica》2009,55(1):205-226
We present polylogarithmic approximations for the R|prec|C
max and R|prec|∑
j
w
j
C
j
problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a
forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints
that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated
machines with precedence constraints of any kind. We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment—this
generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion + dilation”, as
in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–632, 1994). The first step in our algorithm for the R|prec|C
max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment
with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays
technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique
which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function.
A preliminary version of this paper appeared in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 146–157, 2005.
V.S. Anil Kumar supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory,
and supported in part by the Department of Energy under Contract W-7405-ENG-36.
M.V. Marathe supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory,
and supported in part by the Department of Energy under Contract W-7405-ENG-36.
Part of this work by S. Parthasarathy was done while at the Department of Computer Science, University of Maryland, College
Park, MD 20742, and in part while visiting the Los Alamos National Laboratory. Research supported in part by NSF Award CCR-0208005
and NSF ITR Award CNS-0426683.
Research of A. Srinivasan supported in part by NSF Award CCR-0208005, NSF ITR Award CNS-0426683, and NSF Award CNS-0626636. 相似文献
2.
刘田 《计算机科学技术学报》2000,15(5):0-0
The following four conjectures about structural of SAT are studied in this paper.(1) SAT∈P^SPARSE∩NP;(2)SAT∈SRTDtt;(3)SAT∈Ptt^bAPP;(4)FPtt^SAT=FTlog^SAT.It is proved that some pairs of these conjectures imply P=NP ,for example,if SAT∈P^SPARSE∩NP and SAT∈Ptt^bAPP,or if SAT∈SRTDtt and SAT∩PttbAPP,then P=NP.This improves previous results in literature. 相似文献
3.
In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized
in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total
tardiness 1‖max-ΣT
j
and for the problem of maximizing the number of tardy jobs 1‖maxΣU
j
. In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between
the jobs. We show that problem 1‖max-ΣT
j
is polynomially solvable. For several special cases of problem 1‖maxΣT
j
, we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the
latter problem and an alternative exact algorithm. 相似文献
4.
This paper proves that the complexity class P, parity polynomial time [PZ], contains the class of languages accepted byNP machines with few accepting paths. Indeed, P contains a broad class of languages accepted by path-restricted nondeterministic machines. In particular, P contains the polynomial accepting path versions ofNP, of the counting hierarchy, and of Mod
m
NP form>1. We further prove that the class of nondeterministic path-restricted languages is closed under bounded truth-table reductions.These results were announced at the 6th Symposium on Theoretical Aspects of Computer Science [CH3]. Jin-yi Cai was supported in part by NSF Grant CCR-8709818 and the work was done while he was at Yale University. Lane A. Hemachandra was supported in part by a Hewlett-Packard Corporation equipment grant and the National Science Foundation under Grant CCR-8809174/CCR-8996198 and a Presidential Young Investigator Award. His work was done in part while at Columbia University. 相似文献
5.
In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P
≠
NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We
show that 3SAT with a version of the standard distribution is truth-table reducible but not many-one reducible to 3SAT with
a less redundant distribution unless P = NP .
We extend this separation result and define a distributional complexity class C with the following properties:
(1) C is a subclass of DistNP, this relation is proper unless P = NP.
(2) C contains DistP, but it is not contained in AveP unless DistNP
\subseteq AveZPP.
(3) C has a ≤
p
m
-complete set.
(4) C has a ≤
p
tt
-complete set that is not ≤
p
m
-complete unless P = NP.
This shows that under the assumption that P ≠ NP, the two completeness notions differ on some nontrivial subclass of DistNP. 相似文献
6.
Yongxi Cheng 《计算机科学技术学报》2007,22(6):909-913
We investigate the problem of listing combinations using a special class of operations, prefix shifts. Combinations are represented as bitstrings of O's and l's, and prefix shifts are the operations of rotating some prefix of a bitstring by one position to left or right. We give a negative answer to an open problem asked by F. Ruskey and A. Williams (Generating combinations by prefix shifts, In Proc. llth Annual International Computing and Combinatorics Conference 2005, LNCS 3595, Springer, 2005, pp.570-576), that is whether we can generate combinations by only using three very basic prefix shifts on bitstrings, which are transposition of the first two bits and the rotation of the entire bitstring by one position in either direction (i.e., applying the permutations σ2, σn and σn^-1 to the indices of the bitstrings). 相似文献
7.
L. Rocha 《Computing》1997,59(3):187-207
LetG be a compact set in ℝ
d
d≥1,M=G×G andϕ:M →G a map inC
3(M). Suppose thatϕ has a fixed pointξ, i.e.ϕ(ξ, ξ)=ξ. We investigate the rate of convergence of the iterationx
n+2=φ(x
n+1,x
n) withx
0,x
1∈G andx
n→ξ. Iff
n=Q‖x
n−ξ‖ with a suitable norm and a constantQ depending onξ, an exact representation forf
n is derived. The error terms satisfyf
2m+1≍(ƒ2m)γ,f
2m+2≍(ƒ2m+1)2γ,m≥0, with 1<gg<2, andγ=γ(x
1,x
0). According to our main result we have limn→∞{‖x
n+2‖/(‖x
n‖)2}=Q, 0<Q<∞.
This paper constitutes an extension of a part of the author’s doctoral thesis realized under the direction of Prof. E. Wirsing
and Prof. A. Peyerimhoff, University of Ulm (Germany). 相似文献
8.
The problem of finding approximate solutions for a subclass of multicovering problems denoted byILP(k, b) is considered. The problem involves findingx∈{0,1}
n
that minimizes ∑
j
x
j
subject to the constraintAx≥b, whereA is a 0–1m×n matrix with at mostk ones per row,b is an integer vector, andb is the smallest entry inb. This subclass includes, for example, the Bounded Set Cover problem whenb=1, and the Vertex Cover problem whenk=2 andb=1.
An approximation ratio ofk−b+1 is achievable by known deterministic algorithms. A new randomized approximation algorithm is presented, with an approximation
ratio of (k−b+1)(1−(c/m)1/(k−b+1)) for a small constantc>0. The analysis of this algorithm relies on the use of a new bound on the sum of independent Bernoulli random variables,
that is of interest in its own right.
The first author was supported in part by a Walter and Elise Haas Career Development Award and by a grant from the Israeli
Science Foundation. This work was done white the third author was at the Department of Applied Mathematics and Computer Science,
The Weizmann Institute, Rehovot 76100, Israel. 相似文献
9.
The programming of SIMD machines that strongly support data parallelism, such as the Connection Machine, 1 presents new challenges for language, compiler, and algorithm designers. We propose an array language that captures many of the abstractions that are necessary for the effective programming of such machines, thereby liberating the user from having to specify low-level details. Consequently, this new language, ALP, allows for efficient compilation using state-of-the-art techniques, achieving hand-code quality. We demonstrate the effectiveness of our approach by two examples which show that despite being an array language, ALP does not restrict expressiveness to rigidly regular computational structures.Work supported in part by ONR grant number N00014-89-J-1906 while on sabbatical leave at the Department of Computer Science, Yale University.Work supported in part by NSF grant number DCR-8405478 while on sabbatical leave at the Department of Computer Science, Yale University. 相似文献
10.
Semantic scene classification is an open problem in computer vision, especially when information from only a single image
is employed. In applications involving image collections, however, images are clustered sequentially, allowing surrounding
images to be used as temporal context. We present a general probabilistic temporal context model in which the first-order
Markov property is used to integrate content-based and temporal context cues. The model uses elapsed time-dependent transition probabilities between images to enforce the fact that images captured within a shorter period of time are more
likely to be related. This model is generalized in that it allows arbitrary elapsed time between images, making it suitable
for classifying image collections. In addition, we derived a variant of this model to use in ordered image collections for
which no timestamp information is available, such as film scans. We applied the proposed context models to two problems, achieving
significant gains in accuracy in both cases. The two algorithms used to implement inference within the context model, Viterbi
and belief propagation, yielded similar results with a slight edge to belief propagation.
Matthew Boutell received the BS degree in Mathematical Science from Worcester Polytechnic Institute, Massachusetts, in 1993, the MEd degree
from University of Massachusetts at Amherst in 1994, and the PhD degree in Computer Science from the University of Rochester,
Rochester, NY, in 2005. He served for several years as a mathematics and computer science instructor at Norton High School
and Stonehill College and as a research intern/consultant at Eastman Kodak Company. Currently, he is Assistant Professor of
Computer Science and Software Engineering at Rose-Hulman Institute of Technology in Terre Haute, Indiana. His research interests
include image understanding, machine learning, and probabilistic modeling.
Jiebo Luo received his PhD degree in Electrical Engineering from the University of Rochester, Rochester, NY in 1995. He is a Senior
Principal Scientist with the Kodak Research Laboratories.
He was a member of the Organizing Committee of the 2002 IEEE International Conference on Image Processing and 2006 IEEE International
Conference on Multimedia and Expo, a guest editor for the Journal of Wireless Communications and Mobile Computing Special
Issue on Multimedia Over Mobile IP and the Pattern Recognition journal Special Issue on Image Understanding for Digital Photos,
and a Member of the Kodak Research Scientific Council.
He is on the editorial boards of the IEEE Transactions on Multimedia, Pattern Recognition, and Journal of Electronic Imaging.
His research interests include image processing, pattern recognition, computer vision, medical imaging, and multimedia communication.
He has authored over 100 technical papers and holds over 30 granted US patents. He is a Kodak Distinguished Inventor and a
Senior Member of the IEEE.
Chris Brown (BA Oberlin 1967, PhD University of Chicago 1972) is Professor of Computer Science at the University of Rochester.
He has published in many areas of computer vision and robotics. He wrote COMPUTER VISION with his colleague Dana Ballard,
and influential work on the “active vision” paradigm was reported in two special issues of the International Journal of Computer
Vision. He edited the first two volumes of ADVANCES IN COMPUTER VISION for Erlbaum and (with D. Terzopoulos) REAL-TIME COMPUTER
VISION, from Cambridge University Press. He is the co-editor of VIDERE, the first entirely on-line refereed computer vision
journal (MIT Press).
His most recent PhD students have done research in infrared tracking and face recognition, features and strategies for image
understanding, augmented reality, and three-dimensional reconstruction algorithms.
He supervised the undergraduate team that twice won the AAAI Host Robot competition (and came third in the Robot Rescue competition
in 2003). 相似文献
11.
We study FP||
NP , the class of functions that can be computed in polynomial time with nonadaptive queries to an NP oracle. This is motivated
by the question of whether it is possible to compute witnesses for NP sets within FP||
NP . The known algorithms for this task all require sequential access to the oracle. On the other hand, there is no evidence
known yet that this should not be possible with parallel queries.
We define a class of optimization problems based on NP sets, where the optimum is taken over a polynomially bounded range
(NPbOpt). We show that if such an optimization problem is based on one of the known NP-complete sets, then it is hard for FP||
NP . Moreover, we characterize FP||
NP as the class of functions that reduces to such optimization functions. We call this property strong hardness.
The main question is whether these function classes are complete for FP||
NP . That is, whether it is possible to compute an optimal value for a given optimization problem in FP||
NP . We show that these optimization problems are complete for FP||
NP , if and only if one can compute membership proofs for NP sets in FP||
NP . This indicates that the completeness question is a hard one.
Received October 1995, and in final form March 1997. 相似文献
12.
Chang and Kadin have shown that if the difference hierarchy over NP collapses to levelk, then the polynomial hierarchy (PH) is equal to thekth level of the difference hierarchy over
2
p
. We simplify their poof and obtain a slightly stronger conclusion: if the difference hierarchy over NP collapses to levelk, then PH collapses to (P
(k–1)
NP
)NP, the class of sets recognized in polynomial time withk – 1 nonadaptive queries to a set in NPNP and an unlimited number of queries to a set in NP. We also extend the result to classes other than NP: For any classC that has
m
p
-complete sets and is closed under
conj
p
-and
m
NP
-reductions (alternatively, closed under
disj
p
-and
m
co-NP
-reductions), if the difference hierarchy overC collapses to levelk, then PH
C
= (P
(k–1)–tt
NP
)
C
. Then we show that the exact counting class C_P is closed under
disj
p
- and
m
co-NP
-reductions. Consequently, if the difference hierarchy over C_P collapses to levelk, then PHPP(= PHC_P) is equal to (P
(k–1)–tt
NP
)PP. In contrast, the difference hierarchy over the closely related class PP is known to collapse.Finally we consider two ways of relativizing the bounded query class P
k–tt
NP
: the restricted relativization P
k–tt
NP
C
and the full relativization (P
k–tt
NP
)
C
. IfC is NP-hard, then we show that the two relativizations are different unless PH
C
collapses.Richard Beigel was supported in part by NSF Grants CCR-8808949 and CCR-8958528. Richard Chang was supported in part by NSF Research Grant CCR 88-23053. This work was done while Mitsunori Ogiwara was at the Department of Information Science, Tokyo Institute of Technology, Tokyo, Japan. 相似文献
13.
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas 总被引:1,自引:0,他引:1
Michael Alekhnovich Edward A. Hirsch Dmitry Itsykson 《Journal of Automated Reasoning》2005,35(1-3):51-72
DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are
widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to
treelike resolution proofs. Therefore, lower bounds for treelike resolution (known since the 1960s) apply to them. However,
these lower bounds say nothing about the behavior of such algorithms on satisfiable formulas. Proving exponential lower bounds
for them in the most general setting is impossible without proving P ≠ NP; therefore, to prove lower bounds, one has to restrict the power of branching heuristics. In this paper, we give exponential
lower bounds for two families of DPLL algorithms: generalized myopic algorithms, which read up to n
1−ε
of clauses at each step and see the remaining part of the formula without negations, and drunk algorithms, which choose a variable using any complicated rule and then pick its value at random.
★Extended abstract of this paper appeared in Proceedings of ICALP 2004, LNCS 3142, Springer, 2004, pp. 84–96.
†Supported by CCR grant CCR-0324906.
‡Supported in part by Russian Science Support Foundation, RAS program of fundamental research “Research in principal areas
of contemporary mathematics,” and INTAS grant 04-77-7173.
§Supported in part by INTAS grant 04-77-7173. 相似文献
14.
Leen Torenvliet 《Theory of Computing Systems》1988,21(1):99-123
In this paper we discuss the concepts ofimmunity andsimplicity in levels of the relativized Polynomial-time Hierarchy just aboveP. We consider various diagonalization techniques with which oracle sets can be constructed relative to which strong separations
between language classes in the first two levels of this hierarchy are established. In particular, we build oracle sets for
separation of relativized Σ
2
P
from relativizedNP with immunity, of relativized Σ
2
P
from relativizedNP with bi-immunity, of relativized Σ
2
P
from relativized Δ
2
P
with immunity, of relativized Π
2
P
from relativized Δ
2
P
with immunity, and finally of relativized Σ
2
P
from relativized Π
2
P
with simplicity. 相似文献
15.
Every class C of languages satisfying a simple topological condition is shown to have probability one if and only if it contains some language that is algorithmically random in the sense of Martin-Löf. This result is used to derive separation properties of algorithmically random oracles and to give characterizations of the complexity classesP, BPP, AM, andPH in terms of reducibility to such oracles. These characterizations lead to results like:P =NP if and only if an algorithmically random set exists that is
btt
P
-hard forNP.The work of the first author was supported in part by the Alexander-von-Humboldt-Stiftung and by the National Science Foundation under Grant CCR-8913584 while he visited the Lehrstuhl für Theoretische Informatik, Institut für Informatik, Universität Würzburg, Germany. The work of the second author was supported in part by the National Science Foundation under Grant CCR-8809238 and in part by DIMACS, where he was a visitor while a portion of his work was done. 相似文献
16.
Marshall Slemrod 《Mathematics of Control, Signals, and Systems (MCSS)》1989,2(3):265-285
This paper derives a feedback controlf(t), ‖f(t)‖E≦r,r>0, which forces the infinite-dimensional control systemdu/dt=Au+Bf, u(0)=u
o
≠H to have the asymptotic behavioru(t)→0 ast→∞ inH. HereA is the infinitesimal generator of aC
o semigroup of contractionse
At
on a real Hilbert spaceH andB is a bounded linear operator mapping a Hilbert space of controlsE intoH. An application to the boundary feedback control of a vibrating beam is provided in detail and an application to the stabilization
of the NASA Spacecraft Control Laboratory is sketched.
This research was sponsored in part by the Air Force Office of Scientific Research, Air Force Systems Command, USAF Contract/Grants
AFOSR 81-0172 and AFOSR 87-0315. 相似文献
17.
We consider the problem of ray shooting in a three-dimensional scene consisting of k (possibly intersecting) convex polyhedra with a total of n facets. That is, we want to preprocess them into a data structure, so that the first intersection point of a query ray and
the given polyhedra can be determined quickly. We describe data structures that require
preprocessing time and storage (where the
notation hides polylogarithmic factors), and have polylogarithmic query time, for several special instances of the problem.
These include the case when the ray origins are restricted to lie on a fixed line ℓ
0, but the directions of the rays are arbitrary, the more general case when the supporting lines of the rays pass through ℓ
0, and the case of rays orthogonal to some fixed line with arbitrary origins and orientations. We also present a simpler solution
for the case of vertical ray-shooting with arbitrary origins. In all cases, this is a significant improvement over previously
known techniques (which require Ω(n
2) storage, even when k
≪
n).
Work by Haim Kaplan and Natan Rubin has been supported by Grant 975/06 from the Israel Science Fund. Work by Micha Sharir
and Natan Rubin was partially supported by NSF Grant CCF-05-14079, by a grant from the U.S.–Israeli Binational Science Foundation,
by grant 155/05 from the Israel Science Fund, Israeli Academy of Sciences, by a grant from the AFIRST French–Israeli program,
and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. A preliminary version of this paper appeared
in Proc. 15th Annu. Europ. Sympos. Alg. (2007), 287–298. 相似文献
18.
M. Yu. Khachai 《Pattern Recognition and Image Analysis》2008,18(2):236-242
In [1, 2], results on the computational and approximational complexity of a minimum affine separating committee (MASC) problem
were obtained for finite sets A, B ⊂ ℚ
n
. In particular, it was shown that this problem is NP-hard and does not belong to the class Apx (under the assumption that P ≠ NP). Nevertheless, questions concerning the bounds for its effective approximability threshold and for the computational complexity
of a number of practically important particular cases of the problem obtained by imposing additional constraints, for example,
by fixing the dimension of the space, remained open. In this paper, a lower bound is presented for the polynomial approximability
threshold of the problem in the general case, and the intractability of the problem in spaces of fixed dimension greater than
unity is proved. In particular, it is shown that the problem of committee separability remains hard even when it is formulated
on the plane (i.e., in the simplest non-trivial case). This result follows from the fact that the well-known PC problem on
covering a finite planar set by straight lines, whose hardness was proved in [3], is polynomially reducible to the problem
under consideration. The method of reduction represents a modification of the method that was described in [4] and was used
there for proving the hardness of problems on piecewise linear separability of finite sets on the plane.
Mikhail Yur’evich Khachai. Born 1970 in Krasnotur’insk, Sverdlovsk region. Graduated from the Faculty of Mathematics and Mechanics, Ural State University,
Yekaterinburg, in 1993. Received candidate’s degree in mathematical cybernetics in 1996 and doctoral degree in 2005. Since
1994 he has been with the Institute of Mathematics and Mechanics, Ural Division, Russian Academy of Sciences. Since 1997 he
has headed the Department of Pattern Recognition at the same institute. Scientific interests: theory and methods of patter
recognition learning, committee (perceptron) decision rules, and theory and methods of improper optimization problems and
combinatorial optimization. Author of more than 60 publications, including 10 papers in Pattern Recognition and Image Processing. 相似文献
19.
20.
Thecorrelation between two Boolean functions ofn inputs is defined as the number of times the functions agree minus the number of times they disagree, all divided by 2
n
. In this paper we compute, in closed form, the correlation between any twosymmetric Boolean functions. As a consequence of our main result, we get that every symmetric Boolean function having an odd period
has anexponentially small correlation (inn) with the parity function. This improves a result of Smolensky [12] restricted to symmetric Boolean functions: the correlation
between parity and any circuit consisting of a Mod
q
gate over AND gates of small fan-in, whereq is odd and the function computed by the sum of the AND gates is symmetric, is bounded by 2−Ω(n).
In addition, we find that for a large class of symmetric functions the correlation with parity isidentically zero for infinitely manyn. We characterize exactly those symmetric Boolean functions having this property.
This research was supported in part by NSF Grant CCR-9057486. Jin-Yi Cai was supported in part by an Alfred T. Sloan Fellowship
in computer science. The work of F. Green was done in part while visiting Princeton University, while the work of T. Thierauf
was done in part while visiting Princeton University and the University of Rochester. The third author was supported in part
by DFG Postdoctoral Stipend Th 472/1-1 and by NSF Grant CCR-8957604. 相似文献