ISCO is a new biannual symposium with its first issue held in Hammamet, Tunisia in March 2010. The symposium aims to bring together researchers from all the communities related to combinatorial optimization, including algorithms and complexity, mathematical programming and operations research. It is intended to be a forum for presenting original research in these areas and especially in their intersections. Quality papers on all aspects of combinatorial optimization, from mathematical foundations and theory of algorithms to computational studies and practical applications, are solicited.
Spring school
ISCO 2012 will be preceded by a spring school on "Mathematical Programming and Design of Approximation Algorithms". David Shmoys and David Williamson will give 16 hours of lectures on April 1718, 2012.
Submissions deadline: December 1, 2011 December 8, 2011, 11:59 UTC 11 time
Notification of authors: January 30, 2012
Early registration deadline: February 24, 2012
Spring School: April 1718, 2012
Conference: April 1921, 2012
Camera ready version: May 4, 2012
Giorgio Ausiello, Università di Roma "La Sapienza"
Hyperpaths in directed hypergraphs: Properties and algorithms
Abstract: Directed hypergraphs are a natural generalization of digraphs and are a combinatorial model that turns out to be useful in several application domains (databases, logic, artificial intelligence etc.). Although in general the computation of shortest hyperpaths in directed hypergraphs is an NPhard problem, for suitable cost measures such problem becomes tractable. In this paper, after discussing the structural properties of hyperpaths (with particular attention to the role of cycles in hyperpaths and to canonic form of hyperpaths), we present a taxonomy of hyperpath cost functions and we study the relationships between the classes of cost functions on hyperpaths and the structure of the corresponding optimal hyperpaths. Finally we illustrate for what classes in the taxonomy shortest hyperpaths can be computed in polynomial time.
George Nemhauser, Georgia Tech
BranchandPrice Guided Search
Abstract: We present an approach for structured integer programs that solves wellchosen restrictions of the problem to produce highquality solutions quickly. Column generation is used both for automatically generating the restrictions and for producing bounds on the value of an optimal solution. We present computational experience for fixedcharge multicommodity flow and inventory routing problems.
Christos Papadimitriou, UC Berkeley
Computational Insights and the Theory of Evolution
Abstract: I shall discuss recent work (much of it joint with biologists Adi Livnat and Marcus Feldman) on some central problems in Evolution that was inspired and informed by computational ideas. Considerations about the performance of genetic algorithms led to a novel theory on the role of sex in Evolution based on the concept of mixability. And a natural random process on Boolean functions can help us understand better Waddington’s genetic assimilation phenomenon, in which an acquired trait becomes genetic.
Paolo Toth, Università di Bologna
Models and Algorithms for the Train Unit Assignment Problem
Abstract: Passenger railway systems are highly complex systems requiring the solution of several planning problems
that can be analyzed and solved through the application of mathematical models and optimization techniques,
which generally lead to an improvement in the performance of the system, and also to a reduction in the time
required for solving these problems.
The planning process is generally divided into several phases: Line Planning, Train Timetabling, Train Platforming,
Rolling Stock Circulation and Crew Planning. In this lecture, after a description of the whole planning process and
of its main phases, the TrainUnit Assignment Problem, an important NPhard problem arising in the Rolling
Stock Circulation phase, is considered in detail.
In the TrainUnit Assignment Problem (TUAV), we are given a set of timetabled trips, each with a required number
of passenger seats, and a set of different train units, each having a cost and consisting of a selfcontained train
with an engine and a set of wagons with a given number of available seats. TUAV calls for the minimum cost
assignment of the train units to the trips, possibly combining more than one train unit for a given trip,
so as to fulfil the seat requests.
Two Integer Linear Programming (ILP) formulations of TUAV are presented, and valid inequalities are introduced
for strengthening the corresponding Linear Programming (LP) relaxation. Additional relaxations, based on the
Lagrangian approach and on the solution of a restricted problem associated with a peak period (i.e., with a subset
of simultaneous trips that must be assigned to distinct train units), are considered for the effective computation
of tight lower bounds. Constructive heuristic algorithms, based on the previously considered relaxations, are proposed,
and their solutions are improved by applying local search procedures.
Extensive computational results on realworld instances are reported, showing the effectiveness of the proposed
bounding procedures and heuristic algorithms.
Mourad Baïou, Université Blaise Pascal, ClermontFerrand
Evripidis Bampis, Université Pierre et Marie Curie
Francisco Barahona, IBM T.J. Watson, New York
Walid BenAmeur, TELECOM SudParis
Jaroslaw Byrka, University of Wrocław
William Cook, Georgia Tech
Gerard Cornuéjols, CMU
Federico Della Croce, Politecnico di Torino
Josep Diaz, Universitat Politecnica de Catalunya
Bruno Escoffier, Université Paris Dauphine
Satoru Fujishige, Kyoto University
Eric Gourdin, Orange Labs, Paris
Luis Gouveia, University of Lisbon
Anupam Gupta, CMU
Mohamed Haouari, INSAT, Tunis
Brahim Hnich, Izmir University of Economics
Klaus Jansen, ChristianAlbrechtsUniversität, Kiel
Stavros Kolliopoulos, NKUA, Athens
Jochen Könemann, University of Waterloo
Andrea Lodi, Università di Bologna
Nelson Maculan, Universidade Federal do Rio de Janeiro
A. Ridha Mahjoub, Université Paris Dauphine (cochair)
Alberto MarchettiSpaccamela, Università di Roma "La Sapienza"
Vangelis Markakis, AUEB, Athens
Tom McCormick, University of British Columbia
Ioannis Milis, AUEB, Athens (cochair)
Jérôme Monnot, Université Paris Dauphine
Vangelis Paschos, Université Paris Dauphine
Gerhard Reinelt, Universität Heidelberg
Giovanni Rinaldi, IASICNR, Roma
Amin Saberi, Stanford University
François Vanderbeck, Université Bordeaux 1
Peter Widmayer, ETH, Zürich
Gerhard Woeginger, Eindhoven University of Technology
Hande Yaman, Bilkent University, Ankara
Vassilis Zissimopoulos, NKUA, Athens
The submission deadline is Thursday December 8, 2011, 11:59 UTC 11 time.
Paper submission will be handled via Easy Chair.
Papers presenting original unpublished results in all areas of combinatorial optimization and its applications are welcome.
Topics of interest include, but are not limited to:
 Approximation algorithms
 Branchandbound algorithms
 Branchandcutandprice algorithms
 Computational biology
 Computational complexity
 Computational geometry
 Constraint Programming
 Cutting plane algorithms
 Exact and parameterized algorithms
 Graph and network algorithms
 Interior point methods
 Linear and nonlinear integer programming
 Local search algorithms
 Metaheuristics
 Online algorithms
 Polyhedral combinatorics
 Randomized algorithms
 Scheduling algorithms
