CALL FOR PARTICIPATION Second DIMACS Implementation Challenge Clique, Graph Coloring, and Satisfiability October 11-13, 1993 DIMACS, Rutgers University In conjunction with its Special Year on Combinatorial Optimization, the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) has been sponsoring international Implementation Challenge to find effective optimization and approximation algorithms for the following NP-hard problems: Maximum Clique, Graph Coloring, and Satisfiability. The Implementation Challenge culminates in a conference to be held at DIMACS October 11-13. Participants in the Challenge will be presenting their work on generating instances, developing solution algorithms, and analyzing output for these problems. Participants in the Challenge and other interesting researchers are invited to attend this conference. For more details on the Challenge and results to date, please contact Michael Trick (challenge@dimacs.rutgers.edu) or access the Challenge files via anonymous ftp from dimacs.rutgers.edu in the pub/challenge directory. ADVISORY BOARD A committee of DIMACS members has provided general direction for the Implementation Challenge. Committee members are Vasek Chvatal, Rutgers University, Bill Cook, Bell Communications Research, David Johnson, AT&T Bell Laboratories, Cathy McGeoch, Amherst College, Bob Tarjan, Princeton University, and Michael Trick, DIMACS Visiting Fellow/Carnegie Mellon University (Coordinator). REGISTRATION The DIMACS Conference Center can accommodate about 100 participants. Subject to this capacity constraint, the workshop is open to all researchers. To register, contact Pat Toci, toci@dimacs.rutgers.edu. If possible, please register by October 1 -- although registering at the conference is permitted. THERE IS NO REGISTRATION FEE. TRAVEL SUPPORT We have limited travel support money available. Please contact Michael Trick (challenge@dimacs.rutgers.edu) to apply or for information. Graduate students are particularly encouraged to apply for support if needed. ACCEPTED PAPERS Researchers were invited to submit extended abstracts for this conference. The following papers have been accepted for presentation at the conference. In addition, we will be running two poster sessions (one for clique and graph coloring and one for satisfiability) where we expect 6-10 papers each. CLIQUE PAPERS M. Brockington and J.C. Culberson, "Camouflaging Independent Sets in Quasi-Random Graphs" S. Homer and M. Peinado, "On the Performance of Polynomial Time Clique Approximation Algorithms on Very Large Graphs" M.K. Goldberg and R. Rivenbergh, "Constructing Cliques Using the Near Greedy Algorithm" E. Balas and W. Niehaus, "Finding Large Cliques by Bipartite Matching" J.M. Bourjolly, P. Gill, G. Laporte, and H. Mercure, "Two Exact for the Stable Set Problem" E. Balas, S. Ceria, G. Cornuejols, and G. Pitaki, "Linear Programming Methods for the Clique Problem in Graphs" C. Mannino and A. Sassano, "An Exact Algorithm for the Maximum Cardinality Stable Set Problem" E. Balas and J. Xue, "Weighted and Unweighted Maximum Clique Algorithms with Upper Bounds from Fractional Coloring" T. Grossman, "Applying the INN Model for the MaxClique Problem" A. Jagota, L. Sanchis, and R. Ganesan, "Approximately Solving Maximum Clique using Neural Network and Related Heuristics" GRAPH COLORING PAPERS J.C. Culberson and F. Luo, "Exploring the k-colorable Landscape with Iterated Greedy" C. Morganstern, "A Distributed Coloration Neighborhood Search Algorithm" G. Lewandowski and A. Condon, "Experiments with Parallel Graph Coloring Heuristics" SATISFIABILITY PAPERS O. Dubois, P. Andre, Y. Boufkhad, and J. Carlier, "SAT versus UNSAT" A. Van Gelder and Y.K. Tsuji, "Satisfiability Testing with More Reasoning and Less Guessing" D. Pretolani, "Solving Satisfiability Problems: An Algorithm Implementation Challenge?" B. Jaumard, M. Stan, and J. Desrosiers, "Tabu Search and a Quadratic Relaxation for the Satisfiability Problem" M.G.C. Resende and T.A. Feo, "A GRASP for MAX-SAT" B. Selman and H.A. Kautz, "Local Search Strategies for Satisfiability Testing" S. Hampson and D. Kilber, "Plateaus and Plateau Search in Boolean Satisfiability Problems" R.J. Wallace and E.C. Freuder, "Applying Algorithms for Constraint Satisfaction to Maximum Satisfiability Problems" J. Cheriyan, W.H. Cunningham, L. Tuncel, and Y. Wang, "The Maximum 2--Satisfiability Problem" TENTATIVE SCHEDULE A more detailed schedule will be available soon. The following is an outline of the format of the conference. MONDAY, October 11 8:00- 9:00. Coffee and doughnuts 9:15-10:00. Invited Speaker (TBA) 10:00-10:30. Coffee 10:30-12:30. SESSION: Clique instance generation and heuristics 12:30- 1:30. Lunch 1:30- 3:30. SESSION: Exact Algorithms for Cliques 3:30- 4:00. Break with snacks 4:00- 5:00. SESSION: Neural Net Approaches to Finding Cliques 5:00- 5:30. SESSION: An Introduction to the Poster Session 5:30- 7:30. Reception and Clique/Coloring Poster Session 7:30- Informal competitions, code demonstrations, etc. TUESDAY, October 12 8:00- 9:00. Coffee and doughnuts 9:00-10:30. SESSION: Graph Coloring 10:30-11:00. Coffee 11:00-12:00. PANEL DISCUSSION (Cliques and Coloring). 12:00- 1:30. Lunch 1:30- 2:30. Invited Paper TBA 2:30- 3:00. Coffee and snacks 3:00- 5:00. SESSION: Exact Algorithms for Satisfiability 5:00- 5:30. POSTER SESSION OVERVIEW 5:30- 7:30. Reception and Poster Session (Satisfiability) 7:30- Informal competitions, code demonstrations, etc. WEDNESDAY, October 13 8:00- 9:00. Coffee and doughnuts 9:00-10:30. SESSION Heuristic Algorithms for Satisfiability 10:30-11:00. Coffee 11:00-12:00. SESSION Exact Algorithms for Maximum Satisfiability 12:00- 1:30. Lunch 1:30- 2:30. Panel Discussion (Satisfiability) 2:30- 3:00. Future Plans and Effect of Challenge TRAVEL AND HOTEL INFORMATION It is recommended that participants arriving by plane fly into Newark Airport. Flying into Kennedy or La Guardia can add more than an hour to the travel time to DIMACS. DIMACS has successfully and quite pleasantly used the Comfort Inn and the Holiday Inn, both in South Plainfield - they are next to each other. The Comfort Inn gives DIMACS the rate of $40.00 and the Holiday Inn of $60.00 (includes a continental breakfast). The Comfort Inn's # is 908-561-4488. The Holiday Inn's # is 908-753-5500. They both provide free van service to and from DIMACS. If desired, hotel reservations can be made by Pat Toci [toci@dimacs.rutgers.edu], the workshop coordinator. She will need to know the date of arrival and departure, which hotel is preferred, and a credit card and expiration number. It is recommended that hotel reservations be made by October 1, 1993. To travel between Newark Airport and DIMACS/hotels, we recommend ICS Van Service, 1-800-225-4427. The rate is $19.00 per person. It must be booked in advance. From the New York airports, participants may take the Grayline Air (bus) Shuttle (1-800-451-0455) to Newark and then ICS Van service from there. Participants arriving to DIMACS by car will need a parking permit. Parking permits can be obtained in advance by sending email to Pat Toci. Otherwise, they can be obtained any day of the workshop. All workshop events will take place at DIMACS, located in the CoRE Building of Rutgers University, Busch Campus, in Piscataway, New Jersey. Any further questions regarding local transportation and accommodations should be directed to Pat Toci [toci@dimacs.rutgers.edu, (908) 932-5930]. DIRECTIONS TO THE HOTELS: DIRECTIONS TO THE HOLIDAY INN - PHONE: 908-753-5500 4701 Stelton Road, South Plainfield, NJ 07080 and DIRECTIONS TO THE COMFORT INN - 908-561-4488 I 287 and Stelton Road, South Plainfield, NJ 07080 >FROM THE NEW JERSEY TURNPIKE - (Rt. 95): Take exit #10 to Route 287 North. Stay on Route 287 North for approximately 6 miles to the exit marked "Durhan Avenue - South Plainfield." Bear left coming off the exit and go under the Route 287 bridge. At the first light, make a right onto Hadley Road. Go to the end of Hadley Road and make a right onto Stelton Road. The hotels are on the right. >FROM ROUTE 287 NORTH: Get off at the exit marked "Durham Avenue - South Plainfield." Bear left coming off the exit and go under the Route 287 bridge. At the first light, make a right onto Hadley Road. Go to the end of Hadley Road and make a right onto Stelton Road. The hotels are on the right. >FROM ROUTE 287 SOUTH: Get off at the exit marked "Route 529 - Edison." When you get off the exit, you will see the hotels on the left. Go to the first light, at Dunkin Donuts, make a right and then make the U-turn, come back and make the left onto Stelton Road. >FROM THE GARDEN STATE PARKWAY HEADING NORTH: Take exit #127 to Route 287 North. Stay on Route 287 North for approximately 6 miles to the exit marked "Durham Avenue - South Plainfield." Bear left coming off the exit and go under the Route 287 bridge. At the first light, make a right onto Hadley Road. Go to the end of Hadley Road and make a right onto Stelton Road. The hotels are on the right. >FROM THE GARDEN STATE PARKWAY HEADING SOUTH: Take exit #129 to Route 287 North. Stay on Route 287 North for approximately 6 miles to the exit marked "Durham Avenue - South Plainfield." Bear left coming off the exit and go under the Route 287 bridge. At the first light, make a right onto Hadley Road. Go to the end of Hadley Road and make a right onto Stelton Road. The hotels are on the right. >FROM ROUTE 22 EAST: Take the exit marked "Washington Avenue, Dunellen," (you'll be in the town of Green Brook). At the exit, you will make a right turn onto Washington Avenue. Stay on Washington Avenue approximately 4 miles. The name then changes to Stelton Road. Stay on Stelton Road approximately 1 mile and the hotels are on the left. >FROM ROUTE 22 WEST: Take the exit marked "Washington Avenue, Dunellen," (you'll be in the town of Green Brook). This exit takes you across Route 22 (you'll go around a jug-handle) onto Washington Avenue. Stay on Washington Avenue approximately 4 miles. The name then changes to Stelton Road. Stay on Stelton Road approximately 1 mile and the hotels are on the left. >FROM ROUTE 1 HEADING NORTH: Take the exit marked "Plainfield Avenue - Edison," (you will be in the town of Edison). This will direct you around the block so that you cross Route 1. Stay on Plainfield Avenue approximately 5 miles. This road becomes Stelton Toad. The hotels are on your right just before the Route 287 intersection. >FROM ROUTE 1 HEADING SOUTH: Take the exit marked "Plainfield Avenue - Edison," (you will be in the town of Edison). Stay on Plainfield Avenue approximately 5 miles. This road becomes Stelton Road. The hotels are on your right just before the Route 286 intersection. DIRECTIONS TO DIMACS: Directions to DIMACS - CoRE Building, 4th floor Rutgers University BUSCH CAMPUS By Car: From Route 18: Follow Route 18 North (or West: signs differ, mean the same) to New Brunswick Area. Follow sign to 18 NORTH along river over big bridge across river to light at River Road. Cross River Road at light onto Metlars Lane. Proceed up Metlars Lane to 2nd left (Brett Road). Turn left onto Brett Road. At top of Brett Road (beginning of parking lots), go straight and CoRE building is in front of you. Park in the lot farthest to the left (64). The CoRE building is a 7-story building, directly behind the Hill Center. From Route 1 and Turnpike: Get on Route 18 West/North and follow directions as above. From Route 287 North: Take (Bound Brook/Highland Park) exit. Turn left off ramp. Drive through to 3rd light (Hoes Lane) approximately 3 miles. (You will pass Colgate on your left then light.) Turn left and follow Hoes Lane just past the Rutgers Golf Course Clubhouse. Turn right onto Frelinghuysen Road. Follow Frelinghuysen to Bartholomew Road. Turn left. Turn left again onto Brett Road and into parking lot as above. From Route 287 South: Take (Bound Brook/Highland Park) exit. Bear right and follow above directions. From Newark Airport: Take NJ Turnpike (Toll Road) South from Airport. Get off Turnpike at Exit 10. Take 287 North or take Route 1/9 South to 18 North. Follow directions as above. By Train: Ride to New Brunswick (Amtrack or Conrail) Taxi services are familiar with University. Ask for CoRE Bldg. (behind Hill Center, Busch Campus) Otherwise, two blocks behind station are Campus Bus Services. By Bus: (Suburban Transit) Ride to New Brunswick. Take taxi to CoRE Bldg. (behind Hill Center, Busch Campus) Once you park in lot 64, go to the CoRE building and get a parking permit from Pat Toci, who will have a table set up to the left of the elevator when you walk in. Go back to your car and put the permit on the dashboard. The lectures are in the Seminar Room on the 1st floor, unless otherwise noted. From the Holiday Inn/Comfort Inn - South Plainfield. Leave the hotels by way of the back exits behind the Holiday Inn. Make a right onto Hadley Road. Go to the light and make a left onto Stelton Rd. Go to the second light and make a right onto to Metlars Lane. Go to the light, (you will be facing Rackley's Restaurant) and make a left (you will still be on Metlars Lane. Stay on Metlars Lane until you come to the fork in the road at the second light. (Metlars Florist will be on your right). Bear right at the fork (you will still be on Metlars Lane). Go through the next light at the intersection of Metlars Lane and Davidson Rd. Take the second right AFTER the light onto Brett Road. Follow Brett Road up into Lot 64. This is where you should park. You must come up into the CoRE and get a parking permit from Pat Toci, who will have a table set up to the left of the elevator when you walk in. Go back to your car and put the permit on the dashboard. The lectures are in the Seminar Room on the 1st floor, unless otherwise noted.