From - Mon May 12 15:47:12 1997 Path: Radon.Stanford.EDU!news.Stanford.EDU!su-news-hub1.bbnplanet.com!cam-news-hub1.bbnplanet.com!cpk-news-hub1.bbnplanet.com!news.bbnplanet.com!feed1.news.erols.com!howland.erols.net!vixen.cso.uiuc.edu!symcom.math.uiuc.edu!dan From: klinz@fmatbhp1.tu-graz.ac.at (Bettina Klinz) Newsgroups: comp.theory,sci.op-research,sci.math.research,sci.math Subject: ESA'97, List of accepted papers Date: 12 May 1997 15:43:34 GMT Organization: Graz University of Technology, Austria Lines: 120 Approved: Daniel Grayson , moderator for sci.math.research Distribution: inet Message-ID: <5l7dr6$ehm@fstgal00.tu-graz.ac.at> NNTP-Posting-Host: symcom.math.uiuc.edu Summary: ESA'97, List of accepted papers Originator: dan@symcom.math.uiuc.edu Xref: Radon.Stanford.EDU comp.theory:11800 sci.op-research:8102 sci.math.research:7168 sci.math:154952 X-Mozilla-Status: 0001 Content-Length: 3371 =========================================================================== List of papers accepted to ESA'97, September 15-17, Graz, Austria. =========================================================================== *** Diks, Pelc Optimal adaptive broadcasting with a bounded fraction of faulty nodes *** Brandstaedt, Chepoi, Dragan Distance approximating trees for chordal and dually chordal graphs *** Segal On piercing sets of axis-parallel rectangles and rings *** Vallee Algorithms for signs of 2x2 determinants: dynamic and average case analysis *** Helmberg Fixing variables in semidefinite relaxations *** Krznaric, Levcopoulos, Nilsson Minimum spanning trees in d dimensions *** Cornuejols, Urbaniak, Weismantel, Wolsey Decomposition of integer programs and of generating sets *** Rethmann, Wanke Competitive Analysis of on-line stack-up algorithms *** Weihe, Willhalm Reconstructing the topology of a CAD model - A discrete approach *** Larsen, Ottmann, Soisalon-Soininen Relaxed balance for search trees with local rebalancing *** Korupolu, Ramachandran Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence *** Glazebrook, Nino-Mora Scheduling multiclass queueing networks on parallel servers: Klimov's rule *** Henk, Weismantel Test sets of the knapsack problem and simultaneous diophantine approximation *** Nolte, Schrader Coloring in sublinear time *** Bloemer Denesting by bounded degree radicals *** Frigioni, Italiano Dynamically switching vertices in planar graphs *** Mueller-Hannemann, Weihe Improved Approximations for quadrangulations of finite element meshes *** Kalyanasundaram, Pruhs Fault-tolerant real-time scheduling *** Iwama, Miyano 3-dimensional meshes are less powerful than 2-dim ones in oblivious routing *** Garefalakis A new family of randomized algorithms for list accessing *** Brandes, Wagner Linear time algorithm for the arc disjoint Menger Problem in planar digraphs *** Djidjev Weighted graph separators and their application *** Azar, Epstein On-line machine covering *** Grebinski, Kucherov Optimal reconstruction of graphs under the additive model *** Fekete, Schepers A new exact algorithm for general orthogonal d-dimensional knapsack problems *** Naor, Orda, Petruschka Dynamic storage allocation with known durations *** Arkin, Hassin On local search for weighted k-set packing *** Czumaj, Strothmann Bounded degree spanning trees *** Foessmeier, Kaufmann Solving rectilinear Steiner tree problems exactly in theory and practice *** Giancarlo, Guaiana On-line construction of two-dimensional suffix trees *** Amoura, Bampis, Kenyon, Manoussakis How to schedule independent multiprocessor tasks *** Schulz, Skutella Scheduling-LPs bear probabilities *** Biedl, Kaufmann Area-efficient static and incremental graph drawings *** Snoeyink, van Kreveld Linear-time reconstruction of Delaunay triangulations with applications *** Trevisan Approximating satisfiable satisfiability problems *** Fischer, Meyer auf der Heide, Strothmann Dynamic data structures for realtime management of large geometric scenes *** Sevastianov Seven problems: so different yet close *** Kogan, Schuster Collecting garbage pages in a distributed shared memory with reduced memory and communication overhead From owner-dma-list@NIC.SURFNET.NL Wed May 21 04:36:06 1997 Received: from CS.Stanford.EDU (CS.Stanford.EDU [171.64.64.64]) by robotics.Stanford.EDU (8.8.5/8.8.5) with ESMTP id EAA23741; Wed, 21 May 1997 04:36:06 -0700 (PDT) Received: from hearnnt.nic.surfnet.nl (hearnnt.nic.surfnet.nl [192.87.5.133]) by CS.Stanford.EDU (8.8.4/8.8.4) with ESMTP id EAA06161; Wed, 21 May 1997 04:35:11 -0700 (PDT) Received: from hearnnt (192.87.5.133) by hearnnt.nic.surfnet.nl (LSMTP for Windows NT v1.1a) with SMTP id <0.5D0EC420@hearnnt.nic.surfnet.nl>; Wed, 21 May 1997 13:32:01 +0200 Received: from NIC.SURFNET.NL by NIC.SURFNET.NL (LISTSERV release 1.8c) with NJE id 3205 for DMA-LIST@NIC.SURFNET.NL; Wed, 21 May 1997 13:35:20 +0200 Received: from HEARN (NJE origin SMTP@HEARN) by HEARN.NIC.SURFNET.NL (LMail V1.2c/1.8c) with BSMTP id 8393; Wed, 21 May 1997 13:35:18 +0200 Received: from utmfu6.math.utwente.nl by HEARN.nic.SURFnet.nl (IBM VM SMTP V2R2) with TCP; Wed, 21 May 97 13:35:06 +0200 Received: from utmfu0.math.utwente.nl (utmou1.math.utwente.nl) by utmfu6.math.utwente.nl with ESMTP (1.40.112.8/16.2) id AA229954488; Wed, 21 May 1997 13:34:49 +0200 Received: by utmfu0.math.utwente.nl ($Revision: 1.36.108.11 $/16.2) id AA190004486; Wed, 21 May 1997 13:34:46 +0200 Mailer: Elm [revision: 66.36.1.1] Approved-By: DMANET Message-ID: <199705211134.AA190004486@utmfu0.math.utwente.nl> Date: Wed, 21 May 1997 13:34:45 METDST Reply-To: klinz@opt.math.tu-graz.ac.at Sender: DMANET From: DMANET Subject: ESA'97 (Graz), Final Program and Registration Information To: DMA-LIST@NIC.SURFNET.NL X-Mozilla-Status: 0001 Content-Length: 17448 *********************************************************************** Fifth Annual European Symposium on Algorithms (ESA'97) September 15-17, 1997, Graz, Austria. Final Program and Registration Information *********************************************************************** In the series of annual international symposia on algorithms, the Fifth Annual European Symposium on Algorithm (ESA'97), will be held in Graz, September 15-17, 1997, in the university facilities of the Graz University of Technology. The European Symposium on Algorithms covers all research on algorithms and their analysis as it is carried out in the fields of computer science, discrete applied mathematics and mathematical programming, and all other areas of algorithm-oriented research and its applications. This file contains (I) the preliminary program of the meeting, (II) registration information, (III) information on payment, (IV) general information, (V) the registration form, (VI) hotel reservation information and hotel reservation form. *********************************************************************** (I). PRELIMINARY PROGRAM Session 1. 10:00-10:45 (Monday, September 15, 1997) +++ Algorithms for signs of 2x2 determinants: dynamics and average case analysis B. Vallee (Caen) +++ A new exact algorithm for general orthogonal d-dimensional knapsack problems S.P. Fekete (Koeln), J. Schepers (Koeln) +++ Break 10:45-11:15 Session 2. 11:15-12:45 (Monday, September 15, 1997) +++ A new family of randomized algorithms for list accessing Th. Garefalakis (Toronto) +++ Approximating satisfiable satisfiability problems L. Trevisan (Geneve) +++ Area-efficient static and incremental graph drawings Th. Biedl (Rutgers), M. Kaufmann (Tuebingen) +++ Bounded degree spanning trees A. Czumaj (Paderborn), W.B. Strothmann (Paderborn) +++ Lunch Break 12:45-14:30 Session 3. 14:30-15:15 (Monday, September 15, 1997) +++ Collecting garbage pages in a distributed shared memory with reduced memory and communication overhead D. Kogan (Haifa), A. Schuster (Haifa) +++ Coloring in sublinear time A. Nolte (Koeln), R. Schrader (Koeln) +++ Break 15:15-15:45 Session 4. 15:45-17:00 (Monday, September 15, 1997) +++ Competitive Analysis of on-line stack-up algorithms J. Rethmann (Duesseldorf), E. Wanke (Duesseldorf) +++ Decomposition of integer programs and of generating sets G. Cornuejols (Carnegie-Mellon), R. Urbaniak (Berlin), R. Weismantel (Berlin), L. Wolsey (Louvain-la-Neuve) +++ Denesting by bounded degree radicals J. Bloemer (Zuerich) +++ Break 17:00-17:10 +++ ESA'97 Business Meeting 17:10 +++ Reception in the Cityhall of Graz 20:00 Session 5. 9:00-10:30 (Tuesday, September 16, 1997) +++ Distance approximating trees for chordal and dually chordal graphs A. Brandstaedt (Rostock), V. Chepoi (Marseille), F. Dragan (Rostock) +++ Dynamically switching vertices in planar graphs D. Frigioni (Roma), G.F. Italiano (Venezia) +++ Dynamic data structures for realtime management of large geometric scenes M. Fischer (Paderborn), F. Meyer auf der Heide (Paderborn), W.B. Strothmann (Paderborn) +++ Dynamic storage allocation with known durations S. Naor (Haifa), A. Orda (Haifa), Y. Petruschka (Haifa) +++ Break 10:30-11:00 Session 6. 11:00-12:30 (Tuesday, September 16, 1997) +++ Fault-tolerant real-time scheduling B. Kalyanasundaram (Pittsburgh), K. Pruhs (Pittsburgh) +++ Fixing variables in semidefinite relaxations Ch. Helmberg (Berlin) +++ How to schedule independent multiprocessor tasks A.K. Amoura (Paris), E. Bampis (Evry), C. Kenyon (Lyon), Y. Manoussakis (Paris) +++ Improved Approximations for quadrangulations of finite element meshes M. Mueller-Hannemann (Berlin), K. Weihe (Konstanz) +++ Lunch Break 12:30-14:00 Session 7. 14:00-15:30 (Tuesday, September 16, 1997) +++ Linear time algorithm for the arc disjoint Menger Problem in planar directed graphs U. Brandes (Konstanz), D. Wagner (Konstanz) +++ Linear-time reconstruction of Delaunay triangulations with applications J. Snoeyink (UBC), M. van Kreveld (Utrecht) +++ On-line construction of two-dimensional suffix trees R. Giancarlo (Palermo), D. Guaiana (Palermo) +++ Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems M.R. Korupolu (Austin), V. Ramachandran (Austin) +++ Guided City tour 16:30 +++ Conference Dinner 20:00 Session 8. 9:00-10:30 (Wednesday, September 17, 1997) +++ Minimum spanning trees in d dimensions D. Krznaric (Lund), Ch. Levcopoulos (Lund), B.J. Nilsson (Lund) +++ On-line machine covering Y. Azar (Tel-Aviv), L. Epstein (Tel-Aviv) +++ On local search for weighted k-set packing E.M. Arkin (Stony Brook), R. Hassin (Tel-Aviv) +++ On piercing sets of axis-parallel rectangles and rings M. Segal (Beer-Sheva) +++ Break 10:30-11:00 Session 9. 11:00-12:30 (Wednesday, September 17, 1997) +++ Optimal adaptive broadcasting with a bounded fraction of faulty nodes K. Diks (Warszaw), A. Pelc (Quebec) +++ Optimal reconstruction of graphs under the additive model V. Grebinski (Nancy), G. Kucherov (Nancy) +++ Reconstructing the topology of a CAD model - A discrete approach K. Weihe (Konstanz), Th. Willhalm (Konstanz) +++ Relaxed balance for search trees with local rebalancing K.S. Larsen (Odense), Th. Ottmann (Freiburg), E. Soisalon-Soininen (Helsinki) +++ Lunch Break 12:30-14:00 Session 10. 14:00-15:30 (Wednesday, September 17, 1997) +++ Scheduling-LPs bear probabilities: Randomized approximations for Min-Sum Criteria A.S. Schulz (Berlin), M. Skutella (Berlin) +++ Scheduling multiclass queueing networks on parallel servers: approximate and heavy-traffic optimality of Klimov's rule K.D. Glazebrook (Newcastle), J. Nino-Mora (Louvain-la-Neuve) +++ Seven problems: so different yet close S.V. Sevastianov (Novosibirsk) +++ Solving rectilinear Steiner tree problems exactly in theory and practice U. Foessmeier (Tuebingen), M. Kaufmann (Tuebingen) +++ Break 15:30-16:00 Session 11. 16:00-17:15 (Wednesday, September 17, 1997) +++ Test sets of the knapsack problem and simultaneous diophantine approximation M. Henk (Berlin), R. Weismantel (Berlin) +++ 3-dimensional meshes are less powerful than 2-dim ones in oblivious routing K. Iwama (Kyushu), E. Miyano (Kyushu) +++ Weighted graph separators and their application H. Djidjev (Rice) +++ Closing remarks 17:15 *********************************************************************** (II). REGISTRATION INFORMATION Please register for ESA'97 by filling the attached registration form. You should send it to the Symposium Secretariat by airmail, by fax or by e-mail (to esa97@opt.math.tu-graz.ac.at). Confirmation of the registration will be sent after we receive your registration form together with a copy of the receipt of your payment (see section below) or together with your complete credit card data. Registration can only be accepted if payment instructions are duly followed. Registration fee by August 15 after August 15 Full 3200.- ATS (270 US$) 4500.- ATS (380 US$) Student 2000.- ATS (170 US$) 3500.- ATS (290 US$) Extra Dinner ticket 800.- ATS (60 US $) Extra proceedings 500.- ATS (40 US $) The prices listed above are in Austrian Schillings (ATS). Prices given in US dollars are only orientative. The registration fees (both full and student) include the symposium materials, coffee breaks, lunches and proceedings. The full registration fee also includes the symposium dinner. Students and accompanying persons can buy separate tickets for the dinner. Students must also send a certification of their full-time student status. For EASTERN-EUROPEAN participants, there is special funding that allows us to reduce the fee to 1000.- ATS (80 US$) or even less. In case you want to apply for this, or in case you want to apply for travelling support, please contact us before July 15 at esa97@opt.math.tu-graz.ac.at. ESA'97 Symposium Secretariat Institut fuer Mathematik B TU Graz Steyrergasse 30 A-8010 Graz, Austria Fax: +43 316 873 5369 Email: esa97@opt.math.tu-graz.ac.at *********************************************************************** (III). PAYMENT This is the first year where ESA also accepts payment by credit cards (Eurocard, VISA, Diners Club, American Express). If you want to pay by credit card, please indicate card type, credit card number and expiry date in your registration form that you send to us. Don't forget your signature by hand. Otherwise, advance payment of the registration fee should be made by money transfer of the required total amount in Austrian Schillings (ATS) to the account Bank name: P.S.K. Oesterreichische Postsparkasse Address: Georg-Coch-Platz 2, A-1018 Wien, Austria Account name: Institut fuer Mathematik, TU Graz Account number: 92.081.013 SWIFT Code: OPSKATWW Banknumber (BLZ): 60000 To avoid unnecessary bank charges, please make sure that all the information above is present in the transfer. We recall that (unless you pay by credit card) you should send us a copy of the receipt of your payment to confirm your registration. *********************************************************************** (IV). GENERAL INFORMATION +++ Location. ESA '97 will be held in the university facilities of the Graz University of Technology, in the Room BE01 in the Mathematics building (Steyrergasse 30). +++ Climate. The average temperature in Graz during September is 18 C. Towards the end of the month, some days tend to be cloudy and eventually, it might rain. Days are still long; the weather is ideal for sightseeing and other open air activities. Detailed information about Graz's climate is available through WWW. +++ Entry Visa. Non-EU residents may require an entry visa for Austria. Please check with your local Austrian consulate as early as possible. +++ Language. The official language of the conference is English. +++ Proceedings. The proceedings of ESA '97 will be published in the series "Lecture Notes in Computer Science" of Springer-Verlag and will be available at the Symposium. A copy of the proceedings is included in the full and student registration fees. +++ On-line Information. A lot more information is available via the WWW Page of the Symposium at http://www.iicm.edu/esa_97. Information about the city and its climate can be obtained from there. In the near future, there will be more detailed information about the place of the reception and about the symposium dinner. +++ Program Committee. Giorgio Ausiello (Roma), Rainer Burkard (Graz), Josep Diaz (Barcelona), Amos Fiat (Tel Aviv), Mark Jerrum (Edinburgh), Jan Karel Lenstra (Eindhoven), Kurt Mehlhorn (Saarbruecken), Rolf Moehring (Berlin), Pekka Orponen (Helsinki), Christos Papadimitriou (Berkeley), Bill Pulleyblank (Yorktown Heights), Zsolt Tuza (Budapest), Gerhard Woeginger (Graz). *********************************************************************** (V). REGISTRATION FORM Please, fill in this form (with typewriter or block letters, very legible, if sent by ordinary mail or fax) and send or email it to ESA'97 Symposium Secretariat Institut fuer Mathematik B TU Graz Steyrergasse 30 A-8010 Graz, Austria Fax: +43 316 873 5369 Email: esa97@opt.math.tu-graz.ac.at To confirm your registration, you should also send us a copy of the receipt of your payment. Check the section about `Payment' for the details. ++++++++++++++ Begin of registration form of ESA'97 ++++++++++++++++++++++ ESA'97 Fifth Annual European Symposium on Algorithms Technische Universitaet Graz, September 15-17, 1997 Surname: __________________________ Firstname: __________________________ Name for Badge: __________________________________________________________ Affiliation: _____________________________________________________________ Mailing address: _________________________________________________________ _________________________________________________________________ ZIP, City: __________________________ Country: __________________________ Phone: ___________________________ Fax: __________________________________ Email: _______________________________________________ Vegetarian: (YES / NO) Date of arrival [dd.mm.yy]: ______________________________________________ Date of departure [dd.mm.yy]: ____________________________________________ I would like to pay the fee by money order [ ] to the following account: Bank name: P.S.K. Oesterreichische Postsparkasse Address: Georg-Coch-Platz 2, A-1018 Wien, Austria Account name: Institut fuer Mathematik, TU Graz Account number: 92.081.013 SWIFT Code: OPSKATWW Banknumber (BLZ): 60000 or credit card [ ] VISA [ ] MC [ ] Diners [ ] Am. Express NUMBER OF CREDIT CARD: _____________________________________________ EXPIRATION DATE: ___________________________________________________ SIGNATURE: _________________________________________________________ Registration by August 15 after August 15 ------------------------------------------------------------- Full [ ] 3200 ATS [ ] 4500 ATS Student (*) [ ] 2000 ATS [ ] 3000 ATS Additional dinner tickets [ ] 800 ATS Additional proceedings [ ] 500 ATS Total amount: _____________________ (*) certification of full-time student status has to be included ++++++++++++++ End of registration form of ESA'97 ++++++++++++++++++++++++ *********************************************************************** (VI). HOTEL RESERVATION INFORMATION +++ There will be a limited number of rooms available in a students dormitory that is very close to the conference place (very simple accomodation; no breakfast included). The price per night will be about 170.- ATS (single occupancy) and 85.- ATS (double occupancy). If you are interested in this type of accomodation, please contact us before July 15 by email at esa97@opt.math.tu-graz.ac.at. +++ In all other cases, please fax or send the following form as soon as possible (but not later than July 30, 1997) to: CITY TOURIST OFFICE GRAZ City Travel Agency Convention Department Kaiserfeldgasse 15 A-8010 Graz, AUSTRIA Tel. +43/316/8075-62 Fax. +43/316/8075-55 ++++++++++++++ Begin of hotel reservation form for ESA'97 ++++++++++++++++ ESA'97 Fifth Annual European Symposium on Algorithms Technische Universitaet Graz, September 15-17, 1997 PLEASE COMPLETE IN BLOCK LETTERS Participant: ( ) Mr ( ) Ms Family name: ______________________ First Name: _______________________ Affiliation: ___________________________________________________________ Address: _______________________________________________________________ Country: ___________ Postal Code: ________ City: __________________ Telephone: _____________________ Telefax: __________________________ Please reserve: ____ single room(s) ____ double room(s) with bathroom/shower: Hotel category 5* ( ) 1650-1900 ( ) 2300-2600 4* ( ) 1150-1600 ( ) 1650-2150 3* ( ) 700- 920 ( ) 950-1250 2* ( ) 470- 600 ( ) 750- 900 with bathroom/shower on the corridor: ( ) cheaper ( ) cheaper Prices are in Austrian shillings (ATS) per room and per night, including breakfast and taxes. ------------------------------------------------------------------------ I shall arrive by ( ) private car ( ) train ( ) plane Arrival date: ______ Arrival time: ______ Departure date: _______ Number of nights: __________ Cancellation should be made written or by phone to the City Travel Agency 3 days before arrival. To guarantee your reservation we kindly ask you to provide the following information: Credit card number : ________________________ Expiry date: ___/___ ( ) Eurocard ( ) VISA ( ) Diners Club ( ) American Express Place and date: _________________ Signature: _______________________ ++++++++++++++ End of hotel reservation form for ESA'97 ++++++++++++++++++ -- ****************************************************** Contributions to be spread via DMANET are submitted to DMANET@math.utwente.nl Replies to a message carried on DMANET should NOT be addressed to DMANET but to the original sender. The original sender, however, is invited to prepare an update of the replies received and to communicate it via DMANET. DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET) From owner-dma-list@NIC.SURFNET.NL Wed Jul 2 03:36:43 1997 Received: from CS.Stanford.EDU (CS.Stanford.EDU [171.64.64.64]) by robotics.Stanford.EDU (8.8.5/8.8.5) with ESMTP id DAA10354; Wed, 2 Jul 1997 03:36:43 -0700 (PDT) Received: from hearnnt.nic.surfnet.nl (hearnnt.nic.surfnet.nl [192.87.5.133]) by CS.Stanford.EDU (8.8.4/8.8.4) with ESMTP id DAA05908; Wed, 2 Jul 1997 03:36:18 -0700 (PDT) Received: from hearnnt (192.87.5.133) by hearnnt.nic.surfnet.nl (LSMTP for Windows NT v1.1a) with SMTP id <0.0426AC00@hearnnt.nic.surfnet.nl>; Wed, 2 Jul 1997 12:32:34 +0200 Received: from NIC.SURFNET.NL by NIC.SURFNET.NL (LISTSERV release 1.8c) with NJE id 2177 for DMA-LIST@NIC.SURFNET.NL; Wed, 2 Jul 1997 12:36:26 +0200 Received: from HEARN (NJE origin SMTP@HEARN) by HEARN.NIC.SURFNET.NL (LMail V1.2c/1.8c) with BSMTP id 3128; Wed, 2 Jul 1997 12:36:22 +0200 Received: from utmfu6.math.utwente.nl by HEARN.nic.SURFnet.nl (IBM VM SMTP V2R2) with TCP; Wed, 02 Jul 97 12:36:19 +0200 Received: from utmfu0.math.utwente.nl (utmou1.math.utwente.nl) by utmfu6.math.utwente.nl with ESMTP (1.40.112.8/16.2) id AA262589754; Wed, 2 Jul 1997 12:35:55 +0200 Received: by utmfu0.math.utwente.nl ($Revision: 1.36.108.11 $/16.2) id AA138449752; Wed, 2 Jul 1997 12:35:52 +0200 Mailer: Elm [revision: 66.36.1.1] Approved-By: DMANET Message-ID: <199707021035.AA138449752@utmfu0.math.utwente.nl> Date: Wed, 2 Jul 1997 12:35:50 METDST Reply-To: klinz@opt.math.tu-graz.ac.at Sender: DMANET From: DMANET Subject: ESA'97 - Call For Participation (Reminder and Update) To: DMA-LIST@NIC.SURFNET.NL Status: O X-Mozilla-Status: 0001 Content-Length: 18055 *********************************************************************** Fifth Annual European Symposium on Algorithms (ESA'97) September 15-17, 1997, Graz, Austria. WWW: http://www.iicm.edu/esa_97 Final Program and Registration Information *********************************************************************** In the series of annual international symposia on algorithms, the Fifth Annual European Symposium on Algorithm (ESA'97), will be held in Graz, September 15-17, 1997, in the university facilities of the Graz University of Technology. The European Symposium on Algorithms covers all research on algorithms and their analysis as it is carried out in the fields of computer science, discrete applied mathematics and mathematical programming, and all other areas of algorithm-oriented research and its applications. This file contains (I) the preliminary program of the meeting, (II) registration information, (III) information on payment, (IV) general information, (V) the registration form, (VI) hotel reservation information and hotel reservation form. Please note that the deadline for applying for the reduced fee for East-European participants is July 15, 1997. *********************************************************************** (I). PRELIMINARY PROGRAM Invited talk. 9:00-10:00 (Monday, September 15, 1997) +++ Semidefinite programming for approximation algorithms Michel Goemans (Louvain) Session 1. 10:00-10:45 (Monday, September 15, 1997) +++ Algorithms for signs of 2x2 determinants: dynamics and average case analysis B. Vallee (Caen) +++ A new exact algorithm for general orthogonal d-dimensional knapsack problems S.P. Fekete (Koeln), J. Schepers (Koeln) +++ Break 10:45-11:15 Session 2. 11:15-12:45 (Monday, September 15, 1997) +++ A new family of randomized algorithms for list accessing Th. Garefalakis (Toronto) +++ Approximating satisfiable satisfiability problems L. Trevisan (Geneve) +++ Area-efficient static and incremental graph drawings Th. Biedl (Rutgers), M. Kaufmann (Tuebingen) +++ Bounded degree spanning trees A. Czumaj (Paderborn), W.B. Strothmann (Paderborn) +++ Lunch Break 12:45-14:30 Session 3. 14:30-15:15 (Monday, September 15, 1997) +++ Collecting garbage pages in a distributed shared memory with reduced memory and communication overhead D. Kogan (Haifa), A. Schuster (Haifa) +++ Coloring in sublinear time A. Nolte (Koeln), R. Schrader (Koeln) +++ Break 15:15-15:45 Session 4. 15:45-17:00 (Monday, September 15, 1997) +++ Competitive Analysis of on-line stack-up algorithms J. Rethmann (Duesseldorf), E. Wanke (Duesseldorf) +++ Decomposition of integer programs and of generating sets G. Cornuejols (Carnegie-Mellon), R. Urbaniak (Berlin), R. Weismantel (Berlin), L. Wolsey (Louvain-la-Neuve) +++ Denesting by bounded degree radicals J. Bloemer (Zuerich) +++ Break 17:00-17:10 +++ ESA'97 Business Meeting 17:10 +++ Reception in the Cityhall of Graz 20:00 Session 5. 9:00-10:30 (Tuesday, September 16, 1997) +++ Distance approximating trees for chordal and dually chordal graphs A. Brandstaedt (Rostock), V. Chepoi (Marseille), F. Dragan (Rostock) +++ Dynamically switching vertices in planar graphs D. Frigioni (Roma), G.F. Italiano (Venezia) +++ Dynamic data structures for realtime management of large geometric scenes M. Fischer (Paderborn), F. Meyer auf der Heide (Paderborn), W.B. Strothmann (Paderborn) +++ Dynamic storage allocation with known durations S. Naor (Haifa), A. Orda (Haifa), Y. Petruschka (Haifa) +++ Break 10:30-11:00 Session 6. 11:00-12:30 (Tuesday, September 16, 1997) +++ Fault-tolerant real-time scheduling B. Kalyanasundaram (Pittsburgh), K. Pruhs (Pittsburgh) +++ Fixing variables in semidefinite relaxations Ch. Helmberg (Berlin) +++ How to schedule independent multiprocessor tasks A.K. Amoura (Paris), E. Bampis (Evry), C. Kenyon (Lyon), Y. Manoussakis (Paris) +++ Improved Approximations for quadrangulations of finite element meshes M. Mueller-Hannemann (Berlin), K. Weihe (Konstanz) +++ Lunch Break 12:30-14:00 Session 7. 14:00-15:30 (Tuesday, September 16, 1997) +++ Linear time algorithm for the arc disjoint Menger Problem in planar directed graphs U. Brandes (Konstanz), D. Wagner (Konstanz) +++ Linear-time reconstruction of Delaunay triangulations with applications J. Snoeyink (UBC), M. van Kreveld (Utrecht) +++ On-line construction of two-dimensional suffix trees R. Giancarlo (Palermo), D. Guaiana (Palermo) +++ Quasi-fully dynamic algorithms for two-connectivity, cycle equivalence and related problems M.R. Korupolu (Austin), V. Ramachandran (Austin) +++ Guided City tour 16:30 +++ Conference Dinner 20:00 Session 8. 9:00-10:30 (Wednesday, September 17, 1997) +++ Minimum spanning trees in d dimensions D. Krznaric (Lund), Ch. Levcopoulos (Lund), B.J. Nilsson (Lund) +++ On-line machine covering Y. Azar (Tel-Aviv), L. Epstein (Tel-Aviv) +++ On local search for weighted k-set packing E.M. Arkin (Stony Brook), R. Hassin (Tel-Aviv) +++ On piercing sets of axis-parallel rectangles and rings M. Segal (Beer-Sheva) +++ Break 10:30-11:00 Session 9. 11:00-12:30 (Wednesday, September 17, 1997) +++ Optimal adaptive broadcasting with a bounded fraction of faulty nodes K. Diks (Warszaw), A. Pelc (Quebec) +++ Optimal reconstruction of graphs under the additive model V. Grebinski (Nancy), G. Kucherov (Nancy) +++ Reconstructing the topology of a CAD model - A discrete approach K. Weihe (Konstanz), Th. Willhalm (Konstanz) +++ Relaxed balance for search trees with local rebalancing K.S. Larsen (Odense), Th. Ottmann (Freiburg), E. Soisalon-Soininen (Helsinki) +++ Lunch Break 12:30-14:00 Session 10. 14:00-15:30 (Wednesday, September 17, 1997) +++ Scheduling-LPs bear probabilities: Randomized approximations for Min-Sum Criteria A.S. Schulz (Berlin), M. Skutella (Berlin) +++ Scheduling multiclass queueing networks on parallel servers: approximate and heavy-traffic optimality of Klimov's rule K.D. Glazebrook (Newcastle), J. Nino-Mora (Louvain-la-Neuve) +++ Seven problems: so different yet close S.V. Sevastianov (Novosibirsk) +++ Solving rectilinear Steiner tree problems exactly in theory and practice U. Foessmeier (Tuebingen), M. Kaufmann (Tuebingen) +++ Break 15:30-16:00 Session 11. 16:00-17:15 (Wednesday, September 17, 1997) +++ Test sets of the knapsack problem and simultaneous diophantine approximation M. Henk (Berlin), R. Weismantel (Berlin) +++ 3-dimensional meshes are less powerful than 2-dim ones in oblivious routing K. Iwama (Kyushu), E. Miyano (Kyushu) +++ Weighted graph separators and their application H. Djidjev (Rice) +++ Closing remarks 17:15 *********************************************************************** (II). REGISTRATION INFORMATION Please register for ESA'97 by either filling the attached registration form or by filling the registration form which is available at the WWW at the address http://www.iicm.edu/esa_97 In the first case you should send your filled form to the Symposium Secretariat by airmail, by fax or by e-mail (to the address esa97@opt.math.tu-graz.ac.at). Confirmation of the registration will be sent after we receive your registration form together with a copy of the receipt of your payment (see section below) or together with your complete credit card data (including your signature). Registration can only be accepted if payment instructions are duly followed. Registration fee by August 15 after August 15 Full 3200.- ATS (270 US$) 4500.- ATS (380 US$) Student 2000.- ATS (170 US$) 3500.- ATS (290 US$) Extra Dinner ticket 800.- ATS (60 US $) Extra proceedings 500.- ATS (40 US $) The prices listed above are in Austrian Schillings (ATS). Prices given in US dollars are only orientative. The registration fees (both full and student) include the symposium materials, coffee breaks, lunches and proceedings. The full registration fee also includes the symposium dinner. Students and accompanying persons can buy separate tickets for the dinner. Students must also send a certification of their full-time student status. For EASTERN-EUROPEAN participants, there is special funding that allows us to reduce the fee to 1000.- ATS (80 US$) or even less. In case you want to apply for this, or in case you want to apply for travelling support, please contact us before July 15 at esa97@opt.math.tu-graz.ac.at. ESA'97 Symposium Secretariat Institut fuer Mathematik B TU Graz Steyrergasse 30 A-8010 Graz, Austria Fax: +43 316 873 5369 Email: esa97@opt.math.tu-graz.ac.at *********************************************************************** (III). PAYMENT This is the first year where ESA also accepts payment by credit cards (Eurocard, VISA, Diners Club, American Express). If you want to pay by credit card, please indicate card type, credit card number and expiry date in your registration form that you send to us. Don't forget your signature by hand. Otherwise, advance payment of the registration fee should be made by money transfer of the required total amount in Austrian Schillings (ATS) to the account Bank name: P.S.K. Oesterreichische Postsparkasse Address: Georg-Coch-Platz 2, A-1018 Wien, Austria Account name: Institut fuer Mathematik, TU Graz Account number: 92.081.013 SWIFT Code: OPSKATWW Banknumber (BLZ): 60000 To avoid unnecessary bank charges, please make sure that all the information above is present in the transfer. We recall that (unless you pay by credit card) you should send us a copy of the receipt of your payment to confirm your registration. *********************************************************************** (IV). GENERAL INFORMATION +++ Location. ESA '97 will be held in the university facilities of the Graz University of Technology, in the Room BE01 in the Mathematics building (Steyrergasse 30). +++ Climate. The average temperature in Graz during September is 18 C. Towards the end of the month, some days tend to be cloudy and eventually, it might rain. Days are still long; the weather is ideal for sightseeing and other open air activities. Detailed information about Graz's climate is available through WWW. +++ Entry Visa. Non-EU residents may require an entry visa for Austria. Please check with your local Austrian consulate as early as possible. +++ Language. The official language of the conference is English. +++ Proceedings. The proceedings of ESA '97 will be published in the series "Lecture Notes in Computer Science" of Springer-Verlag and will be available at the Symposium. A copy of the proceedings is included in the full and student registration fees. +++ On-line Information. Lots of informations are available via the WWW Page of the Symposium at http://www.iicm.edu/esa_97. Information about the city and its climate can be obtained from there. In the near future, there will be more detailed information about the place of the reception and about the symposium dinner. +++ Program Committee. Giorgio Ausiello (Roma), Rainer Burkard (Graz), Josep Diaz (Barcelona), Amos Fiat (Tel Aviv), Mark Jerrum (Edinburgh), Jan Karel Lenstra (Eindhoven), Kurt Mehlhorn (Saarbruecken), Rolf Moehring (Berlin), Pekka Orponen (Helsinki), Christos Papadimitriou (Berkeley), Bill Pulleyblank (Yorktown Heights), Zsolt Tuza (Budapest), Gerhard Woeginger (Graz). *********************************************************************** (V). REGISTRATION FORM Please, fill in this form (with typewriter or block letters, very legible, if sent by ordinary mail or fax) and send or email it to ESA'97 Symposium Secretariat Institut fuer Mathematik B TU Graz Steyrergasse 30 A-8010 Graz, Austria Fax: +43 316 873 5369 Email: esa97@opt.math.tu-graz.ac.at To confirm your registration, you should also send us a copy of the receipt of your payment. Check the section about `Payment' for the details. Alternatively, you may register via the WWW at http://www.iicm.edu/esa_97 ++++++++++++++ Begin of registration form of ESA'97 ++++++++++++++++++++++ ESA'97 Fifth Annual European Symposium on Algorithms Technische Universitaet Graz, September 15-17, 1997 Surname: __________________________ Firstname: __________________________ Name for Badge: __________________________________________________________ Affiliation: _____________________________________________________________ Mailing address: _________________________________________________________ _________________________________________________________________ ZIP, City: __________________________ Country: __________________________ Phone: ___________________________ Fax: __________________________________ Email: _______________________________________________ Vegetarian: (YES / NO) Date of arrival [dd.mm.yy]: ______________________________________________ Date of departure [dd.mm.yy]: ____________________________________________ I would like to pay the fee by money order [ ] to the following account: Bank name: P.S.K. Oesterreichische Postsparkasse Address: Georg-Coch-Platz 2, A-1018 Wien, Austria Account name: Institut fuer Mathematik, TU Graz Account number: 92.081.013 SWIFT Code: OPSKATWW Banknumber (BLZ): 60000 or credit card [ ] VISA [ ] MC [ ] Diners [ ] Am. Express NUMBER OF CREDIT CARD: _____________________________________________ EXPIRATION DATE: ___________________________________________________ SIGNATURE: _________________________________________________________ Registration by August 15 after August 15 ------------------------------------------------------------- Full [ ] 3200 ATS [ ] 4500 ATS Student (*) [ ] 2000 ATS [ ] 3000 ATS Additional dinner tickets [ ] 800 ATS Additional proceedings [ ] 500 ATS Total amount: _____________________ (*) certification of full-time student status has to be included ++++++++++++++ End of registration form of ESA'97 ++++++++++++++++++++++++ *********************************************************************** (VI). HOTEL RESERVATION INFORMATION +++ There will be a limited number of rooms available in a students dormitory that is very close to the conference place (very simple accomodation; no breakfast included). The price per night will be about 170.- ATS (single occupancy) and 85.- ATS (double occupancy). If you are interested in this type of accomodation, please contact us before July 15 by email at esa97@opt.math.tu-graz.ac.at. +++ In all other cases, please fax or send the following form as soon as possible (but not later than July 30, 1997) to: CITY TOURIST OFFICE GRAZ City Travel Agency Convention Department Kaiserfeldgasse 15 A-8010 Graz, AUSTRIA Tel. +43/316/8075-62 Fax. +43/316/8075-55 ++++++++++++++ Begin of hotel reservation form for ESA'97 ++++++++++++++++ ESA'97 Fifth Annual European Symposium on Algorithms Technische Universitaet Graz, September 15-17, 1997 PLEASE COMPLETE IN BLOCK LETTERS Participant: ( ) Mr ( ) Ms Family name: ______________________ First Name: _______________________ Affiliation: ___________________________________________________________ Address: _______________________________________________________________ Country: ___________ Postal Code: ________ City: __________________ Telephone: _____________________ Telefax: __________________________ Please reserve: ____ single room(s) ____ double room(s) with bathroom/shower: Hotel category 5* ( ) 1650-1900 ( ) 2300-2600 4* ( ) 1150-1600 ( ) 1650-2150 3* ( ) 700- 920 ( ) 950-1250 2* ( ) 470- 600 ( ) 750- 900 with bathroom/shower on the corridor: ( ) cheaper ( ) cheaper Prices are in Austrian shillings (ATS) per room and per night, including breakfast and taxes. ------------------------------------------------------------------------ I shall arrive by ( ) private car ( ) train ( ) plane Arrival date: ______ Arrival time: ______ Departure date: _______ Number of nights: __________ Cancellation should be made written or by phone to the City Travel Agency 3 days before arrival. To guarantee your reservation we kindly ask you to provide the following information: Credit card number : ________________________ Expiry date: ___/___ ( ) Eurocard ( ) VISA ( ) Diners Club ( ) American Express Place and date: _________________ Signature: _______________________ ++++++++++++++ End of hotel reservation form for ESA'97 ++++++++++++++++++ -- ****************************************************** Contributions to be spread via DMANET are submitted to DMANET@math.utwente.nl Replies to a message carried on DMANET should NOT be addressed to DMANET but to the original sender. The original sender, however, is invited to prepare an update of the replies received and to communicate it via DMANET. DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)