There will be two types of submissions:
a) Regular papers
They should be of at most 12 pages, including front matter and bibliography, in LNCS style. Proofs omitted due to space constraints should be included in a clearly marked appendix which will be taken into account by the program committee members and the reviewers, but it will not be published in the proceedings. Simultaneous submissions to other conferences with published proceedings or journals are not allowed.
Accepted regular papers will be published by SpringerVerlag in the Lecture Notes in Computer Science (LNCS) series in a postconference proceedings volume. The authors will have to prepare their cameraready version two weeks after the end of ISCO 2012.
b) Short papers
They should be of at most 4 pages (including front matter and bibliography) with no optional appendix. Accepted short papers will be included in a volume of local proceedings.
The following Special Issues of International Journals will be associated with ISCO 2102:
 A special issue of Mathematical Programming Series B on "Combinatorial Optimization". See here for the CFP for this issue.
 A special issue of Theoretical Computer Science on "Combinatorial Optimization: Theory of algorithms and complexity". See here for the CFP for this issue.
 A special issue of RAIROOperations Research on "Combinatorial Optimization". See here for the CFP for this issue.
To be published in the LNCS postconference proceedings volume.
(37 out of 94, acceptance rate 39.4%)

Cid C. De Souza and Breno Piva.
The Minimum Stabbing Triangulation Problem: IP Models and Computational Evaluation 
Matteo Fischetti and Leo Liberti
Orbital shrinking 
Laura Galli, Konstantinos Kaparis and Adam Letchford
Gap Inequalities for the MaxCut Problem: a CuttingPlane Algorithm 
Trivikram Dokka, Ioannis Mourtos and Frits Spieksma
Fast Separation Algorithms for ThreeIndex Assignment problems 
Yuri Faenza, Samuel Fiorini, Roland Grappe and Hans Raj Tiwary
Extended formulations, nonnegative factorizations, and randomized communication protocols 
Gábor Braun and Sebastian Pokutta
An algebraic approach to symmetric extended formulations 
Alexandre Freire, Vicente Acuna, Pierluigi Crescenzi, Carlos Ferreira, Vincent Lacroix, Paulo Vieira Milreu, Eduardo Moreno and MarieFrance Sagot
Minimum ratio cover of matrix columns by extreme rays of its induced cone 
Gabriela Argiroffo, Graciela Nasini and Pablo Torres
The Packing Coloring Problem for (q,q4) graphs 
Leonardo Martinez and Alexandre Cunha
A Parallel Lagrangian Relaxation Algorithm for the MinDegree Constrained Minimum Spanning Tree Problem 
Sophie Toulouse
Differential Approximation of the Multiple Stacks TSP 
Yuichi Asahiro, Jesper Jansson, Eiji Miyano and Hirotaka Ono
Graph Orientations Optimizing the Number of Light or Heavy Vertices 
James Ostrowski
Using Symmetry to Optimize Over the SheraliAdams Relaxation 
Luis Gouveia, Markus Leitner and Ivana Ljubic
On the Hop Constrained Steiner Tree Problem with multiple Root Nodes 
Satoru Fujishige and Jens Massberg
Dual Consistent Systems of Linear Inequalities and Cardinality Constrained Polytopes 
Agostinho Agra, Marielle Christiansen, Rosa Figueiredo, Lars Magnus Hvattum, Michael Poss and Cristina Requejo
Layered Formulation for the Robust Vehicle Routing Problem with Time Windows 
Monique Laurent and Antonios Varvitsiotis
The Gram dimension of a graph 
Jianqiang Cheng, Celine Gicquel and Abdel Lisser
A secondorder Cone programming approximation to joint chanceconstrained linear Programs 
Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau and JeanClaude König
SumMax Graph Partitioning Problem 
Eduardo ÁlvarezMiranda, Valentina Cacchiani, Tim Dorneth, Michael Jünger, Frauke Liers, Andrea Lodi, Tiziano Parriani and Daniel R. Schmidt
Models and Algorithms for Robust Network Design with Several Traffic Scenarios 
Fabio Furini, Carlo Alfredo Persiani and Paolo Toth
Aircraft sequencing problems via a rolling horizon algorithm 
Manuel Sorge, Hannes Moser, Rolf Niedermeier and Mathias Weller
Exploiting a Hypergraph Model for Finding Golomb Rulers 
Pierre Fouilhoux and Aurélien Questel
The NonDisjoint mRingStar Problem : polyhedral results and SDH/SONET network design 
Monaldo Mastrolilli and Georgios Stamoulis
Constrained Matching Problems in Bipartite Graphs 
Anna Huber and Vladimir Kolmogorov
Towards Minimizing kSubmodular Functions 
Pierre Bonami, Viet Hung Nguyen, Michel Klein and Michel Minoux
On the Solution of a Graph Partitioning Problem under Capacity Constraints 
MarieEmilie Voge and François Clautiaux
Theoretical investigation of aggregation in pseudopolynomial networkflow models 
Mario Ruthmair and Günther Raidl
On Solving the Rooted Delay and DelayVariationConstrained Steiner Tree Problem 
Rafael Schouery and Cristina Fernandes
SecondPrice Ad Auctions with Binary Bids and Markets with Good Competition 
Agnes Gorge, Abdel Lisser and Riadh Zorgati
Semidefinite Relaxations for Mixed 01 SecondOrder Cone Program 
Sylvie Borne, Roland Grappe and Mathieu Lacroix
The Uncapacitated Asymmetric Traveling Salesman Problem with Multiple Stacks 
Marc Demange, Jérôme Monnot, Petrica Pop and Bernard Ries
Selective Graph Coloring in Some Special Classes of Graphs 
Tommy Färnqvist
Counting Homomorphisms via Hypergraphbased Structural Restrictions 
Konstantinos Papalamprou and Leonidas Pitsoulis
Recognition algorithms for binary signedgraphic matroids 
Bo Xiong and Christine Chung
Completion Time Scheduling and the WSRPT Algorithm 
Mikhail Kovalyov, Ammar Oulamara and Ameur Soukhal
Two agent scheduling on a serial batching machine 
Dennis Weyland, Roberto Montemanni and Luca Maria Gambardella
Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines 
Mathieu Lacroix, Ridha Mahjoub and Sebastien Martin
Polyhedral Analysis and BranchandCut for the Structural Analysis Problem

