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


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 [...]




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 [...]




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 [...]




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 [...]




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
  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Buy Viagra Online has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.