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
  In particular, Texas Payday Loans can cater to the needs of its residents. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cheap Cialis was obtained in Europe, Australia, New Zealand.