Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program
We show that solving linear programming (LP) relaxations of many classical NP-hard combinatorial optimization problems (set cover/packing, facility location, maximum satisfiability, maximum independent set, multiway cut, three-dimensional matching, and constraint satisfaction) is as hard as solving the general LP problem. Precisely, the general LP can be reduced in nearly linear time to the LP relaxation of each of these problems. This result poses a limitation on designing algorithms to compute exact or even approximate solutions to the LP relaxations, as any lower bound on the complexity of solving the general LP problem is inherited by the LP relaxations.
D. Prusa, T. Werner (2019), Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program, SIAM Journal on Optimization. (PDF)
Learning CNNs from weakly annotated images
We show how to learn CNNs for face recognition using weakly annotated images where the annotation is assigned to a set of candidate faces rather than a single face like in the standard supervised setting. We use our method to create a database containing more than 300k faces of celebrities each annotated with his/her biological age, gender and identity.
Probabilistic model for joint segmentation, detection and tracking
We have developed a novel method for joint segmentation, detection and tracking of multiple objects. The method is based on a probabilistic model that is defined implicitly in terms of a Markov chain Monte Carlo algorithm. The parameters of the model are learned using an objective based on empirical risk minimization. Our method was used by researchers from the Cells-in-Motion (CiM) Cluster of Excellence at the University of Münster for analysing the molecular mechanisms of motion and contact dynamics of endothelial cells when they form new blood vessels (full story). This work led to a joint publication in Nature Communications.
Jiahui Cao et al. (2017), Polarized actin and VE-cadherin dynamics regulate junctional remodelling and cell migration during sprouting angiogenesis, Nature Communications 8(1), (paper)
License Plate recognition and Super-resolution from Low-Resolution Videos We developed CNN architecture recognizing license plates from a sequence of low-resolution videos. Our system works reliably on videos which are unreadable by humans. We also show how to a generate super-resolution LP images from low-res videos.
V.Vasek, V. Franc, M. Urban (2018), License Plate Recognition and Super-resolution from Low-Resolution Videos by Convolutional Neural Networks, Proc. of British Machine Vision Conference. (PDF, BibTex)