לוח שנה משולב

The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and $k$ designated terminals. The goal is to partition the vertices of the graph into~$k$ parts, each containing exactly one of the terminals, such that the sum of weights of the edges connecting vertices in different parts of the partition is minimized. The problem is APX-hard for $k\ge3$. The currently best-known approximation algorithm for the problem for arbitrary~$k$, obtained by Sharma and Vondr\'ak [STOC 2014] more than a decade ago, has an approximation ratio of 1.2965. We present an algorithm with an improved approximation ratio of 1.2787. Also, for small values of $k \ge 4$ we obtain the first improvements in 25 years over the currently best approximation ratios obtained by Karger, Klein, Stein, Thorup, and Young [STOC 1999]. (For $k=3$ an optimal approximation algorithm is known.)

Our main technical contributions are new insights on rounding the LP relaxation of C{\u{a}}linescu, Karloff, and Rabani [STOC 1998], whose integrality ratio matches Multiway Cut's approximability ratio, assuming the Unique Games Conjecture [Manokaran, Naor, Raghavendra, and Schwartz, STOC 2008]. First, we introduce a generalized form of a rounding scheme suggested by Kleinberg and Tardos [FOCS 1999] and use it to replace the Exponential Clocks rounding scheme used by Buchbinder, Naor, and Schwartz [STOC 2013] and by Sharma and Vondr\'ak. Second, while previous algorithms use a mixture of two, three, or four basic rounding schemes, each from a different family of rounding schemes, our algorithm uses a computationally-discovered mixture of hundreds of basic rounding schemes, each parametrized by a random variable with a distinct probability distribution, including in particular many different rounding schemes from the same family. We give a completely rigorous analysis of our improved algorithms using a combination of analytical techniques and interval arithmetic.

Joint work with Joshua Brakensiek, Neng Huang and Aaron Potechin.

Lessons learned from our experience in Pepticom as far as the vision and execution: Business plan, building a team, raising capital, pivoting on ideas, securing deals and more.   

Dear Colleagues,As part of the Multidisciplinary Vesicle Program Webinar Series, we are pleased to invite you to a special webinar entitled: "Introduction to Analytical Ultracentrifugation (AUC)" This session will provide an overview of Analytical Ultracentrifugation (AUC) and its applications in the characterization of extracellular vesicles, nanoparticles, macromolecular complexes and other biological systems. The webinar will highlight the principles of sedimentation analysis, methodological considerations and the advantages of AUC as a powerful label free analytical platform for assessing size distribution, heterogeneity, aggregation state and sample purity. The session is intended for researchers interested in advanced biophysical characterization approaches and scalable analytical solutions for EV and nanoparticle research.