The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...
Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been ...
Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...
We show that the Chow covectors of a linkage matching field define a bijection of lattice points and we demonstrate how one can recover the linkage matching field from this bijection. This resolves two open questions from Sturmfels & Zelevinsky (1993) on l ...
Treatment of patients bearing human papillomavirus (HPV)-related cancers with synthetic long-peptide (SLP) therapeutic vaccines has shown promising results in clinical trials against premalignant lesions, whereas responses against later stage carcinomas ha ...
Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question:How can we design efficient algorithms for large-scale computation?In this thesis, we focus on devising a general strategy to addr ...
We present an efficient matching method for generalized geometric graphs. Such graphs consist of vertices in space connected by curves and can represent many real world structures such as road networks in remote sensing, or vessel networks in medical imagi ...
The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...
A bipartite graph G is semi-algebraic in R-d if its vertices are represented by point sets P,Q subset of R-d and its edges are defined as pairs of points (p,q) epsilon P x Q that satisfy a Boolean combination of a fixed number of polynomial equations and i ...
Suppose k is a positive integer and X is a k-fold packing of the plane by infinitely many arc-connected compact sets, which means that every point of the plane belongs to at most k sets. Suppose there is a function f(n) = o(n(2)) with the property that any ...
