Profile



Areas of Expertise: Problem Solving | Software Engineering | Algorithms | Statistical Data Analysis | Communication

Education

Ph.D. Computer Science

The Graduate Center, CUNY, NY, USA

Fulbright Scholar
Focus: Discrete and Approximation Algorithms

M.Sc. Computer Science

ETH Zürich, Switzerland

Focus: Algorithms, Graph Theory, Machine Learning, Computational Statistics

B.Sc. Information Technology

Zürich University of Applied Sciences, Switzerland

Focus: Software Systems, Computer Systems, Computer Networks

Apprenticeship in Business Informatics

Swiss Re, Zürich, Switzerland

Focus: Software Engineering, Business Studies, Project Management

Work Experience

Data Science & Software Engineering

Algorithms Engineer

Driversiti

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.

Open Source Software Contribution

Google (Summer of Code) / CGAL

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

Computational Statistician

Smava GmbH, Berlin, Germany

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.

Research Intern

IBM Research, Zürich, Switzerland

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


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

Software Engineer

University of Zürich, Switzerland

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.

SQL Developer

Swiss Re, Zürich, Switzerland

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

Entrepreneurial Work

Startup Co-Founder

Rumr, New York

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.

Teaching (Adjunct Lecturer)

Course Instructor

City College, CUNY, New York

Discrete Mathematics

Data Structures & Algorithms


Selected course material, prepared and graded assignments and examinations.

Lab Instructor

Queens College, CUNY, New York

Advanced C++

Advanced Java

Visual Basic


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

Research Assistant

Network Science Collaborative Technology Alliance

NS-CTA, Graduate Center, CUNY, New York

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

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

Strategy Problems for Robots and Sensor Networks

NSF-CCF, City College, CUNY, New York

Researched the exploration of graphs by multiple robots.

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

Pattern Recognition and Machine Learning Lab

Graduate Center, CUNY, New York

Researched and implemented novel approaches to visualize high dimensional data.

Research

Journal Publications

Shortest Path Planning for a Tethered Robot

Joint work with Peter Braß and Ning Xu
Computational Geometry, 48 (9)

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(kn2 log n) time algorithm to find the shortest path between the source and the destination point. This improves the previous O(lkn3) 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.

On Packing R3 With Thin Tori

Discrete & Computational Geometry, 51 (3)

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.

On Separating Families of Bipartitions

Joint work with Takahisa Toda
Discrete Mathematics, 313 (3)

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.

On Separating Convex Points with Lines

Joint work with Takahisa Toda
Congressus Numerantium, 214

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.

Conference Publications

Improved Approximation Algorithms for Weighted 2-path and Triangle Partitions

Joint work with Amotz Bar-Noy, David Peleg and George Rabanca
ESA (European Symposium on Algorithms), 953-964

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.

Improved Analysis of a Multirobot Graph Exploration Strategy

Joint work with Peter Braß and Ning Xu
In Proceedings of ICARCV 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.

Packing and Covering a Polygon with Geodesic Disks

Mexican Conference on Discrete Mathematics and Computational Geometry, Oaxaca, Mexico

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.

Range-Aggregate Queries for Geometric Extent Problems

Joint work with Peter Braß, Christian Knauer, Chan-Su Shin and Michiel Smid
Computing: the Australasian Theory Symposium, Melbourne, Australia
​

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.

Under Submission

Covering a Polygon Boundary with Geodesic Unit Disk

Joint work with George Rabanca

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 log2 n + k) time 2-approximation algorithm for finding the centers of the disks, with k denoting the number of centers found by the algorithm.

On Isolating Points Using Unit Disks

Joint work with Matt Gibson, Gaurav Kanade, Rainer Penninger and Kasturi Varadarajan

Given a set of disks (that we think of as wireless sensors) and a set of points in the plane, we consider the problem of selecting a minimum 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. Using a similar hardness reduction, we further show that removing a minimum subset of a given 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. Lastly, we show that the Multiterminal Cut problem remains NP-complete on unit disk graphs.