APEX 2013 - Satellite Workshop of ICALP 2013

International Workshop on Approximation, Parameterized and EXact algorithms

July 7, 2013, Riga, Latvia


Sunday, July 7, 2013
9h00-9h30 Welcome
9h30-10h20 Invited talk: Daniel Marx

10h20-10h40 Coffee break

10h40-11h00 Yongjie Yang and Jiong Guo
Exact Algorithms for Weighted and Unweighted Borda Manipulation Problems
11h00-11h20 Guillaume Blin, Paola Bonizzoni, Riccardo Dondi and Florian Sikora.
On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem
11h20-11h40 Sepp Hartung and André Nichterlein
On the Parameterized and Approximation Hardness of Metric Dimension
11h40-12h00 Konrad Dabrowski, Marc Demange and Vadim Lozin.
The Complexity of Risk-free Marriage
12h00-12h20 Klaus Jansen, Felix Land and Kati Land.
Bounding the Running Time of Algorithms for Scheduling and Packing Problems

12h20-14h00 Lunch

14h00-14h50 Invited talk: Maxim Sviridenko

14h50-15h00 Coffee break

15h00-15h20 Zeev Nutov.
A unified approach to source location via rooted network augmentation
15h20-15h40 Silvia Mapa and Sebastian Urrutia.
A 1/2-approximation algorithm for the Maximum Acyclic Subgraph problem under Negative Disjunctive Constraints
15h40-16h00 Nachshon Cohen and Zeev Nutov.
Approximating $\{0,1,2\}$-Survivable Networks with Minimum Number of Steiner Points
16h00-16h20 Giorgio Lucarelli and Ioannis Milis.
Improved approximation algorithms for the Max Edge-Coloring problem

16h20-16h40 Coffee break

16h40-17h00 Eric Angel, Romain Campigotto and Christian Laforest
A Memory-Efficient Algorithm for Vertex Covering on Huge Graphs
17h00-17h20 Nicolas Boria, Federico Della Croce and Fabio Salassa.
Machine Scheduling and Reoptimization
17h20-17h40 Christian Laforest and Raksmey Phan.
Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic: Experimental Approach
17h40-18h00 Peng Cui.
Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion