Scientific Program Cluster Details

Program -> Parallel Sessions -> Cluster List -> Details all clusters
Search talks included | sessions only


Please login, if you want to personalize your selection of clusters.

Cluster: Approximation & online algorithms

Monday


10:30 - 12:00, room: H 3010

Chair: Sylvia Boyd and David Shmoys
Approximation in routing and others

An Improving Christofides' algorithm for the s-t path TSP [...]
Schalekamp On the integrality gap of the subtour LP for the 1,2-TSP [...]
Shmoys A primal-dual approximation algorithm for min-sum single-machine scheduling problems [...]

 

13:15 - 14:45, room: H 3010

Chair: Sanjoy Baruah
Real-time scheduling

Niemeier Scheduling with an orthogonal resource constraint [...]
van der Ster Mixed-criticality scheduling of sporadic task systems on a single machine [...]
Chen Resource augmentation in real-time systems [...]

 

15:15 - 16:45, room: H 3010

Chair: Artem Panin
Location and routing problems

Nonner Polynomial-time approximation schemes for shortest path with alternatives [...]
Bock The school bus problem [...]
Panin On approximability some location and pricing problems [...]

 

 

Tuesday


10:30 - 12:00, room: H 3010

Chair: Chaitanya Swamy
Approximation in algorithmic game theory

Georgiou Black-box reductions for cost-sharing mechanism design [...]
Vöcking A universally-truthful approximation scheme for multi-unit auctions [...]
Chakrabarty Matching markets with ordinal preferences [...]

 

13:15 - 14:45, room: H 3010

Chair: Sylvia Boyd and David Shmoys
Travelling salesman problem I

Boyd The travelling salesman problem on cubic and subcubic graphs [...]
van Zuylen A proof of the Boyd-Carr conjecture [...]
Sebő Shorter tours by nicer ears [...]

 

13:15 - 14:45, room: MA 041

Chair: David Phillips
Practical implementations and models using approximation algorithms

Carrasco Experimental results of approximation algorithms for energy aware scheduling [...]
Asgeirsson Performance of distributed game theoretic algorithms for single slot scheduling in wireless networks [...]
Phillips Scheduling and planning magnetic resonance imaging machines [...]

 

15:15 - 16:45, room: H 3010

Chair: Sylvia Boyd and David Shmoys
Travelling salesman problem II

Singh A randomized rounding approach to the traveling salesman problem [...]
Mömke Approximationg graphic TSP by matchings [...]
Mucha 13/9-approximation for graphic TSP [...]

 

 

Wednesday


10:30 - 12:00, room: H 3010

Chair: Asaf Levin
Scheduling and packing: Approximation with algorithmic game theory in mind

Epstein Generalized selfish bin packing [...]
Levin A unified approach to truthful scheduling on related machines [...]
van Stee The price of anarchy for selfish ring routing is two [...]

 

13:15 - 14:45, room: H 3010

Chair: Nicole Megow and Jose Correa
Approximation in routing and scheduling

Soto The traveling salesman problem in cubic graphs [...]
Verschae The power of recourse for online MST and TSP [...]
Telha The jump number (maximum independent set) of two-directional orthogonal-ray graphs [...]

 

15:15 - 16:45, room: H 3010

Chair: Maxim Sviridenko
Randomized rounding algorithms in mathematical programming

Nagarajan Thresholded covering algorithms for robust and max-min optimization [...]
Im Preemptive and non-preemptive generalized min sum set cover [...]
Srinivasan Dependent rounding and its applications [...]

 

 

Thursday


10:30 - 12:00, room: H 3010

Chair: Naonori Kakimura
Approximation algorithms

Williamson A dual-fitting 3⁄2-approximation algorithm for some minimum-cost graph problems [...]
Kolliopoulos Planar disjoint-paths completion [...]
Kakimura Computing knapsack solutions with cardinality robustness [...]

 

13:15 - 14:45, room: H 3010

Chair: Nicole Megow
Scheduling, packing and covering

Höhn On the performance of Smith's rule in single-machine scheduling with nonlinear cost [...]
Dürr Packing and covering problems on the line as shortest path problems [...]
Souza Approximation algorithms for generalized and variable-sized bin covering [...]

 

15:15 - 16:45, room: H 3010

Chair: Lisa Fleischer
Online algorithms

Madry A polylogarithmic-competitive algorithm for the k-server problem [...]
Bhaskar Online mixed packing and covering [...]
Mirrokni Simultaneous adversarial and stochastic approximations for budgeted allocation problems [...]

 

 

Friday


10:30 - 12:00, room: H 3010

Chair: Ignacio Javier Vargas
Approximation of vehicle routing problems

van Brink Express delivery of packages [...]
Vargas An efficient decision making process for vehicle operations in underground mining based on a mixed-integer programming model [...]
Bartolini The single-vehicle dial-a-ride problem [...]

 

13:15 - 14:45, room: H 3010

Chair: Chris Potts
Scheduling and online algorithms

Grigoriu Scheduling on uniform processors with at most one downtime on each machine [...]
Flatberg Online bin covering with lookahead and bounded space [...]
Potts On-line production planning to maximize on-time orders [...]

 

15:15 - 16:45, room: H 3010

Chair: Nicole Megow
Routing and shortest paths

Bonifaci Physarum can compute shortest paths [...]
Matuschke Approximation algorithms for capacitated location routing [...]
Sitters Metrical service systems and the generalized work function algorithm [...]

 

 

Program -> Parallel Sessions -> Cluster List -> Details all clusters
Search talks included | sessions only
  Payday Loans In Indiana. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.