research
∙
08/21/2023
Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs
In a right-angle crossing (RAC) drawing of a graph, each edge is represe...
share
research
∙
04/27/2023
A Parameterized Theory of PAC Learning
Probably Approximately Correct (i.e., PAC) learning is a core concept of...
research
∙
02/28/2022
Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts
Decompositional parameters such as treewidth are commonly used to obtain...
research
∙
11/15/2021
Sometimes, Convex Separable Optimization Is Much Harder than Linear Optimization, and Other Surprises
An influential 1990 paper of Hochbaum and Shanthikumar made it common wi...
research
∙
10/21/2020
A Note on the Approximability of Deepest-Descent Circuit Steps
Linear programs (LPs) can be solved through a polynomial number of so-ca...
research
∙
05/11/2020
An Algorithmic Method of Partial Derivatives
We study the following problem and its applications: given a homogeneous...
research
∙
12/07/2019
Parameterized Algorithms for MILPs with Small Treedepth
Solving (mixed) integer linear programs, (M)ILPs for short, is a fundame...
research
∙
04/25/2018
Extensor-Coding
We devise an algorithm that approximately computes the number of paths o...
research
∙
04/29/2016