#### Natural Language Processing Research Scientist

##### Bloomberg LP

Researching and developing algorithms for natural language processing.

since 4/2016

Researching and developing algorithms for natural language processing.

4/2015 - 4/2016

Lead developer & lead architect of core algorithm library in C++:

- - Implemented machine learning algorithms to infer driving behavior from smart phone sensors data.
- - Developed a restAPI for a spatial database on AWS involving EC2, RDS (PostGis), S3, ELB, Gunicorn
- Build master & release manager: - Set up Continuous Integration environment, issued tickets, enforced unit testing.

5/2014 - 8/2014

Finalized the implementation of a 2D Reconstruction and Simplification Algorithm for Point Sets. Designed and documented an API, refactored and optimized prototype code accordingly, wrote Multiplatform Unit Tests and adapted a Qt demo.

Tools: C++11, Boost Graph Library, Template Programming, CMake, Git

1/2013 - 9/2013

Based on a record of 55'000 users and 8 banks, inferred bank-acceptance probability for new users.

Selected relevant features from 130 user attributes.

Implemented and evaluated inference quality of 4 different statistical classification models in R.

6/2012 - 8/2012

Researched and implemented a (column generation) Linear Programming approach for Railway Scheduling.

Tools: C++, Lemon Graph Library, CPLEX, OPL

2/2006 - 4/2009

Developed an Eclipse plug-in for modeling software requirements.

Designed and implemented algorithms for visualizing large requirement models in Eclipse.

Implemented a complex 3-valued truth maintenance system, using boolean satisfiability solving.

Generated a parser for a formal language with 300 rules, used to analyze its graph structure.

Designed Unit tests and integrated databases.

1/2001 - 9/2001

Implementation of underwriting applications in SQL and COBOL on a mainframe system.

5/2013 - 12/2014

A service for finding apartment rentals using social networks.

Rumr got bought 1/2015.

Analyzed markets and competitors, created a business model, planed projects, implemented front and back end.

1/2010 - 5/2011

Discrete Mathematics

Data Structures & Algorithms

Selected course material, prepared and graded assignments and examinations.

9/2010 - 5/2013

Advanced C++

Advanced Java

Visual Basic

Gave detailed feedback on problem solutions and source code, graded examinations.

6/2014 - 12/2014

Developed deterministic and randomized approximation algorithms for optimization problems on graphs.

Proved bounds on approximation ratio and running time to improve upon prior art.

9/2010 - 5/2014

Researched the exploration of graphs by multiple robots.

Researched an efficient algorithm for navigating a tethered robot in an obstacle domain.

9/2009 - 5/2010

Researched and implemented novel approaches to visualize high dimensional data.

2009 - 3/2015

2006 - 2009

2002 - 2006

1998 - 2001

2016

Given a set of points in the plane and a set of disks which separate the points, we consider the problem of selecting a minimum size subset of the disks such that any path between any pair of points is intersected by at least one of the selected disks. We present a (9 + ε)-approximation algorithm for this problem and show that it is NP-complete even if all disks have unit radius and no disk contains any points. Using a similar reduction, we further show that the Multiterminal Cut problem remains NP-complete on unit disk graphs. Lastly, we prove that removing a minimum subset of a collection of unit disks, such that the plane minus the arrangement of the remaining disks consists of a single connected region is also NP-complete.

2015

We consider the problem of finding the shortest path for a tethered robot in a planar environment with polygonal obstacles on n total vertices.
The robot is attached to an anchor point by a tether of finite length. The robot can cross the tether; i.e.
the tether can be self-intersecting. Neither the robot nor the tether may enter the interior of any obstacle.
The initial tether configuration is given as a polyline of k vertices.
If the tether is automatically retracted and kept taut, we present a O(kn^{2} log n)
time algorithm to find the shortest path between the source and the destination point.
This improves the previous O(lkn^{3}) time algorithm [Xavierâ€™99, ICRA. pp. 1011-1017], where l
is the number of loops in the initial tether configuration. If the tether can only be retracted while the robot backtracks along the tether,
we present an algorithm to find the shortest path in O((n + log k)log n) time.

2014

We show that R ^{ 3 } can be packed at a density of 0.222... with tori whose minor radius goes to zero. Furthermore, we show that the same torus arrangement yields an asymptotically optimal number of pairwise linked tori.

2013

We focus on families of bipartitions, i.e. set partitions consisting of at most two components. A family of bipartitions is a separating family for a set if every two elements in the set are separated by some bipartition. In this work we enumerate separating families of arbitrary size. We furthermore enumerate inclusion-wise minimal separating families of minimum and maximum sizes.

2012

For a set S of n points in the plane a linear bipartition P of S is a set {U, S\U } consisting of two disjoint nonempty subsets of S which respectively are fully contained in the two open half-planes bounded by some line. A set P of linear bipartitions is called a linear separating family for S if every two elements in S are separated by some bipartition in P. In addition, P is called minimal, if no proper subset of P is a separating family for S. For the case where the points in S are in convex position, we present a bijection between the set of all minimal linear separating families and a restricted class of edge covers. Using this bijection we enumerate minimal separating families of minimum size and maximum size.

2015

We investigate two NP-complete vertex partition problems on {0,1}-edge-weighted complete graphs with 3k vertices. The first problem asks to partition the graph into k vertex disjoint paths of length 2 (referred to as 2-paths) such that the total weight of the paths is maximized. ]For this problem, we present a .75-approximation algorithm, improving upon the .55-approximation algorithm of Hassin et al. Combining this algorithm with a previously known approximation algorithm for the 3-Set Packing problem, we obtain a .6-approximation algorithm for the problem of partitioning a {0,1}-edge-weighted graph into k vertex disjoint triangles of maximum total weight. The best known approximation algorithm for general weights achieves an approximation ratio of .5257.

2014

We show that the Multirobot DFS algorithm proposed in IEEE Transactions on Robotics (2011) by Braß et al. for the multirobot exploration on trees is also good on graphs with ω(n) edges among n vertices, but we give an adversarial construction that shows it is not good on sparse cyclic graphs.

2013

Given a polygon P, for two points s and t contained in the polygon, their geodesic distance is the length of the shortest st-path within P. A geodesic disk of radius r centered at a point v in P is the set of points in P whose geodesic distance to v is at most r. We present a polynomial time 2-approximation algorithm for finding a densest geodesic unit disk packing in P. Allowing arbitrary radii but constraining the number of disks to be k, we present a 4-approximation algorithm for finding a packing in P with k geodesic disks whose minimum radius is maximized. We then turn our focus on coverings of P and present a 2-approximation algorithm for covering P with k geodesic disks whose maximal radius is minimized. Furthermore, we show that all these problems are NP-hard in polygons with holes. Lastly, we present a polynomial time exact algorithm which covers a polygon with two geodesic disks of minimum maximal radius.

2012

â€‹

Let S be a set of n points in the plane. We present data structures that solve range-aggregate query problems on three geometric extent measure problems. Using these data structures, we can report, for any axis-parallel query rectangle Q, the area/perimeter of the convex hull, the width, and the radius of the smallest enclosing disk of the points in S ∩ Q.

2015

We consider the problem of covering the boundary of a simple polygon on
n vertices using the minimum number of geodesic unit disks. We present an
O(n log^{2} n + k) time 2-approximation algorithm for finding the centers of the disks,
with k denoting the number of centers found by the algorithm.