Final Program, ISAAC'00, Taipei, Taiwan

[Hsueh-I Lu]

  11th Annual International Symposium on Algorithms and Computation
			     (ISAAC 2000)
			    Final Program
			December 18--20, 2000
	  Institute of Information Science, Academia Sinica
			    Taipei, Taiwan
		http://www.iis.sinica.edu.tw/isaac00/
--------				   
Sponsors
--------
Academia Sinica
National Science Council of ROC
ACM Taipei/Taiwan Chapter
The Inst. of Info. and Comput. Mach. (IICM)
-----------------
Program Committee
-----------------
Co-chair: D. T. Lee, Academia Sinica
Co-chair: Shang-Hua Teng, Univ. of Illinois
Helmut Alt, Free University of Berlin 
Nina Amenta, Univ. of Texas at Austin 
Gen-Huey Chen, National Taiwan Univ.
Jeff Erickson, University of Illinois 
Giuseppe Italiano, University of Rome 
Kazuo Iwama, Kyoto University 
Marcos Kiwi, University of Chile 
Ming-Tat Ko, Academia Sinica 
Kurt Mehlhorn, Max Planck Institute  
Michael D. Mitzenmacher, Harvard Univ. 
Kunsoo Park, Seoul National University 
Tadao Takaoka, University of Canterbury 
Takeshi Tokuyama, Sendi University 
Peng-Jun Wan, Illinois Inst. of Technology 
Derick Wood, Hong Kong Univ. Sci. & Tech.
===================
Sunday, December 17
===================
6:30--9PM Reception, Western-style Resturant, Academia Sinica 
          (located right behind the Activity Center)
===================
Monday, December 18
===================
9:00--10:00 Invited Talk (Chair: D.T. Lee)
Voronoi-Based Systems of Coordinates and Surface Reconstruction, 
Jean-Daniel Boissonnat (INRIA, Unit\'e de Sophia Antipolis).  
------------------------------------------
10:30--12:00 (Chair: Kunsoo Park) 
Session 1A: Algorithms and Data Structures
------------------------------------------
Strategies for Hotlink Assignments
(P. Bose, J. Czyzowicz, L. Gasieniec, E. Kranakis, D. Krizanc, 
A. Pelc, M. Martin)

A New Competitive Analysis of Randomized Caching
(C. Law and C. E. Leiserson)

Online Routing in Convex Subdivisions
(P. Bose, A. Brodnik, S. Carlsson, E. Demaine, R. Fleischer, A. Lopez-Ortiz, P. Morin, J. Munro)
------------------------------------------
10:30--12:00 (Chair: Xiaotie Deng)
Session 1B: Combinatorial Optimization
------------------------------------------
A Simple Linear-Time Approximation Algorithm for Multi-processor Job
Scheduling on Four Processors (J. Huang, J. Chen, S. Chen)

Classification of Various Neighborhood Operations for the Nurse
Scheduling Problem (T. Osogami, H. Imai)

Optimal Bid Sequences for Multiple-Object Auctions with Unequal
Budgets (Y. Chen, M.-Y. Kao, H.-I. Lu)
------------------------------------------
2:00--3:30 (Chair: Takao Nishizeki)
Session 2A: Algorithms and Data Structures
------------------------------------------
Coping with Delays and Time-Outs in Binary Search Procedures
(F. Cicalese, U. Vaccaro)

Some Formal Analysis of Rocchio's Similarity-Based Relevance Feedback
Algorithm (Z. Chen, B. Zhu)

Reasoning with Ordered Binary Decision Diagrams (T. Horiyama,
T. Ibaraki)
------------------------------------------
2:00--3:30 (Chair: Kazuo Iwama)
Session 2B: Approximation and Randomized Algorithms
------------------------------------------
On Approximating Minimum Vertex Cover for Graphs with Perfect Matching
(J. Chen, I. A. Kanj)

2-Approximation Algorithm for Path Coloring on Trees of Rings
(X. Deng, G. Li, W. Zang, Y. Zhou)

An Approximate Algorithm for the Weighted Hamiltonian Path Completion
Problem on a Tree (Q. S. Wu, C. L. Lu, R. C. T. Lee)
------------------------------------------
4:00--5:30 (Chair: Helmut Alt)
Session 3A: Algorithms and Data Structures
------------------------------------------
Finding Independent Spanning Trees in Partial $k$-Trees (X. Zhou,
T. Nishizeki)

On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover
(R. Niedermeier, P. Rossmanith)

Constructive Linear-Time Algorithms for Small Cutwidth and
Carving-Width (D. M. Thilikos, M. J. Serna, H. L. Bodlaender)
------------------------------------------
4:00--5:30 (Chair: Yuh-Dauh Lyuu)
Session 3B: Approximation and Randomized Algorithms
------------------------------------------
Approximation Algorithms for the Maximum Power Consumption Problem on
Combinatorial Circuits (T. Asano, M. M. Halld\'orsson, K. Iwama,
T. Matsuda)

A Simple and Quick Approximation Algorithm for Traveling Salesman
Problem in the Plane (N. Kubo, K. Muramoto, S. Shimozono)

Simple Algorithms for a Weighted Interval Selection Problem
(T. Erlebach, F. C.R. Spieksma)
====================
Tuesday, December 19
====================
9:00-10:00 Invited Talk (Chair: Wen-Lian Hsu) 
Essentially Every Unimodular Matrix Defines an Expander, Jin-Yi Cai
(State University of New York at Buffalo, University of Wisconsin)
------------------------------------------
10:30--12:00 (Chair: Hsu-Chun Yen)
Session 4A: Graph Drawing and Algorithms
------------------------------------------
Efficient Minus and Signed Domination in Graphs (C. L. Lu,
S.-L. Peng, C. Y. Tang)

Convex Grid Drawings of Four-Connected Plane Graphs (K. Miura,
S.-i. Nakano, T. Nishizeki)

An Algorithm for Finding Three-Dimensional Symmetry in Series-Parallel
Digraphs (S.-H. Hong, P. Eades)
------------------------------------------
10:30--12:00 (Chair: Takeshi Tokuyama)
Session 4B: Automata, Cryptography, and Complexity Theory
------------------------------------------
Undecidability Results for Monoids with Linear-Time Decidable Word
Problems (M. Katsura, Y. Kobayashi, F. Otto)

Secret Key Exchange Using Random Deals of Cards on Hierarchical
Structures (R. Yoshikawa, S. Guo, K. Motegi, Y. Igarashi)

Derandomizing Arthur-Merlin Games under Uniform Assumptions (C.-J. Lu)
------------------------------------------
2:00--3:30 (Chair: Tao Jiang)
Session 5A: Algorithms and Data Structures
------------------------------------------
A Near Optimal Algorithm for Vertex Connectivity Augmentation
(B. Jackson, T. Jordan)

Simultaneous Augmentation of Two Graphs to an $\ell$-Edge-Connected
Graph and a Biconnected Graph (T. Ishii, H. Nagamochi)

Location Problems Based on Node-Connectivity and Edge-Connectivity
between Nodes and Node-Subsets (H. Ito, M. Ito, Y. Itatsu, H. Uehara,
M. Yokoyama)
------------------------------------------
2:00--3:30 (Chair: Kuo-Liang Chung)]
Session 5B: Parallel and Distributed Algorithms
------------------------------------------
An Intuitive and Effective New Representation for Interconnection
Network Structures (J. Chen, W. Jia, L. Liu, S. Chen)

