BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computational Optimisation Group - ECPv6.15.11//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computational Optimisation Group
X-ORIGINAL-URL:http://optimisation.doc.ic.ac.uk
X-WR-CALDESC:Events for Computational Optimisation Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20170101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20181116T150000
DTEND;TZID=UTC:20181116T160000
DTSTAMP:20260513T052843
CREATED:20181001T084447Z
LAST-MODIFIED:20181001T084617Z
UID:1158-1542380400-1542384000@optimisation.doc.ic.ac.uk
SUMMARY:Seminar: Arrangements of Circles and Spheres leading to Convex Hulls with Minimal Boundaries
DESCRIPTION:Title: Arrangements of Circles and Spheres leading to Convex Hulls with Minimal Boundaries\nSpeaker: Dr Josef Kallrath\nAffiliation: Advanced Business Analytics\, BASF SE\, Germany\nLocation: 218 Huxley Building\nTime: 15:00 – 16:00 \nAbstract. We present and solve a new computational geometry optimization problem in 2D and 3D and provide theoretical insights. Circles (2D) and Spheres (3D) with given radii should be arranged in such a way that a) they do not overlap and b) the length of the perimeter or surface area\, resp.\, of the boundary ∂S of the convex hull S enclosing the spheres is minimized. An additional constraint could be to fit the spheres into a specified geometry\, e.g.\, a rectangle or a rectangular solid\, respectively. \nA motivation for the 2D problem is a rope to be minimized\, which encloses the circles\, where the circles could be the base of cylinders loaded an a truck with rectangular loading area. \nIn 2D\, ∂S is established by line segments and circular arcs. To tackle the problem\, we derive a non-convex mixed-integer non-linear programming (MINLP) formulation. We exploited the isoperimetric inequality to get a tighter lower bound for the perimeter than the lower bound obtained by the relaxation of the MINLP. As demonstrated in numerical experiments\, problem instances with only congruent circles are computational better tractable than non-congruent instances\, as for congruent instances only the line segments have to be minimized. For small instances with up to five non-congruent circles\, and minimizing only lL the MINLP problems we obtained gaps smaller than 10−4 with the current state-of-the-art global solvers BARON and LINDO available in GAMS. For larger problems of up to 90 circles\, the relative gap between the upper and lower bound provided by the global solvers remains larger than 7 %. \nIn 3D\, ∂S consists of spherical polygons with k vertices formed by k arcs of great circles\, triangles and truncated cones. Here\, we take a different approach than in the 2D situation. Similarly as in modeling the surface of eclipsing binary stars\, we cover the surface of the spheres by a grid of approximately uniformly distributed points using spherical coordinates. We derive closed non-convex NLP models for this sphere arrangement problem. \nFor two spheres\, we prove that the minimal area of ∂S is identical to the sum of the surface areas of the two spheres. For special configurations of spheres we provide theoretical insights and compute analytically minimal area configurations. Numerically\, we have solved problems containing up to 200 spheres using a polylithic modeling and solution approach.
URL:http://optimisation.doc.ic.ac.uk/event/seminar-arrangements-of-circles-and-spheres-leading-to-convex-hulls-with-minimal-boundaries/
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=UTC:20181128T160000
DTEND;TZID=UTC:20181128T170000
DTSTAMP:20260513T052843
CREATED:20180907T201315Z
LAST-MODIFIED:20181126T205541Z
UID:1145-1543420800-1543424400@optimisation.doc.ic.ac.uk
SUMMARY:Seminar: Capacity upper bounds for deletion-type channels
DESCRIPTION:Title: Capacity upper bounds for deletion-type channels\nSpeaker: Dr Mahdi Cheraghchi\nAffiliation: Dept of Computing\, Imperial College London\nLocation: 218 Huxley Building\nTime: 16:00 – 17:00 \nAbstract. We develop a systematic approach\, based on convex programming and real analysis\, for obtaining upper bounds on the capacity of the binary deletion channel and\, more generally\, channels with i.i.d. insertions and deletions. Other than the classical deletion channel\, we give a special attention to the Poisson-repeat channel introduced by Mitzenmacher and Drinea (IEEE Transactions on Information Theory\, 2006). Our framework can be applied to obtain capacity upper bounds for any repetition distribution (the deletion and Poisson-repeat channels corresponding to the special cases of Bernoulli and Poisson distributions). Our techniques essentially reduce the task of proving capacity upper bounds to maximizing a univariate\, real-valued\, and often concave function over a bounded interval. We show the following: \n1. The capacity of the binary deletion channel with deletion probability $d$ is at most $(1-d)log(phi)$ for $d > 1/2$\, and\, assuming the capacity function is convex\, is at most $1-d log(4/phi)$ for $d<1/2$\, where $phi=(1+sqrt{5})/2$ is the golden ratio. This is the first nontrivial capacity upper bound for any value of $d$ outside the limiting case $d to 0$ that is fully explicit and proved without computer assistance. \n2. We derive the first set of capacity upper bounds for the Poisson-repeat channel. \n3. We derive several novel upper bounds on the capacity of the deletion channel. All upper bounds are maximums of efficiently computable\, and concave\, univariate real functions over a bounded domain. In turn\, we upper bound these functions in terms of explicit elementary and standard special functions\, whose maximums can be found even more efficiently (and sometimes\, analytically\, for example for $d=1/2$). \nAlong the way\, we develop several new techniques of potentially independent interest in information theory\, probability\, and mathematical analysis. \n[Based on an article published in proceedings of ACM STOC 2018] \nBiography. Dr Mahdi Cheraghchi is a Lecturer in the Department of Computing at Imperial College London. Previously\, he has been a Qualcomm Research Fellow at the Simons Institute for the Theory of Computing of U.C. Berkeley and have held post-doctoral researcher positions at the MIT Computer Science and Artificial Intelligence Lab\, Computer Science Department of the Carnegie Mellon University and the University of Texas at Austin. He received his PhD in Computer Science from EPFL\, Switzerland\, where he worked as a research assistant in the Laboratory of Algorithms (ALGO) under the supervision of Amin Shokrollahi. Dr Cheraghchi main research interest is in the field of Theoretical Computer Science.
URL:http://optimisation.doc.ic.ac.uk/event/seminar-capacity-upper-bounds-for-deletion-type-channels/
END:VEVENT
END:VCALENDAR