Céline Gicquel, Abdel Lisser and Michel Minoux.
Tight lower bounds by semidefinite relaxation for a lotsizing problem with sequencedependent changeover costs 
Bendotti Pascale, Pierre Fouilhoux and Podkanski Karol.
Permutation Problem using a UnitCapacity Robot : Feasibility Recovery and Cuttingplane based Formulation with MTZ strengthening 
Alain Billionnet, Fethi Jarray, Ghassen Tlig and Ezzedine Zagrouba.
Combining simulated annealing and linear programming approaches for reconstructing hvconvex colored images 
Michaël Gabay, Gerd Finke and Nadia Brauner.
Identical coupled task scheduling problem: the finite case 
Hipolito Hernandez Perez and Juan Jose Salazar Gonzalez.
Solving the multicommodity manytomany PickupandDelivery Traveling Salesman Problem 
Luis Gouveia and Juan Jose Salazar.
Polynomial Separation of the Enhanced Reverse Multistar Inequalities 
Irène Charon and Olivier Hudry.
A branch and bound method for the aggregation of symmetric relations 
Tolga Bektas and Luis Gouveia.
A polyhedral approach for generalizing the MillerTuckerZemlin subtour elimination constraints for routing problems 
Alexandre Cunha.
Algorithms for the Multiperiod Degree Constrained Minimum Spanning Tree Problem 
Mette Gamst.
A routebased decomposition for the MultiCommodity ksplittable Maximum Flow Problem 
Stefan Gollowitzer, Bernard Gendron and Ivana Ljubic.
Capacitated Network Design with Facility Location 
Nicolas Dupin.
A 2stage robust optimization model for planning nuclear maintenances with uncertain maintenance durations 
Monaldo Mastrolilli and Georgios Stamoulis.
Restricted MaxMin Fair Allocation with Inclusionfree Intervals 
Miriam Kießling, Sascha Kurz and Jörg Rambau.
An exact columngeneration approach for the lottype design problem 
Valeria Leoni, Erica Hinrichsen and María Patricia Dobson.
Generalized Limited packings of P4tidy graphs 
Walid BenAmeur, Pierre Bauguion and Eric Gourdin.
An efficient treebased model for multicommodity flow problems 
Eric Gourdin and Yuhui Wang.
Bottleneck and Maxmin Transportation Problems with Degree Constraints 
Fabio Salassa, Wim Vancroonenburg, Tony Wauters, Federico Della Croce and Greet Vanden Berghe.
Matheuristics for the Eternity II puzzle 
Didem Gözüpek, Mordechai Shalom, Ariella Voloshin and Shmuel Zaks.
On the Complexity of Constructing Minimum Reload Cost PathTrees 
Roland Grappe.
Polynomial cases of hypergraph local edgeconnectivity augmentation 
Houssein Alaeddine, Emmanuel Neron, Kamal Serrhini and Mindjid Maizia.
Planning for evacuation 
Rafaelli Coutinho, Lúcia Drummond, Yuri Frota, Luidi Simonetti and Eduardo Uchoa.
A Distributed Transportation Simplex Applied to a Content Distribution Network Problem 
Pierre Fouilhoux.
Cliquebranching formulation for the vertex coloring problem 
Laurent Alfandari, Anass Nagih, Agnès Plateau and Jalila Sadki.
Generalizations of Dobson approximation algorithm and cooperation with Column Generation for largesize Covering Integer Programs 
Pierre Le Bodic and Cédric Bentz.
On the complexity of Partial Colored Multiterminal Cut problems 
Eduardo ÁlvarezMiranda, Ivana Ljubic, S. Raghavan and Paolo Toth.
The Recoverable Robust TwoLevel Network Design Problem 
Sophie Toulouse, JeanFrançois Culus and Roupin Frédéric.
DIFFERENTIAL APPROXIMATION OF SNP OPTIMIZATION PROBLEMS 
Denis Cornaz, Herve Kerivin and Ridha Mahjoub.
A combinatorial linearization of the quadratic acyclic vertexinduced subgraph problem 
Mourad Baiou and Francisco Barahona.
The classical facility location polytope for graphs with no godd Ycycle 
Amal Benhamiche, Ridha Mahjoub, Nancy Perrot and Eduardo Uchoa.
A BranchandPrice Algorithm for the Optical MultiBand Network Design Problem 
Hassene Aissi and A. Ridha Mahjoub.
On the constrained minimum s − t cut problem
To download the program in pdf, click here.
"Mathematical Programming and Design of Approximation Algorithms"
by
David Shmoys and
David Williamson
The material for the course will be drawn from our recent book The Design of Approximation Algorithms (DAA), and be augmented by several recent papers. We list below the topics of the course, the associated sections of the book and the related additional papers (though the papers cited in these book sections might also be covered more completely than in the text). The list below is probably somewhat too ambitious for the allotted time.
The uncapacitated facility location problem
 Deterministic (DAA 4.5) and randomized rounding (DAA 5.8, DAA 12.1), primaldual method (DAA 7.6) and local search (DAA 9.1)
and the kmedian problem
 Lagrangean relaxation (DAA 7.7) and local search (DAA 9.2)
The traveling salesman problem
 Greedy algorithms (DAA 2.4)
 L. A. Wolsey, Heuristic analysis, linear programming and branch and bound, In Combinatorial Optimization II, volume 13, Mathematical Programming Studies, pages 121134. Springer, 1980
 T. Mömke and O. Svensson, Approximating graphic TSP by matchings, Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 560569, 2011
 M. Mucha, 13/9approximation for the graphic TSP, to appear in Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), 2012
 H.C. An, R. Kleinberg, and D. Shmoys, Improving Christofides’ Algorithm for the st path TSP, to appear in Proceedings of the 44th Annual ACM Symposium on Theory of Computing
 F. Schalekamp, D. Williamson, A. van Zuylen, A proof of the BoydCarr conjecture, Proceedings of the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, pages 14771486, 2012
The Steiner tree problem (primaldual method, DAA 7.4) and the generalized Steiner tree problem (randomized rounding, DAA 12.3)
The boundeddegree minimum spanning tree problem (deterministic rounding, DAA 11.2)
The minimumcost knapsack problem (primaldual method, DAA 7.5)
The prizecollecting Steiner tree problem
 Deterministic rounding (DAA 4.4), randomized rounding (DAA 5.7) and primaldual method (DAA 14.1)
and the prizecollecting TSP
"Mathematical Programming and Design of Approximation Algorithms"
by
David Shmoys and
David Williamson
schedule
Tuesday, April 17, 2012  

9:0010:30  Lecture 1 
10:3010:45  Coffee Break 
10:4512:30  Lecture 2 
Lunch  
14:0016:00  Problem Session 1 
16:0016:15  Coffee Break 
16:1518:00  Lecture 3 
18:0019:00  Problem Solutions 1 
Wednesday, April 18, 2012  
9:0010:30  Lecture 4 
10:3010:45  Coffee Break 
10:4512:30  Lecture 5 
Lunch  
14:0016:00  Problem Session 2 
16:0016:15  Coffee Break 
16:1518:00  Lecture 6 
18:0019:00  Problem Solutions 2 
Christos Amanatidis, AUEB, Athens
Katerina Kinta, Université Paris Dauphine
Anna Klouvatou, RCAUEB, Athens
Giorgio Lucarelli, Université Paris Dauphine
A. Ridha Mahjoub, Université Paris Dauphine
Vangelis Markakis, AUEB, Athens
Ioannis Milis, AUEB, Athens
Vangelis Paschos, Université Paris Dauphine
Georgios Zois, AUEB, Athens
To register click here (you will be redirected to our bank page for ISCO 2012 registration).
Registration Fees
Early up to 24/02/12 
Late from 25/02/12 

