We develop the algorithmic theory of vertex separators, and its relation to the embeddings of
certain metric spaces. Unlike in the edge case, we show that embeddings into L1 (and even …

Assuming that NP \not⊆ ϵ>0 BPTIME (2^n^ϵ), we show that graph min-bisection, dense k-
subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We …

We consider the following problem: There is a set of items (eg, movies) and a group of
agents (eg, passengers on a plane); each agent has some intrinsic utility for each of the …

Brands and agencies use marketing as a tool to influence customers. One of the major
decisions in a marketing plan deals with the allocation of a given budget among media …

The Small Set Expansion Hypothesis is a conjecture which roughly states that it is NP-hard
to distinguish between a graph with a small subset of vertices whose (edge) expansion is …

We consider the unit-demand min-buying pricing problem, in which we want to compute
revenue maximizing prices for a set of products P assuming that each consumer from a set …

We prove an improved hardness of approximation result for two problems, namely, the
problem of finding the size of the largest clique in a graph and the problem of finding the …

We consider the algorithmic problem of finding large balanced independent sets in sparse
random bipartite graphs, and more generally the problem of finding independent sets with …

Given a graph G and an integer k, the k-Biclique problem asks whether G contains a
complete bipartite subgraph with k vertices on each side. Whether there is an f (k) ċ| G| O (1) …

We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut
problem. So far, these two notorious NP-hard graph problems have resisted all attempts to …