[ISAAC98] Call for Participation
ISAAC '98
isaac98 at jupiter.kaist.ac.kr
Thu Oct 8 23:20:53 PDT 1998
============================================================================
Ninth Annual International Symposium
on Algorithms and Computation
============================================================================
December 14-16, 1998
Riviera Hotel, Taejon, Korea
Hosted by
KAIST(Korea Advanced Institute of Science and Technology) and
KISS(Korea Information Science Society)
Sponsored by
MIC (Ministry of Information and Communication) and
KOSEF (Korea Science and Engineering Foundation)
This symposium is intended to provide a forum for researchers working in
algorithms and theory of computation. It will be held in Taejon which is
famous with hot spring resort and historical landmarks of the ancient(18
B.C-A.D.660) civilization. Taejon is also surrounded by beautiful mountains
- Kyeryoung, Daedoon and Pomun. Co-host KISS has been the professional
organization in Korea for those in computer and information sciences since
1973. The symposium is hosted in celebration of KISS's 25th anniversary.
Organization
------------
o Program Committee Chair
* Kyung-Yong Chwa (Co-Chair; KAIST, Korea)
* Oscar Ibara (Co-Chair; UC Santa Barbara, USA)
o Program Committee
* Takao Asano (Chuo U., Japan)
* Ding-Zhu Du (U. of Minnesota, USA)
* Susanne Hambrusch (Purdue U., USA)
* Hiroshi Imai (U. of Tokyo, Japan)
* Tao Jiang (McMaster U., Canada)
* Sam Kim (Kyungpook Nat. U., Korea)
* D.T. Lee (Northwestern U., USA)
* Ming Li (U. of Waterloo, Canada)
* Pandu Rangan (IIT, Madras, India)
* Sartaj Sahni (U. of Florida, USA)
* P. Spirakis (Comp. Tech. Inst., Patras, Greece)
* Roberto Tamassia (Brown U., USA)
* Shanghua Teng (U. of Illinois, USA)
* Osamu Watanabe (Tokyo Inst. Tech., Japan)
* Peter Widmayer (ETH, Zurich, Switzerland)
* Chee K. Yap (Courant Inst. NYU, USA)
* Hsu-Chun Yen (National Taiwan U., Taiwan)
o Organizing Committee Chair
* Jik Hyun Chang (Sogang U., Korea)
o Organizing Committee
* Hee-Chul Kim (Hankuk U. of Foreign Studies, Korea)
* Sang-Ho Lee (Ewha Womans U., Korea)
* Kunsoo Park (Seoul National U., Korea)
Invited Speaker
---------------
o Bernard Chazelle(Princeton University and Ecole Polytechnique)
"The Discrepancy Method"
o Roberto Tamassia(Brown University)
"Implementing Algorithms and Data Structures:
an Educational and Research Perspective"
Preliminary Program
-------------------
Sunday, December 13, 1998
6:00 Early Registration
8:00 Welcome Reception
Monday, December 14, 1998
8:30 Registration
9:20 Opening Address
Invited Presentation
9:30 The Discrepancy Method - Abstract
Bernard Chazelle (Princeton and Ecole Polytechnique)
Coffee Break: 10:30 -- 11:00
Session 1A: Geometry I
11:00 $L_\infty$ Voronoi Diagrams and Applications to VLSI Layout and
Manufacturing
Evanthia Papadopoulou
11:30 Facility Location on Terrains
Boris Aronov, Marc van Kreveld, René van Oostrum, Kasturirangan
Varadarajan
12:00 Computing Weighted Rectilinear Median and Center Set in the Presence
of Obstacles
Joonsoo Choi, Chan-Su Shin, Sung Kwon Kim
Session 1B: Complexity I
11:00 Maximizing Agreement with a Classification by Bounded or Unbounded
Number of Associated Words
Hiroki Arimura, Shinichi Shimozono
11:30 Disjunctions of Horn Theories and their Cores
Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
12:00 Checking Programs Discreetly: Demonstrating Result-Correctness
Efficiently While Concealing It
Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung
Lunch: 12:30 --- 2:00
Session 2A: Graph Drawing
2:00 Two-Layer Planarization in Graph Drawing
Petra Mutzel, René Weiskircher
2:30 Computing Orthogonal Drawings in a Variable Embedding Setting
Walter Didimo, Giuseppe Liotta
3:00 Dynamic Grid Embedding with Few Bends and Changes
Ulrik Brandes, Dorothea Wagner
Session 2B: On-line Algorithm and Scheduling
2:00 Two New Families of List Update Algorithms
Frank Schulz
2:30 An Optimal Algorithm for On-line Palletizing at Delivery Industry
J. Rethmann, E. Wanke
3:00 On-Line Scheduling of Parallel Jobs with Runtime Restrictions
Stefan Bischof, Ernst W. Mayr
Coffee Break: 3:30 -- 4:00
Session 3A: CAD/CAM and Graphics
4:00 Testing the Quality of Manufactured Disks and Cylinders
Prosenjit Bose, Pat Morin
4:30 Casting with Skewed Ejection Direction
Hee-kap Ahn, Siu-Wing Cheng, Otfried Cheong
5:00 Repairing Flaws in a Picture Based on a Geometric Representation of
a Digital Image
Tetsuo Asano, Hiro Ito, Souichi Kimura, Shigeaki Shimazu
Session 3B: Graph Algorithm I
4:00 k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary
Multigraph
Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki
4:30 Polyhedral Structure of Submodular and Posi-modular Systems
Hiroshi Nagamochi, Toshihide Ibaraki
5:00 Maximizing the Number of Connections in Optical Tree Networks
Thomas Erlebach, Klaus Jansen
Tuesday, December 15, 1998
Invited Presentation
9:00 Implementing Algorithms and Data Structures: an Educational and
Research Perspective - Abstract
Roberto Tamassia (Brown)
Session 4: Best Paper Presentation
10:00 Selecting the k Largest Elements with Parity Tests
Tak Wah Lam, Hing Fung Ting
Coffee Break: 10:30 -- 11:00
Session 5A: Randomized Algorithm
11:00 Randomized K-Dimensional Binary Search Trees
Amalia Duch, Vladimir Estivill-Castro, Conrado Martínez
11:30 Randomized O(log log n)-Round Leader Election Protocols in Packet
Radio Networks
Koji Nakano, Stephan Olariu
12:00 Random Regular Graphs with Edge Faults: Expansion through Cores
Andreas Goerdt
Session 5B: Complexity II
11:00 A Quantum Polynomial Time Algorithm in Worst Case for Simon's
Problem
Takashi Mihara, Shao Chin Sung
11:30 Generalized Graph Colorability and Compressibility of Boolean
Formulae
Richard Nock, Pascal Jappy, Jean Sallantin
12:00 On the Complexity of Free Monoid Morphisms
Klaus-Jörn Lange, Pierre McKenzie
Lunch: 12:30 --- 2:00
Session 6A: Graph Algorithm II
2:00 Characterization of Efficiently Solvable Problems on
Distance-Hereditary Graphs
Sun-Yuan Hsieh, Chin-Wen Ho, Tsan-Sheng Hsu, Ming-Tat Ko, Gen-Huey
Chen
2:30 Fast Algorithms for Independent Domination and Efficient Domination
in Trapezoid Graphs
Yaw-Ling Lin
3:00 Finding Planar Geometric Automorphisms in Planar Graphs
Seok-Hee Hong, Peter Eades, Sang-Ho Lee
Session 6B: Combinatorial Problem
2:00 A New Approach for Speeding Up Enumeration Algorithms
Takeaki Uno
2:30 Hamiltonian Decomposition of Recursive Circulants
Jung-Heum Park
3:00 Convertibility among Grid Filling Curves
Tetsuo Asano, Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama
Coffee Break: 3:30 -- 4:00
Session 7A: Geometry II
4:00 Generalized Self-Approaching Curves
Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein,
Elmar Langetepe, Günter Rote
4:30 The Steiner Tree Problem in $\lambda_4$-geometry Plane
Guo-Hui Lin, Guoliang Xue
Session 7B: Computational Biology
4:00 Approximation and Exact Algorithms for RNA Secondary Structure
Prediction and Recognition of Stochastic Context-free Languages
Tatsuya Akutsu
4:30 On the Multiple Gene Duplication Problem
Michael Fellows, Michael Hallett, Ulrike Stege
7:00 Conference Banquet
Wednesday, December 16, 1998
Session 8A: Geometry III
9:00 Visibility Queries in Simple Polygons and Applications
Boris Aronov, Leonidas J. Guibas, Marek Teichmann, Li Zhang
9:30 Quadtree Decomposition, Steiner Triangulation, and Ray shooting
Siu-Wing Cheng, Kam-Hing Lee
10:00 Optimality and Integer Programming Formulations of Triangulations in
General Dimension
Akira Tajima
Session 8B: Approximation Algorithm
9:00 Space-efficient Approximation Algorithms for MAXCUT and COLORING
Semidefinite Programs
Philip N. Klein, Hsueh-I Lu
9:30 A Capacitated Vehicle Routing Problem on a Tree
Shin-ya Hamaguchi, Naoki Katoh
10:00 Approximation Algorithms for Some Optimum Communication Spanning
Tree Problems
Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang
Coffee Break: 10:30 -- 11:00
Session 9A: Complexity III
11:00 The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees
Xiao Zhou, Takao Nishizeki
11:30 Inapproximability Results for Guarding Polygons without Holes
Stephan Eidenbenz
12:00 The Inapproximability of Non NP-hard Optimization Problems
Liming Cai, David Juedes, Iyad Kanj
Session 9B: Parallel and Distributed Algorithm
11:00 An Efficient NC Algorithm for a Sparse $k$-Edge-Connectivity
Certificate
Hiroshi Nagamochi, Toru Hasunuma
11:30 A Parallel Algorithm for Sampling Matchings from an Almost Uniform
Distribution
J. Diaz, J. Petit, P. Psycharis, M. Serna
12:00 Optimal Approximate Agreement with Omission Faults
Richard Plunkett, Alan Fekete
12:30: Lunch
Proceedings
-----------
Accepted papers will be published in the proceedings of the
symposium(Lecture Notes in Computer Science, Springer-Verlag).
Some selected papers will appear in Theoretical Computer Science
as special issues.
Further Information
-------------------
If you have any question and request, do not hesitate to ask us. Fax number
is +82-42-869-3510 and e-mail address is isaac98 at jupiter.kaist.ac.kr.
The detailed information for transportation(including time tables for buses
and trains), conference site map, and tourist attractions can be found
at our web site: http://jupiter.kaist.ac.kr/~isaac98/
General Information
-------------------
* Location
ISAAC'98 will be held at Riviera Hotel in Taejon. Taejon city is situated in
the geographical center of South Korea. The city of 1.3 million is also
surrounded by historical landmarks of the ancient Paekche civilization(18B.C
- A.D.660)
Mt.Daedoon Provincial Park, Mt.Kyeryoung National Park, Mt.Pomun Park and
Yusung, Korea's famous hot spring resort are all within a 30 minute drive.
* Weather
Weather in December is mostly cold with occasional snows. Temperature ranges
between -5 degrees Centigrade and -2.5 degrees Centigrade(23F - 27.5F).
* Currency Exchange
US $1 is about 1350 won. But nowadays, the exchange rate is fluctuating very
much. You can get the current exchange rate from internet.
(http://www.koexbank.co.kr/exchange_rating/newexchange2.html)
The unit of Korean currency is the "won". Coin denominations are 10 won, 50
won, 100 won, 500 won. Bank notes are 1,000 won, 5,000 won, 10,000 won.
Foreign bank notes and traveler's checks can be converted into Korean won at
foreign exchange banks and other authorized money changers. Credit cards,
including VISA and Master Cards are accepted at hotels, department stores
and restaurants.
* Passport and Visa
Every foreign visitor entering Korea must present a valid passport.
Delegates from countries requiring visas should apply at the Korean consular
offices of diplomatic missions in their respective countries before their
departure. Visitors from some countries may stay 15 days without VISA. For
the details, participants are advised to contact their local travel agent,
carrier or Korean diplomats.
Accommodation
-------------
Two hotels have been chosen as standard lodging for the conference.
One is Riviera hotel(the conference venue), and the other is Top hotel
(within easy walking distance to Riviera Hotel).
We have arranged for special conference rates at these hotels.
You can find more detailed information in the registration/accommodation
form below.
Transportation
--------------
o Conference Location
The conference location, Taejon city, is located at the center of
Korea's transportation network - about 100 miles south from Seoul and
200 miles north from Pusan. Seoul(Kimpo) airport and Pusan(Kimhae)
airport are two major airports, but there is no direct public
transportation to the conference venue.
o How to get there
Refer to the Web page at http://jupiter.kaist.ac.kr/~isaac98/
In the Web page, you can obtain the detail information about
the tranportation.
Registration
------------
You can register ISAAC'98 early by FAX or postal mail. There is
also Hotel reservation form in this registration form.
* Pre-registration Deadline: November 6, 1998
* Hotel information -- here
* Registration fee
------------------------------------------------------------------
Before November 6,1998 After November 6, 1998/On-site
------------------------------------------------------------------
Regular US $300 US $360
Student US $200 US $240
------------------------------------------------------------------
Please, complete the form(with the payment) and send it to the
following address(FAX or postal mail only):
Fax: +82-2-360-2306
Address:Ms. Cho, Tae-Nam
Dept. of Computer Science and Engineering
College of Engineering, Ewha Womans University
11-1 Daehyun-dong, Seodaemun-ku, Seoul, Korea 120-750
(E-Mail:isaac98 at mm.ewha.ac.kr)
------------------------------ cut here -----------------------------------
=======================================================================
ISAAC'98 REGISTRATION/ACCOMMODATION FORM
=======================================================================
Mail or fax to:
Ms. Cho, Tae-Nam, Dept. of Computer Science and Engineering
College of Engineering, Ewha Womans University,
11-1 Daehyun-dong, Seodaemun-ku, Seoul, Korea 120-750
Fax: +82-2-360-2306
__ Male __ Female
__ Dr. __ Prof. __ Researcher & Engineer __ Student
__ Other (please specify)_________________
Family name:_________________ Given name:_________________
Affiliation:_________________________________________
Address:_____________________________________________
_____________________________________________________
_____________________________________________________
Phone:_________________ Fax:________________________
Email:_______________________________________________
------------------------------------------------------
Registration Before Nov. 6 After Nov. 6
======================================================
Regular US $300 ___ US $360 ___
Student US $200 ___ US $240 ___
------------------------------------------------------
Registration covers a copy of proceedings, reception on Dec. 13,
3 lunches, coffee and banquet on Dec. 15.
The student fee does not include the banquet.
-----------------------------------------------------
Additional Tickets Number Amount
=====================================================
Banquet(US $50 each) ______ ______
-----------------------------------------------------
-----------------------------------------------------------
Hotel Rates(Daily rates in US dollars per room (incl.tax).)
===========================================================
Category Riviera (4 star) Top
===========================================================
Single(1) 95,000 won ___ 39,000 won ___
Double(2) 105,000 won ___ 48,000 won ___
Ondol(2) 95,000 won ___ 39,000 won ___
-----------------------------------------------------------
(Ondol means a Korean traditional room which is heated by
Korean under-floor heating system. There are no beds in
the Ondol room. US $1 is about 1350 won. The exchange rate
is fluctuating very much.)
Arrival Date:_____________ Departure Date:_____________
I wish to share my room with:____________________________
(We will make a hotel reservation for you. To guarantee your
reservation, a nonrefundable deposit(US $50) is required.
The remaining hotel charge should be paid directly to the hotel.)
Grand Total
============
Registration fee + Room deposit + Banquet tickets
(optional)
= _______________
Payment
========
All payments should be made in US dollar through one of the
following means. Bank transfer is highly recommended.
* Bank transfer
----------------
Name of the bank: Korea Exchange Bank Pangbaidong branch,
Seoul, Korea
Account number: 099-JSD-100740
Name of Account holder : KISS
Please enclose a copy of the bank transfer when sending the
registration form.
* By credit card. Please complete
-----------------
___ VISA ___ MASTER
Card Number:_____________________________________________
Card Holder Name:________________________________________
Card Holder Address:_____________________________________
_________________________________________________________
Expires:_____________ Signature:________________________
Registration/reservation will be confirmed only after
payment has been received.
Cancellation
=============
In case of the cancellation, written notification should be
sent to Ms. Cho, Tae-Nam. Registration fee, excluding 20% of
the fee, will be refunded only for cancellations made before
November 6, 1998. No refunds will be given for cancellations
made after this date.
-------------
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
More information about the Compgeom-announce
mailing list