[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