Category Combinatorial Optimization

Denoising binary images

Data science is transforming the world: we already see self-driving cars moving from research to production, data-driven cancer diagnostic systems, machine learning trader bots and lots of other exciting technologies because the corresponding problems have been reduced to understanding data. While the science of data for centuries was known as statistics, computer scientists, together with […]

Provably Fast Inference of Latent Features from Networks

Latent feature learning: where overlapping communities, correlation clustering, binary matrix factorization and extremal graph theory meet Motivation: Suppose we are given the following. Agents: Five agents, represented by . Binary vertex features. An agent can either be interested or not in each out of three news categories business, entertainment, sports.  Each interest is represented by a […]

Knapsack formulations

Integer programming is all about formulations. Preferably tight formulations. I will show you here two equivalent formulations of the famous knapsack problem. Knapsack problem: Given a set of weights of objects, a knapsack of capacity and  values select a subset of objects such that their total weight is less than and the total value is maximized. Let’s […]