Randomized Leader Election Protocols in Radio Networks with no Collision Detection
(K. Nakano, S. Olariu)

Deterministic Broadcasting Time with Partial Knowledge of the Network
(G. De Marco, A. Pelc)
------------------------------------------
4:00-5:30 (Chair: Danny Z. Chen)
Session 6A: Algorithms and Data Structures
------------------------------------------
Minimizing Makespan in Batch Machine Scheduling (C. K. Poon, P. Zhang)

Preemptive Parallel Task Scheduling in O(n)+poly(m) Time (K. Jansen,
L. Porkolab)

Compressed Text Databases with Efficient Query Algorithms based on the
Comressed Suffix Array (K. Sadakane)
------------------------------------------
4:00-5:30 (Chair: Yaw-Ling Lin)
Session 6B: Computational Geometry
------------------------------------------
A Better Lower Bound for Two-Circle Point Labeling (A. Wolff, M. Thon,
Y. Xu)

Voronoi Diagram of a Circle Set Constructed from Voronoi Diagram of a
Point Set (D.-S. Kim, D. Kim, K. Sugihara)

An Improved Algorithm for Subdivision Traversal without Extra Storage
(P. Bose, P. Morin)
-------------------------------------------------
6:30-10:00 PM Banquet, Business Meeting, Karaokey
(Lai Lai Sheraton Hotel, Downtown Taipei)
-------------------------------------------------
======================
Wednesday, December 20
======================
------------------------------------------
9:00-10:30 (Chair: Tadao Takaoka)
Session 7A: Algorithms and Data Structures
------------------------------------------
Generalized H-coloring of Graphs (P. Kristiansen, J. A. Telle)

Finding a Two-Core of a Tree in Linear Time (B.-F. Wang, J.-J. Lin)

Unbalanced and Hierarchical Bipartite Matchings with Applications to
Labeled Tree Comparsion (M.-Y. Kao, T.-W. Lam, W.-K. Sung, H.-F. Ting)
------------------------------------------
9:00-10:30 (Chair: Prosenjit Bose)
Session 7B: Computational Geometry
------------------------------------------
Optimal Beam Penetrations in Two and Three Dimensions (D. Z. Chen,
X. (S.) Hu, J. Xu)

Searching a Simple Polygon by a $k$-searcher (X. Tan)

Characterization of Rooms Searchable by Two Guards (S.-M. Park,
J.-H. Lee, K.-Y. Chwa)
------------------------------------------
11:00--12:00 (Chair: Kun-Mao Chao)
Session 8A: Computational Biology
------------------------------------------
Improved Phylogeny Comparisons: Non-Shared Edges, Nearest Neighbor
Interchanges, and Subtree Transfers (W.-K. Hon, M.-Y. Kao, T.-W. Lam)

Phylogenetic $k$-Root and Steiner $k$-Root (G.-H. Lin, P. E. Kearney,
T. Jiang)
--------------------------------------
11:00--12:00 (Chair: Rudolf Fleischer)
Session 8B: Computational Geometry
--------------------------------------
Maintenance of a Piercing Set for Intervals with Applications
(M. J. Katz, F. Nielsen, M. Segal)

Optimal Polygon Cover Problems and Applications
(D. Z. Chen, X. (S.) Hu, X. Wu)
-----------------
2:00 -- Excursion
-----------------


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.