ISCO 2012 Regular  360€  480€ 
ISCO 2012 Student  200€  280€ 
Spring School  10€  20€ 
Coffee breaks
Conference final program
Conference proceedings
Conference social events and dinner
The Spring School fee applies for administrative purposes only.
For lunch (near AUEB) and dinner (in Athens) options click here.
How to reach your hotel from the airport
There are various options to reach the downtown hotels depending on whether you want to use public transportation or taxi.
By public transport: The blue metro line goes all the way from the airport to downtown and passes through
the Syndagma metro station (where you can connect with the red line) and the Monastiraki metro station
(where you can connect with the green line that goes towards AUEB). Please do not confuse the metro line with the
suburban railway system, which departs from the adjacent platform and is not convenient for going downtown.
The metro line takes about 3540 minutes to Syndagma and the ticket from the airport costs 8 euros (note that a
regular metro ticket costs only 1.40 as long as you use it within the city, it is only for the airport that costs 8 euros).
The metro operates from 5:30 am till around midnight. Within the city it runs pretty frequently but the departures to/from the
airport are only every 30 minutes (normally at 5 and 35 past every hour).
Apart from the metro, and especially if you arrive late, you can also take the bus X95 which also goes to Syndagma square.
The bus departs every 15 minutes and the ticket costs 5 euros.
By taxi: During the day there is now a standard rate of 35 euros to the city center from the airport.
If you arrive past midnight, the tariff is 50 euros.
How to come to the conference venue
The conference will take place in the main building of AUEB (the Athens University of Economics and Business).
AUEB is located in the city center, and the main building is on 76 Patission st. If your hotel is not within walking
distance, the best way to come to AUEB is by using the green line and getting off at Victoria station. It is then a 5 minute walk
till the main building. There are also several buses and trolleys that stop just outside AUEB such as the buses
608, 622, A8, B8, Γ8 and the trolleys 3, 5, 11, 13, 14. In the map below you can have a better view of where the main
building of AUEB is located.
View ISCO 2012 in a larger map
How to reach the Acropolis Museum for the social event
To come to the social event on Friday evening, one option is to take the metro from Victoria station near AUEB and switch in Omonoia to the red line. Then you get off at the Akropolis station and the museum is just a few minutes walk from there. Alternatively you can take the trolley 5 (just across from the main building) and get off at the Makrygianni stop.
The Athens University of Economics and Business (AUEB), where the conference will take place, is located in the centre of Athens where many hotels can be found. We include here some recommended hotels, in walking distance from AUEB, and their offers for ISCO 2012.

Radisson Park Hotel
ISCO 2012 offer and booking form
(~5 min walking distance from AUEB)
Alexandras ave 10, 10682 Athens
Tel.: +30 210 8894500
Fax : +30 210 8238420
anna.agrafa@rbathenspark.com 
Areos Hotel
ISCO 2012 offer
(~5 min walking distance from AUEB)
19 Mpoumpoulinas Street. 10682 Athens
Tel: +30 210 8259540
Fax: +30 210 8259244
rsv@athensareoshotel.gr 
Zafolia Hotel
ISCO 2012 offer and booking form
(~15 min walking distance from AUEB)
8789, Alexandras Av. 11474 Athens
Tel: +30 210 6449 002
Fax: +30 210 6442 042
info@zafoliahotel.gr 
Meliá Athens
ISCO 2012 offer and booking form
(~15 min walking distance from AUEB)
14 Chalkokondili & 28 October (Patision), 10677 Athens
Tel: +30 210 3320100
Fax: +30 210 3320200
melia.athens@melia.com
Recommended areas for other accommodation options include: Panepistimiou street, Stadiou street, Syntagma square, Kolonaki.
For any further information please write to isco12@cs.aueb.gr