@article{Chen-Miranda/01,
AUTHOR = {Chen, Jianer and Miranda, Antonio},
TITLE = {A polynomial time approximation scheme for general multiprocessor job scheduling},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {1-17},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {job scheduling, approximation algorithm, polynomial time approximation scheme, multiprocessor processing},
URL = {http://dx.doi.org/10.1137/S0097539798348110},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kao-Lam-Sung-Ting/01a,
AUTHOR = {Kao, Ming-Yang and Lam, Tak-Wah and Sung, Wing-Kin and Ting, Hing-Fung},
TITLE = {A decomposition theorem for maximum weight bipartite matchings},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {18-26},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {all-cavity matchings, maximum weight matchings, minimum weight covers, graph algorithms, unfolded graphs},
URL = {http://dx.doi.org/10.1137/S0097539799361208},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Althaus-Mehlhorn/01,
AUTHOR = {Althaus, Ernst and Mehlhorn, Kurt},
TITLE = {Traveling Salesman-based curve reconstruction in polynomial time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {27-66},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {traveling salesman, polynomial time, curve reconstruction},
URL = {http://dx.doi.org/10.1137/S0097539700366115},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Liu-Aiello-Bhatt/01,
AUTHOR = {Liu, Pangfeng and Aiello, William and Bhatt, Sandeep},
TITLE = {Tree search on an atomic model for message passing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {67-85},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {parallel tree search, parallel communication model, randomized algorithm},
URL = {http://dx.doi.org/10.1137/S0097539799358070},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Leonardi-Marchetti-Spaccamela-Presciutti-Rosen/01,
AUTHOR = {Leonardi, Stefano and Marchetti-Spaccamela, Alberto and Presciutti, Alessio and Ros{\'{e}}n, Adi},
TITLE = {On-line randomized call control revisited},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {86-112},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {on-line algorithms, competitive analysis, randomized algorithms, call admission control},
URL = {http://dx.doi.org/10.1137/S0097539798346706},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Flum-Grohe/01,
AUTHOR = {Flum, J{\"{o}}rg and Grohe, Martin},
TITLE = {Fixed-parameter tractability, definability, and model-checking},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {113-145},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {parameterized complexity, model-checking, descriptive complexity},
URL = {http://dx.doi.org/10.1137/S0097539799360768},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chekuri-Motwani-Natarajan-Stein/01,
AUTHOR = {Chekuri, C. and Motwani, R. and Natarajan, B. and Stein, C.},
TITLE = {Approximation techniques for average completion time scheduling},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {146-166},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithms, scheduling, parallel machine scheduling, release dates, precedence constraints},
URL = {http://dx.doi.org/10.1137/S0097539797327180},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Luby-Randall-Sinclair/01,
AUTHOR = {Luby, Michael and Randall, Dana and Sinclair, Alistair},
TITLE = {Markov chain algorithms for planar lattice structures},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {167-192},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {markov chains, rapid mixing, dimer systems, domino tilings, eulerian orientations},
URL = {http://dx.doi.org/10.1137/S0097539799360355},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cucker-Grigoriev/01a,
AUTHOR = {Cucker, Felipe and Grigoriev, Dima},
TITLE = {There are no sparse $NP_w$-hard sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {193-198},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {structural complexity, real number computations},
URL = {http://dx.doi.org/10.1137/S0097539700379346},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kucera-Slaman/01,
AUTHOR = {Ku{\v{c}}era, Anton{\'{\i}}n and Slaman, Theodore A.},
TITLE = {Randomness and recursive enumerability},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {199-211},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {random real, chaitin, kolmogorov, $\omega$-number},
URL = {http://dx.doi.org/10.1137/S0097539799357441},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bouchitte-Todinca/01,
AUTHOR = {Bouchitt{\'{e}}, Vincent and Todinca, Ioan},
TITLE = {Treewidth and minimum fill-in: Grouping the minimal separators},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {212-232},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {graph algorithms, treewidth, minimum fill-in, weakly triangulated graphs},
URL = {http://dx.doi.org/10.1137/S0097539799359683},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Boyar-Larsen-Nielsen/01,
AUTHOR = {Boyar, Joan and Larsen, Kim S. and Nielsen, Morten N.},
TITLE = {The accommodating function: A generalization of the competitive ratio},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {233-258},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {on-line algorithms, performance measures, competitive analysis, restricted adversaries, bin packing, seat reservations, flow time},
URL = {http://dx.doi.org/10.1137/S0097539799361786},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Sawada/01,
AUTHOR = {Sawada, Joe},
TITLE = {Generating bracelets in constant amortized time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {259-268},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {bracelet, necklace, cat algorithm, generate, forbidden substring},
URL = {http://dx.doi.org/10.1137/S0097539700377037},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Eiter-Ibaraki-Makino/01,
AUTHOR = {Eiter, Thomas and Ibaraki, Toshihide and Makino, Kazuhisa},
TITLE = {Disjunctions of Horn theories and their cores},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {269-288},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {computational issues in artificial intelligence, logic in computer science, horn theory},
URL = {http://dx.doi.org/10.1137/S0097539799350840},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hell-Shamir-Sharan/01,
AUTHOR = {Hell, Pavol and Shamir, Ron and Sharan, Roded},
TITLE = {A fully dynamic algorithm for recognizing and representing proper interval graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {289-305},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {fully dynamic algorithms, graph algorithms, proper interval graphs, lower bounds},
URL = {http://dx.doi.org/10.1137/S0097539700372216},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Csuros-Kao/01,
AUTHOR = {Cs\H{u}r{\"{o}}s, Mikl{\'{o}}s and Kao, Ming-Yang},
TITLE = {Provably fast and accurate recovery of evolutionary trees through harmonic greedy triplets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {306-322},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {evolutionary trees, the Jukes-Cantor model of evolution, computational learning, harmonic greedy triplets},
URL = {http://dx.doi.org/10.1137/S009753970037905X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen/01g,
AUTHOR = {Chen, Jing-Chao},
TITLE = {Proportion extend sort},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {1},
PAGES = {323-330},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {algorithm, partition, sort, quick sort, insertion sort},
URL = {http://dx.doi.org/10.1137/S0097539798342903},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bar-Noy-Guha-Naor-Schieber/01,
AUTHOR = {Bar-Noy, Amotz and Guha, Sudipto and Naor, Joseph (Seffi) and Schieber, Baruch},
TITLE = {Approximating the throughput of multiple machines in real-time scheduling},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {331-352},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithms, scheduling, real-time scheduling, multiple machines scheduling, parallel machines scheduling, throughput},
URL = {http://dx.doi.org/10.1137/S0097539799354138},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pagh/01,
AUTHOR = {Pagh, Rasmus},
TITLE = {Low redundancy in static dictionaries with constant query time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {353-363},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {information retrieval, dictionary, hashing, redundancy, compression},
URL = {http://dx.doi.org/10.1137/S0097539700369909},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Henzinger-King/01,
AUTHOR = {Henzinger, Monika R. and King, Valerie},
TITLE = {Maintaining minimum spanning forests in dynamic graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {364-374},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {dynamic graph, graph algorithm, minimum spanning tree, data structure},
URL = {http://dx.doi.org/10.1137/S0097539797327209},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cryan-Goldberg-Goldberg/01,
AUTHOR = {Cryan, Mary and Goldberg, Leslie Ann and Goldberg, Paul W.},
TITLE = {Evolutionary trees can be learned in polynomial time in the two-state general Markov model},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {375-397},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {computational learning theory, evolutionary trees, pac-learning, learning of distributions, markov model},
URL = {http://dx.doi.org/10.1137/S0097539798342496},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vadhan/01,
AUTHOR = {Vadhan, Salil P.},
TITLE = {The complexity of counting in sparse, regular, and planar graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {398-427},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {$\#\cal p$, completeness, matchings, vertex covers, independent sets, fibonacci numbers, polynomial interpolation},
URL = {http://dx.doi.org/10.1137/S0097539797321602},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rodl-Rucinnski-Wagner/01,
AUTHOR = {R{\"{o}}dl, Vojtech and Ruci{\'n}nski, Andrzej and Wagner, Michelle},
TITLE = {Matchings meeting quotas and their impact on the blow-up lemma},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {428-446},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {$\epsilon$-regular graphs, perfect matchings, conditional probabilities, randomized algorithms, derandomization, blow-up lemma},
URL = {http://dx.doi.org/10.1137/S0097539700371053},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Kao-Lyuu-Wong/01,
AUTHOR = {Chen, Gen-Huey and Kao, Ming-Yang and Lyuu, Yuh-Dauh and Wong, Hsing-Kuo},
TITLE = {Optimal buy-and-hold strategies for financial markets with bounded daily returns},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {447-459},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {buy-and-hold trading problems, balanced strategy, dollar averaging strategy, online algorithms, competitive analysis, planning games, minimax theorem, linear programming, zero-sum two-person games},
URL = {http://dx.doi.org/10.1137/S0097539799358847},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Roychowdhury-Vatan/01,
AUTHOR = {Roychowdhury, Vwani P. and Vatan, Farrokh},
TITLE = {Quantum formulas: A lower bound and simulation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {460-476},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {quantum formula, lower bound, mixed state, density matrix},
URL = {http://dx.doi.org/10.1137/S0097539700370965},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Naor-Zosin/01,
AUTHOR = {Naor, Joseph (Seffi) and Zosin, Leonid},
TITLE = {A 2-approximation algorithm for the directed multiway cut problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {477-482},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithms, combinatorial optimization, multicommodity flow, multiway cut, directed graph},
URL = {http://dx.doi.org/10.1137/S009753979732147X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Merkle/01,
AUTHOR = {Merkle, Wolfgang},
TITLE = {The global power of additional queries to $P$-random oracles},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {483-495},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {separation of reducibilities, random sets, resource-bounded measure, effective measure, resource-bounded reducibilities, effective reducibilities, bounded truth-table reducibility, truth-table reducibility},
URL = {http://dx.doi.org/10.1137/S0097539700366711},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mulmuley-Sohoni/01,
AUTHOR = {Mulmuley, Ketan D. and Sohoni, Milind},
TITLE = {Geometric complexity theory I: An approach to the $P$ vs. $NP$ and related problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {496-526},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {geometric invariant theory, computational complexity, algebraic geometry, representation theory, stability},
URL = {http://dx.doi.org/10.1137/S009753970038715X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bar-Noy-Freund-Naor/01,
AUTHOR = {Bar-Noy, Amotz and Freund, Ari and Naor, Joseph (Seffi)},
TITLE = {On-line load balancing in a hierarchical server topology},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {527-549},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {on-line algorithms, load balancing, hierarchical servers, temporary jobs, resource procurement},
URL = {http://dx.doi.org/10.1137/S0097539798346135},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ergun-Kumar-Rubinfeld/01,
AUTHOR = {Erg{\"{u}}n, Funda and Kumar, S. Ravi and Rubinfeld, Ronitt},
TITLE = {Checking approximate computations of polynomials and functional equations},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {550-576},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {program testing, approximate testing, property testing, polynomials, functional equations},
URL = {http://dx.doi.org/10.1137/S0097539798337613},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hoffmann-Icking-Klein-Kriegel/01,
AUTHOR = {Hoffmann, Frank and Icking, Christian and Klein, Rolf and Kriegel, Klaus},
TITLE = {The polygon exploration problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {577-600},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {angle hull, competitive strategy, computational geometry, curve length, motion planning, navigation, on-line algorithm, optimum watchman tour, polygon, robot},
URL = {http://dx.doi.org/10.1137/S0097539799348670},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Garg-Tamassia/01,
AUTHOR = {Garg, Ashim and Tamassia, Roberto},
TITLE = {On the computational complexity of upward and rectilinear planarity testing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {601-625},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {graph drawing, planar drawing, upward drawing, rectilinear drawing, orthogonal drawing, layout, ordered set, planar graph, algorithm, computational complexity, $NP$-complete problem, approximation algorithm},
URL = {http://dx.doi.org/10.1137/S0097539794277123},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Leighton-Lu-Rao-Srinivasan/01,
AUTHOR = {Leighton, Tom and Lu, Chi-Jen and Rao, Satish and Srinivasan, Aravind},
TITLE = {New algorithmic aspects of the local lemma with applications to routing and partitioning},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {626-641},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {disjoint paths, randomized rounding, integer programming},
URL = {http://dx.doi.org/10.1137/S0097539700379760},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Attiya-Fouren/01,
AUTHOR = {Attiya, Hagit and Fouren, Arie},
TITLE = {Adaptive and efficient algorithms for lattice agreement and renaming},
JOURNAL = {SIAM J. Comput.},
VOLUME = {31},
NUMBER = {2},
PAGES = {642-664},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {shared-memory systems, wait-free computation, atomic read/write registers, renaming, lattice agreement, atomic snapshots},
URL = {http://dx.doi.org/10.1137/S0097539700366000},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Agarwal-Wang/01,
AUTHOR = {Agarwal, Pankaj K. and Wang, Hongyan},
TITLE = {Approximation algorithms for curvature-constrained shortest paths},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1739-1772},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {robotics, motion planning, configuration space, approximation algorithms},
URL = {http://dx.doi.org/10.1137/S0097539796307790},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Shahrokhi-Sykora-Szekely-Vrto/01,
AUTHOR = {Shahrokhi, Farhad and S{\'{y}}kora, Ondrej and Sz{\'{e}}kely, L{\'{a}}szl{\'{o}} A. and Vr{\u{t}}o, Imrich},
TITLE = {On bipartite drawings and the linear arrangement problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1773-1789},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {bipartite drawing, bipartite crossing number, biplanar graph, linear arrangement, approximation algorithms},
URL = {http://dx.doi.org/10.1137/S0097539797331671},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Frieze/01,
AUTHOR = {Frieze, Alan M.},
TITLE = {Edge-disjoint paths in expander graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1790-1801},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {edge-disjoint paths, expander graphs, randomized algorithms},
URL = {http://dx.doi.org/10.1137/S0097539700366103},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
NOTE = {see Erratum in SIAM J. Comp., Vol. 31, 2002, No. 3, 988-988},
}
@article{Berkman-Parnas-Sgall/01,
AUTHOR = {Berkman, Omer and Parnas, Michal and Sgall, Ji{\v{r}}{\'{\i}}},
TITLE = {Efficient dynamic traitor tracing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1802-1828},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {analysis of algorithms, asymptotic complexity, cryptography, traitor tracing},
URL = {http://dx.doi.org/10.1137/S0097539700367984},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Buhrman-Cleve-van_Dam/01,
AUTHOR = {Buhrman, Harry and Cleve, Richard and van Dam, Wim},
TITLE = {Quantum entanglement and communication complexity},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1829-1841},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {complexity theory, communication complexity, quantum computing},
URL = {http://dx.doi.org/10.1137/S0097539797324886},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Alon-Krivelevich-Newman-Szegedy/01,
AUTHOR = {Alon, Noga and Krivelevich, Michael and Newman, Ilan and Szegedy, Mario},
TITLE = {Regular languages are testable with a constant number of queries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1842-1862},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {property testing, regular languages, context-free languages},
URL = {http://dx.doi.org/10.1137/S0097539700366528},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Khanna-Sudan-Trevisan-Williamson/01,
AUTHOR = {Khanna, Sanjeev and Sudan, Madhu and Trevisan, Luca and Williamson, David P.},
TITLE = {The approximability of constraint satisfaction problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1863-1920},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {approximation algorithms, approximation classes, approximation-preserving reductions, complete problems, boolean constraint satisfaction problems, hardness of approximation},
URL = {http://dx.doi.org/10.1137/S0097539799349948},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Meleis/01,
AUTHOR = {Meleis, Waleed M.},
TITLE = {Dual-issue scheduling for binary trees with spills and pipelined loads},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1921-1941},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {scheduling algorithms, code generations, parallel functional units, registers},
URL = {http://dx.doi.org/10.1137/S009753979834610X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jiang-Kearney-Li/01,
AUTHOR = {Jiang, Tao and Kearney, Paul and Li, Ming},
TITLE = {A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1942-1961},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {dense instance, evolutionary tree, approximation algorithm, quartet method, smooth polynomial},
URL = {http://dx.doi.org/10.1137/S0097539799361683},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dyer-Goldberg-Greenhill-Jerrum-Mitzenmacher/01,
AUTHOR = {Dyer, Martin and Goldberg, Leslie Ann and Greenhill, Catherine and Jerrum, Mark and Mitzenmacher, Michael},
TITLE = {An extension of path coupling and its application to the Glauber dynamics for graph colorings},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1962-1975},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {markov chains, coupling, stopping times, graph coloring, glauber dynamics},
URL = {http://dx.doi.org/10.1137/S0097539700372708},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mereghetti-Pighizzini/01,
AUTHOR = {Mereghetti, Carlo and Pighizzini, Giovanni},
TITLE = {Optimal simulations between unary automata},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1976-1992},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {formal languages, deterministic, nondeterministic, and alternating finite state automata, unary languages},
URL = {http://dx.doi.org/10.1137/S009753979935431X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cai-Deng-Zang/01,
AUTHOR = {Cai, Mao-cheng and Deng, Xiaotie and Zang, Wenan},
TITLE = {An approximation algorithm for feedback vertex sets in tournaments},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {1993-2007},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {feedback vertex set, tournament, min-max relation, approximation algorithm},
URL = {http://dx.doi.org/10.1137/S0097539798338163},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Micciancio/01,
AUTHOR = {Micciancio, Daniele},
TITLE = {The shortest vector in a lattice is hard to approximate to within some constant},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {2008-2035},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {np-hardness, shortest vector problem, point lattices, geometry of numbers, sphere packing},
URL = {http://dx.doi.org/10.1137/S0097539700373039},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Boros-Gurvich-Khachiyan-Makino/01,
AUTHOR = {Boros, Endre and Gurvich, Vladimir and Khachiyan, Leonid and Makino, Kazuhisa},
TITLE = {Dual-bounded generating problems: Partial and multiple transversals of a hypergraph},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {2036-2050},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {transversal, independent set, hypergraph, dualization, monotone boolean function, incremental polynomial time, threshold function, data mining, maximal frequent set, minimal infrequent set},
URL = {http://dx.doi.org/10.1137/S0097539700370072},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Srinivasan-Teo/01,
AUTHOR = {Srinivasan, Aravind and Teo, Chung-Piaw},
TITLE = {A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {2051-2068},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {packet routing, approximation algorithms, linear programming, multicommodity flow, rounding theorems, randomized algorithms, covering integer programs, randomized rounding, discrete ham-sandwich theorems},
URL = {http://dx.doi.org/10.1137/S0097539798335596},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chu-La/01,
AUTHOR = {Chu, Chengbin and La, R{\'{e}}my},
TITLE = {Variable-sized bin packing: Tight absolute worst-case performance ratios for four approximation algorithms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {2069-2083},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {variable-sized bin packing, absolute worst-case performance ratios, approximation algorithms},
URL = {http://dx.doi.org/10.1137/S009753979834669X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mirkowska-Salwicki-Srebrny-Tarlecki/01,
AUTHOR = {Mirkowska, Gra{\.z}yna and Salwicki, Andrzej and Srebrny, Marian and Tarlecki, Andrzej},
TITLE = {First-order specifications of programmable data types},
JOURNAL = {SIAM J. Comput.},
VOLUME = {30},
NUMBER = {6},
PAGES = {2084-2096},
YEAR = {2001},
EDITOR = {Yannakakis, M.},
KEYWORDS = {algebraic specification, reachable algebra, data types},
URL = {http://dx.doi.org/10.1137/S0097539797322528},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}