Publication
A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing
Related publications (56)
Monochromatic cycle covers in random graphs
A classic result of Erdos, Gyarfas and Pyber states that for every coloring of the edges of K-n with r colors, there is a cover of its vertex set by at most f(r)=O(r2logr) vertex-disjoint monochromatic cycles. In particular, the minimum number of such cove ...
WILEY2018Optimal Representations for Adaptive Streaming in Interactive Multiview Video Systems
Interactive multiview video streaming (IMVS) services permit to remotely navigate within a 3D scene with an immersive experience. This is possible by transmitting a set of reference camera views (anchor views), which are used by the clients to freely navig ...
Ieee-Inst Electrical Electronics Engineers Inc2017On the Zarankiewicz problem for intersection hypergraphs
Let d and t be fixed positive integers, and let denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem ...
Academic Press Inc Elsevier Science2016K-Adaptability in Two-Stage Distributionally Robust Binary Programming
Daniel Kuhn, Grani Adiwena Hanasusanto, Wolfram Wiesemann
We propose to approximate two-stage distributionally robust programs with binary recourse decisions by their associated K-adaptability problems, which pre-select K candidate second-stage policies here-and-now and implement the best of these policies once t ...
Elsevier Science Bv2016Incremental View Maintenance for Collection Programming
Christoph Koch, Daniel Lupei, Val Tannen
In the context of incremental view maintenance (IVM), delta query derivation is an essential technique for speeding up the processing of large, dynamic datasets. The goal is to generate delta queries that, given a small change in the input, can update the ...
ACM2016Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex
We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant such that whenever are n-element subsets of , we can find a point and subsets for every , each of size at least , suc ...
Springer2015Ramsey-Type Results For Semi-Algebraic Relations
A k-ary semi-algebraic relation E on R-d is a subset of R-kd, the set of k-tuples of points in R-d, which is determined by a finite number of polynomial inequalities in kd real variables. The description complexity of such a relation is at most t if d, k < ...
Amer Mathematical Soc2014Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme
Boi Faltings, Immanuel Trummer
The goal of multi-objective quality-driven service selection (QDSS) is to find service selections for a workflow whose quality-of-service (QoS) values are Pareto-optimal. We consider multiple QoS attributes such as response time, cost, and reliability. A s ...
Institute of Electrical and Electronics Engineers2014Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(vertical bar V vertical bar (vertical bar E vertical bar+vertical bar V vertical bar log vertical bar V vertical bar))-time, drastically improvin ...
Assoc Computing Machinery2014Ramsey-type results for semi-algebraic relations
A k-ary semi-algebraic relation E on R^d is a subset of R^{kd}, the set of k-tuples of points in R^d, which is determined by a finite number of polynomial equations and inequalities in kd real variables. The description complexity of such a relation is at ...
2013