@incollection{Karpinski/97a,
AUTHOR = {Karpinski, Marek},
TITLE = {Polynomial time approximation schemes for some dense instances of $NP$-hard optimization problems},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {1-14},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Cooper-Frieze-Mehlhorn-Priebe/97,
AUTHOR = {Cooper, Colin and Frieze, Alan and Mehlhorn, Kurt and Priebe, Volker},
TITLE = {Average-case complexity of shortest-paths problems in the vertex-potential model},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {15-26},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Levcopoulos-Gudmundsson/97,
AUTHOR = {Levcopoulos, Christos and Gudmundsson, Joachim},
TITLE = {Approximation algorithms for covering polygons with squares and similar problems},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {27-41},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Kreuter-Nierhoff/97,
AUTHOR = {Kreuter, Bernd and Nierhoff, Till},
TITLE = {Greedily approximating the $r$-independent set and $k$-center problems on random instances},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {43-53},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Arora/97a,
AUTHOR = {Arora, Sanjeev},
TITLE = {Nearly linear time approximation schemes for Euclidean TSP and other geometric problems},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {55-55},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Tetali-Vempala/97,
AUTHOR = {Tetali, Prasad and Vempala, Santosh},
TITLE = {Random sampling of Euler tours},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {57-66},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Goldreich-Safra/97,
AUTHOR = {Goldreich, Oded and Safra, Shmuel},
TITLE = {A combinatorial consistency lemma with application to proving the PCP theorem},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {67-84},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Rudich/97,
AUTHOR = {Rudich, Steven},
TITLE = {Super-bits, demi-bits, and $N{\tilde P}$/qpoly natural proofs},
BOOKTITLE = {Proceedings of the First International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {85-93},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'e}},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=1269&spage=85},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Saks-Zhou/97,
AUTHOR = {Saks, Michael and Zhou, Shiyu},
TITLE = {Sample spaces with small bias on neighborhoods},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {95-109},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Crescenzi-Kann/97,
AUTHOR = {Crescenzi, P. and Kann, V.},
TITLE = {Approximation on the Web: A compendium of $NP$ optimization problems},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {111-118},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Schulz-Skutella/97,
AUTHOR = {Schulz, Andreas S. and Skutella, Martin},
TITLE = {Random-based scheduling --- New approximations and $LP$ lower bounds},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {119-133},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Peinado-Lengauer/97,
AUTHOR = {Peinado, Marcus and Lengauer, Thomas},
TITLE = {``Go with the Winners'' generators with applications to molecular modeling},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {135-149},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Hong-Birget/97,
AUTHOR = {Hong, Dawei and Birget, Jean-Camille},
TITLE = {Probabilistic approximation of some $NP$ optimization problems by finite-state machines},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {151-164},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Impagliazzo/97,
AUTHOR = {Impagliazzo, Russell},
TITLE = {Using hard problems to derandomize algorithms: An incomplete survey},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {165-173},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Ambainis-Freivalds-Karpinski/97,
AUTHOR = {Ambainis, Andris and Freivalds, R{\=u}si{\c{n}}{\v{s}} and Karpinski, Marek},
TITLE = {Weak and strong recognition by 2-way randomized automata},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {175-185},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Kaneps-Geidmanis-Freivalds/97,
AUTHOR = {Ka{\c{n}}eps, J{\=a}nis and Geidmanis, Dainis and Freivalds, R{\=u}si{\c{n}}{\v{s}}},
TITLE = {Tally languages accepted by Monte Carlo pushdown automata},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {187-195},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Kautz/97,
AUTHOR = {Kautz, Steven M.},
TITLE = {Resource-bounded randomness and compressibility with respect to nonuniform measures},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {197-211},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}
@incollection{Wang/97g,
AUTHOR = {Wang, Yongge},
TITLE = {Randomness, stochasticity and approximations},
BOOKTITLE = {Proceedings of the 1st International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'97 (Bologna, Italy, July 11-12, 1997)},
SERIES = {LNCS},
VOLUME = {1269},
PAGES = {213-225},
YEAR = {1997},
EDITOR = {Rolim, Jos{\'{e}}},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg-New York-Barcelona-Budapest-Hong Kong-London-Milan-Paris-Santa Clara-Singapore-Tokyo},
}