Seminář G²OAT: Approximation Algorithms for Orthogonal Line Centers

Kdy

20. 11. 2023
13:00 – 14:00

Kde

Místnost TH:A-1247

Thákurova 7, Praha 6

V rámci pravidelného pondělního semináře skupiny G²OAT vystoupí Arun Kumar Das z Katedry teoretické informatiky FIT ČVUT. Během své odborné přednášky představí „approximation algorithms for orthogonal line centers“. 

Web akce

Abstrakt

The problem of orthogonal line center is about computing a set of axis-parallel lines for a given set of points in such that the maximum among the distances between each point to its nearest line is minimized. A -factor approximation algorithm and a bi-criteria approximation algorithm are presented for the problem. Both of them are deterministic approximation algorithms using combinatorial techniques and having sub-quadratic running times.

Za obsah stránky zodpovídá: Bc. Veronika Dvořáková