Mayr E.W., Pr?mel H.J., Steger A. (eds.) Lectures on Proof Verification and Approximation Algorithms
Подождите немного. Документ загружается.
328 Bibliography
[Fag74]
[Fei91]
[Fei95]
[ ei96]
[Fer96]
[FG95]
[FGL+91]
[FK91]
[FK94]
[FL92]
[Fri91]
[FRSS8]
[FRS90I
R. Fagin. Generalized first-order spectra and polynomial-time rec-
ognizable sets. In SIAM-AMS Proceedings, pages 43-73, 1974.
U. Feige. On the success probability of the two provers in one-
round proof systems. In Proceedings of the 6th IEEE Symposium on
Structure in Complexity Theory, pages 116-123, 1991.
U. Feige. Error reduction by parallel repetition - the state of the
art. Technical Report CS95-32, WISDOM Technical reports in Com-
puter Science, 1995.
U. Feige. A threshold of In n for approximating set cover. In Proceed-
ings of the 28th Annual ACM Symposium on Theory of Computing,
pages 314-318, 1996.
W. Fernandez de la Vega. MAXCUT has a randomized approxima-
tion scheme in dense graphs. Random Structures and Algorithms,
8(3):187-198, 1996.
U. Feigc and M. Goemans. Approximating the value of two prover
proof systems, with applications to MAX2SAT and MAXDICUT. In
Proceedings of the 3rd Israel Symposium on the Theory of Computing
and Systems, pages 182-189, 1995.
U. Feige, S. Goldwasser, L. Lov~sz, S. Safra, and M. Szegedy. Ap-
proximating clique is almost A/'P-complete. In Proceedings of the
32nd Annual IEEE Symposium on Foundations of Computer Sci-
ence, pages 2-12, 1991.
H. Furstenberg and Y. Katznelson. A density version of the Hales-
Jewett theorem. Journal d'Analyse Mathematique, 57:64-119, 1991.
U. Feige and J. Kilian. Two-prover protocols - low error at afford-
able rates. In Proceedings of the 26th Annual ACM Symposium on
Theory of Computing, pages 172-183, 1994.
U. Feige and L. Lov~z. Two-prover one-round proof systems: Their
power and their problems. In Proceedings of the 24th Annual ACM
Symposium on Theory of Computing, pages 733-744, 1992.
J. ~iedman. On the second eigenvalue and random walks in random
d-regular graphs. Combinatorica, 11(4):331-362, 1991.
L. Fortnow, J. Rompel, and M. Sipser. On the power of multi-prover
interactive protocols. In Proceedings of the 3rd IEEE Symposium on
Structure in Complexity Theory, pages 156-161, 1988.
L. Fortnow, J. Rompel, and M. Sipser. Errata for on the power
of multi-prover interactive protocols. In Proceedings of the 5th
IEEE Symposium on Structure in Complexity Theory, pages 318-
319, 1990.
Bibliography 329
[FV96]
[FW91]
[GG81]
[GGJ76]
[Gi1931
[GJ79]
[Goe97]
[Go195]
[Gra90]
[GS92]
[GvL861
[GW94a]
[GW94b]
[GW95]
U. Feige and O. Verbitsky. Error reduction by parallel repetition - A
negative result. In Proceedings of the 11th Annual IEEE Conference
on Computational Complexity Theory, 1996.
M. Formann and F. Wagner. A packing problem with applications to
lettering of maps. In Proceedings of the 7th Annual A CM Symposium
on Computational Geometry, pages 281--288, 1991.
O. Gabber and Z. Galil. Explicit constructions of linear-sized super-
concentrators. Journal of Computer and System Sciences, 22:407-
420, 1981.
M.R. Garey, R.L. Graham, and D.S. Johnson. Some AfP-complete
geometric problems. In Proceedings of the 8th Annual ACM Sym-
posium on Theory of Computing, pages 10-22, 1976.
D. Gillman. A Chernoff bound for random walks on expanders. In
Proceedings of the 3$th Annual IEEE Symposium on Foundations
of Computer Science, pages 680-691, 1993.
M.R. Garey and D.S. Johnson. Computers and Intractability. A
Guide to the Theory of AfT~-Completeness. W.H. Freeman and Com-
pany, 1979.
M.X. Goemans. Semidefinite programming in combinatorial opti-
mization. In Proceedings of the 16th International Symposium on
Mathematical Programming, 1997.
O. Goldreich. Probabilistic proof systems (survey). Technical re-
port, Department of Computer Science and Applied Mathematics,
Weizmann Institute of Science, 1995.
R.M. Gray. Entropy and Information Theory. Springer-Verlag, 1990.
P. Gemmell and M. Sudan. Highly resilient correctors for polyno-
mials. Information Processing Letters, 43:169-174, 1992.
G.H. Golub and C.F. van Loan. Matrix Computations. North Oxford
Academic, 1986.
M.X. Goemans and D.P. Williamson..878 approximation algorithms
for MAXCUT
and
MAX2SAT. In
Proceedings of the 26th Annual
ACM Symposium on Theory of Computing, pages 422-431, 1994.
M.X. Goemans and D.P. Williamson. New 3/4-approximation algo-
rithms for the maximum satisfiahility problem. SIAM Journal on
Discrete Mathematics, 7:656-666, 1994.
M.X. Goemans and D.P. Williamson. Improved approximation algo-
rithms for maximum cut and satisfiability problems using semidefi-
nite programming. Journal of the ACM, 42:1115-1145, 1995.
330 Bibliography
[H~s96a]
[H~96b]
[H~s97a]
[H~97b]
[HL96]
[HN79]
[Hoe63]
[HPS94]
[HS85]
[IK75]
[Joh74]
[Kar72]
[Kar84]
J. HLstad. Clique is hard to approximate within n x-e. In Proceedings
of the 37th Annual IEEE Symposium on Foundations of Computer
Science, pages 627-636, 1996.
J. HLstad. Testing of the long code and hardness for clique. In Pro-
ceedings of the 28th Annual ACM Symposium on Theory of Com-
puting, pages 11-19, 1996.
J. Hs Clique is hard to approximate within n 1-~. Technical
Report TR97-038, Electronic Colloquium on Computational Com-
plexity, 1997. An earlier version was presented in Proceedings of the
37th Annual IEEE Symposium on Foundations of Computer Science
1996, pp. 627-636.
J. H~stad. Some optimal inapproximability results. In Proceedings
of the 29th Annual ACM Symposium on Theory of Computing, pages
1-10, 1997. Also appeared as Technical Report TR97-037, Electronic
Colloquium on Computational Complexity.
T. Hofmeister and H. Lehnann. A combinatorial design approach
to MAXCUT. Random Structures and Algorithms, 9(1-2):163-175,
1996.
W. Hsu and G. Nemhauser. Easy and hard bottleneck location
problems. Discrete Applied Mathematics, 1:209-216, 1979.
W. Hoeffding. Probability inequalities for sums of bounded random
variables. Journal of the American Statistical Association, 58:13-30,
1963.
S. Hougardy, H.J. PrSmel, and A. Steger. Probabilistically check-
able proofs and their consequences for approximation algorithms.
Discrete Mathematics, 136:175-223, 1994.
D.S. Hochbanm and D. Shmoys. A best possible heuristic for ttle
k-center problem. Mathematics of Operations Research, 10:180-184,
1985.
O.H. Ibarra and C.E. Kim. Fast approximation algorithms for the
knapsack and sum of subsets problems. Journal of the ACM, 22:463-
468, 1975.
D.S. Johnson. Approximation algorithms for combinatorial prob-
lems. Journal of Computer and System Sciences, 9:256-278, 1974.
R.M. Karp. Reducibility among combinatorial problems. In R.E.
Miller and J.W. Thatcher, editors, Complexity of Computer Com-
putations, pages 85-103. Plenum Press, 1972.
N. Karmarkar. A new polynomial-time algorithm for linear pro-
gramming. Combinatorica, 4(4):373-395, 1984.
Bibliography 331
[Kar91]
[Kar96]
[Kha79]
[KK82]
[KL96]
[KMS94]
[KMSV94]
[Knu81]
[KR90]
[KZ97]
[LFKN92]
[LMN93]
[LN87]
R.M. Karp. An introduction to randomized algorithms.
Discrete
Applied Mathematics,
34:165-201, 1991.
H.J. Karloff. How good is the Goemans-Williamson MAXCUT al-
gorithm? In
Proceedings of the 28th Annual ACM Symposium on
Theory o] Computing,
pages 427-434, 1996.
L.G. Khachian. A polynomial algorithm in linear programming.
Soviet Mathematics Doklady,
20:191-194, 1979.
N. Karmarkar and R.M. Karp. An efficient approximation scheme
for the one-dimensional bin packing problem. In
Proceedings of the
23rd Annual IEEE Symposium on Foundations of Computer Sci-
ence,
pages 312-320, 1982.
P. Klein and H.-I. Lu. Efficient approximation algorithms for
semidefinite programs arising from MAXCUT and COLORING. In
Proceedings of the 28th Annual A CM Symposium on Theory of Com-
puting,
pages 338-347, 1996.
D. Karger, R. Motwani, and M. Sudan. Approximate graph coloring
by semidefinite programming. In
Proceedings of the 35th Annual
IEEE Symposium on Foundations of Computer Science,
pages 2-
13, 1994.
S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic
versus computational views of approximability. In
Proceedings of
the 26th Annual ACM Symposium on Theory of Computing,
pages
819-830, 1994.
D.E. Knuth.
The Art of Computer Programming, Vol. 2, Seminu-
merical Algorithms.
Addison-Wesley, 2nd edition, 1981.
R.M. Karp and V. Ramachandran. Parallel algorithms for shared-
memory machines. In J. van Leeuwen, editor,
Handbook of Theoret-
ical Computer Science, Vol. A, Algorithms and Complexity,
pages
869-941. Elsevier, 1990.
M. Karpinski and A. Zelikovsky. Approximating dense cases of cov-
ering problems. Technical Report TR97-004, Electronic Colloquium
on Computational Complexity, 1997.
C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods
for interactive proof systems.
Journal of the ACM,
39(4):859-868,
1992.
N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits,
Fourier transform and learnability.
Journal of the ACM,
40(3):607-
620, 1993.
R. Lidl and H. Niederreiter.
Finite Fields.
Cambridge University
Press, 1987.
332 Bibliography
[Lov75]
[LPS86]
[Lub85]
[Lub86]
[LY93]
[Mar75]
[MBCV97]
[MBG+93]
[Mit96]
[MNR96]
[MR95a]
[MR95b]
L. Lov~sz. On the ratio of the optimal integral and fractional covers.
Discrete Mathematics,
13:383-390, 1975.
A. Lubotzky, R. Phillips, and P. Sarnak. Explicit expanders and the
Ramanujan conjectures. In
Proceedings of the 18th Annual ACM
Symposium on Theory of Computing,
1986.
M. Luby. A simple parallel algorithm for the maximal independent
set problem. In
Proceedings of the 17th Annual ACM Symposium
on Theory of Computing,
pages 1-10, 1985.
M. Luby. A simple parallel algorithm for the maximal independent
set problem.
SIAM Journal on Computing,
15(4):1036-1053, 1986.
C. Lund and M. Yannakakis. On the hardness of approximating
minimization problems. In
Proceedings of the 25th Annual ACM
Symposium on Theory of Computing,
pages 286-293, 1993. Also
appears in:
Journal of the ACM
41: 960-981, 1994.
G.A. Margulis. Explicit construction of concentrators.
Problems of
Information 2],ansmission,
10:325-332, 1975.
J.S.B. Mitchell, A. Blum, P. Chalasani, and S. Vempala. A constant-
factor approximation algorithm for the geometric k-MST problem in
the plane.
SIAM Journal on Computing,
pages 402-408, 1997. To
appear. Journal version of: J.S.B. Mitchell. Guillotine subdivisions
approximate polygonal subdivisions: A simple new method for the
geometric k-MsT problem. In
Proceedings of the 7th Annual ACM-
SIAM Symposium on Discrete Algorithms.
1996.
A. Menezes, I. Blake, X. Gao, R. Mullin, S. Vanstone, and T. Yag-
hoobian.
Applications of Finite Fields.
Kluwer Academic Publishers,
1993.
J.S.B. Mitchell. Guillotine subdivisions approximate polygonal sub-
divisions: Part II - a simple polynomial-time approximation scheme
for geometric k-MsT, TsP, and related problems. Technical report,
Department of Applied Mathematics and Statistics, Stony Brook,
1996.
R. Motwani, J. Naor, and P. Raghavan. Randomized approximation
algorithms in combinatorial optimization. In D.S. Hochbaum, edi-
tor,
Approximation Algorithms for Alp-hard Problems,
pages 447-
481. PWS Publishing Company, 1996.
S. Mahajan and H. Ramesh. Derandomizing semidefinite program-
ming based approximation algorithms. In
Proceedings of the 36th
Annual IEEE Symposium on Foundations of Computer Science,
pages 162-169, 1995.
R. Motwani and P. Raghavan.
Randomized Algorithms.
Cambridge
University Press, 1995.
Bibliography
333
[MS77]
[Nis96]
[NSS95]
[Pap77]
[Pap94]
[PM81}
[PS82]
[PS94]
[PT95]
[PY91]
[P g88]
[R 95]
[Raz97]
[ 92]
F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-Correct-
ing Codes. North-Holland, 1977.
N. Nisan. Extracting randomness: How and why - A survey. In Pro-
ceedings of the 11th IEEE Symposium on Structure in Complexity
Theory, 1996.
M. Naor, L. Schulman, and A. Srinivasan. Splitters and near-optimal
derandomization. In Proceedings of the 36th Annual IEEE Sympo-
sium of Foundations of Computer Science, pages 182-191, 1995.
C.H. Papadimitriou. The Euclidean traveling salesman problem is
A/P-complete. Theoretical Computer Science, 4:237-244, 1977.
C.H. Papadimitriou. Computational Complexity. Addison-Wesley,
1994.
A. Paz and S. Moran. Non deterministic polynomial optimization
problems and their approximation. Theoretical Computer Science,
15:251-277, 1981.
C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization:
Algorithms and Complexity. Prentice-Hall, 1982.
A. Polishchuk and D.A. Spielman. Nearly linear-size holographic
proofs. In Proceedings of the 26th Annual ACM Symposium on The-
ory of Computing, pages 194-203, 1994.
S. Poljak and Z. Tuza. Maximum cuts and large bipartite sub-
graphs. In Combinatorial Optimization, volume 20 of DIMACS
Series in Discrete Mathematics and Theoretical Computer Science,
pages 181-244, 1995.
C.H. Papadimitriou and M. Yannakakis. Optimization, approxi-
mation, and complexity classes. Journal of Computer and System
Sciences, 43:425-440, 1991.
P. Raghavan. Probabilistic construction of deterministic algorithms:
approximating packing integer programs. Journal of Computer and
System Sciences, 37:130-143, 1988.
R. Raz. A parallel repetition theorem. In Proceedings o] the 27th
Annual ACM Symposium on Theory o] Computing, pages 447-456,
1995.
R. Raz. A parallel repetition theorem (full version). Unpublished
manuscript, 1997.
R. Rubinfeld and M. Sudan. Self-testing polynomial functions effi-
ciently and over rational domains. In Proceedings of the 3rd Annual
A CM-SIAM Symposium on Discrete Algorithms, pages 23-32, 1992.
334 Bibliography
[RT87]
[Spe94]
[SS77]
[Sud92]
[SW97]
[Tre97]
[TSSW961
[VB96]
[Ver94]
[Ver96]
[Weg93]
[Yan92]
lYe90]
[Zuc93]
P. Raghavan and C.D. Thompson. Randomized rounding: a tech-
nique for provably good algorithms and algorithmic proofs.
Combi-
natorica,
7:365-374, 1987.
J. Spencer. Randomization, derandomization and antirandomiza-
tion: three games.
Theoretical Computer Science,
131:415-429, 1994.
R. Solovay and V. Strassen. A fast Monte-Carlo test for primal-
ity.
SIAM Journal on Computing,
6(1):84-85, 1977. An erratum
appeared in
SIAM Journal on Computing
7(1): 118, 1978.
M. Sudan.
E1~cient checking of polynomials and proofs and the
hardness of approximation problems.
PhD thesis, Department of
Computer Science, Berkeley, 1992.
M. Sudan and D.P. Williamson. Some notes on H~stad's proof.
Unpublished manuscript, 1997.
L. Trevisan.
Reductions and (Non)-Approximability.
PhD thesis,
Computer Science Department, University of Rome"La Sapienza",
1997.
L. Trevisan, G.B. Sorkin, M. Sudan, and D.P. Williamson. Gad-
gets, approximation, and linear programming. In
Proceedings of the
37th Annual IEEE Symposium on Foundations of Computer Sci-
ence,
pages 617-626, 1996.
L. Vandenberghe and S. Boyd. Semidefinite programming.
SIAM
Review,
38:49-95, 1996.
O. Verbitsky. Towards the parallel repetition conjecture. In
Pro-
ceedings of the 9th IEEE Symposium on Structure in Complexity
Theory,
pages 304-307, 1994.
O. Verbitsky. Towards the parallel repetition conjecture.
Theoretical
Computer Science,
157(2):277-282, 1996.
I. Wegener.
Theoretische lnformatik: eine algorithmenorientierte
Einfiihrung.
B.G. Teubner, 1993.
M. Yannakakis. On the approximation of maximum satisfiability. In
Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete
Algorithms,
pages 1-9, 1992.
Y. Ye. An
O(naL)
potential reduction algorithm for linear program-
ming. In
Contemporary Mathematics,
volume 114, pages 91-107,
1990.
D. Zuckerman. Alp-complete problems have a version that's hard to
approximate. In
Proceedings of the 8th IEEE Symposium on Struc-
ture in Complexity Theory,
pages 305-312, 1993. Journal version,
entitled: On unapproximable versions of A/'P-complete problems. In
SIAM Journal on Computing,
25: 1293-1304, 1996.