The hallmark of the Cooley-Tukey algorithm for Fast Fourier Transform is the butterfly network, which helps reduce O(N^2) computations to O(NlogN). Butterflies are very special graphs entangled in routing [Arora], switching [Chung], shuffling [Yang], and mixing [Czumaj].
Given a weighted connected component, what is the weight of of the maximum independent set, and how many different sets have this weight? A Petersen graph GP(5, 2) with zero vertex weights has three maximal subsets by size, 0 maximum set weight but 76 distinct independent sets with this weight. Continue reading
Gus wants to open franchises of his restaurant, Los Pollos Hermanos, along Central Avenue. There are n possible locations for franchises, where location i is at mile i on Central. Each location i > 1, is thus a distance of 1 mile from the previous one. There are two rules.
- At each location, there can be at most one restaurant, and the profit of a restaurant at location i is p_i.
- Any two restaurants must be at least 2 miles apart.
Min-max heaps were introduced in [ASSS86] as an efficient way to support heap operations for both minimum and maximum values. Structurally, the min-max heap levels alternate between min-heap condition and max-heap, and hence evaluates grandchildren/grandparents during insertion or search. Min-max heaps can also be generalized to find the k-th smallest element in O(1) time.
The aim of this post is to highlight the utility of non-negative factorization (NMF) in data analysis through examples. In a different post, we’ll talk theory and implementation by thinking of NMF as constrained optimization.
Learning parts of a whole
When Lee and Seung [Lee99] re-introduced non-negative matrix factorization (NMF), they emphasized on the algorithm’s ability to learn parts of a whole. Continue reading
 Bandits with concave rewards and convex knapsacks, Shipra Agrawal and Nikhil R. Devanur
Introduces and gives polynomial-time near-optimal algorithms for a general model for bandit exploration-exploitation. The algorithm is an extension of the Upper Confidence Bound (UCB) algorithm for the multi-armed bandits problem. The new framework allows them to give more efficient algorithms for other problems such as Blackwell approachability, online convex optimization and conditional-gradient/projection-free/Frank-Wolfe algorithm.
The Internet of 1986 underwent a congestion collapse as available bandwidth dropped by factor of 1000 (1). Transmission Control Protocol (TCP) was then enhanced with various algorithms, two in particular, to ensure that the network reached and stayed close to equilibrium. Continue reading
A problem I was asked: suppose a file that stored many valid IPv4 addresses was corrupted such that all dot in the addresses were removed. Given such a corrupt IP, infer all possible corresponding IP addresses. For example, given 12345, all possible addresses are: 184.108.40.206, 220.127.116.11, 18.104.22.168 and 22.214.171.124. The hint that recursion should be used made the problem easier: