Archive for the ‘2013’ Category

Boris Aronov, The complexity of unions of shapes

Wednesday, December 18th, 2013
The complexity of unions of shapes
Boris Aronov
Department of Computer Science and Engineering
Polytechnic Institute of NYU
2013/12/20 Friday 4PM-5PM
Room 1409
Over the years, the following class of problems has been studied quite a lot: Given a class of simply-shaped objects in the plane (disks, unit disks, squares, axis-aligned squares, isosceles triangles, shapes definable with a small number of polynomial equations and inequalities), how complicated can be the union of N shapes from the class? There are several different ways in which one can measure this (combinatorial) complexity. Two popular measures are the number of connected components of the complement, and the number of places where two object boundaries intersect on the boundary of the union (so-called “vertices” of the union).

It is easy to see that, if each object is “simple,” the union of N objects cannot be larger than O(N^2) and a matching construction is easy. Are there classes of objects for which this quantity is near-linear in N? (Yes, there are: disks, axis-aligned squares, and more.) The quest for such classes, over the years, motivation for the problem, generalizations to higher dimensions, and other puzzles will constitute the content of this talk.

If I ever get to it, the latest and most amazing result in this area is joint work with Mark de Berg, Esther Ezra, and Micha Sharir. It is quite technical and I will not be able to say much about this during the talk, but if anyone is interested, I can provide lots of technical details on request. An overview of the subject will be mostly based on a survey of Agarwal, Pach, and Sharir.

Eunjung Kim (김은정), On subexponential and FPT-time inapproximability

Monday, November 18th, 2013
On subexponential and FPT-time inapproximability
Eunjung Kim
CNRS, LAMSADE, Paris, France
2013/12/18 Wednesday 4PM-5PM
Room 1409

Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between these different frameworks. In particular, whether Independent Set would be better approximable once allowed with subexponential-time or FPT-time is a central question. Recently, several independent results appeared regarding this question, implying negative answer toward the conjecture. They state that, for every 0<r<1, there is no r-approximation which runs in better than certain subexponential-function time. We outline the results in these papers and overview the important concepts and techniques used to obtain such results.

Hermanshu Kaul, Finding Large induced subgraphs and allocation of resources under dependeny

Tuesday, October 29th, 2013
Finding Large induced subgraphs and allocation of resources under dependeny
Hermanshu Kaul
Illinois Institute of Technology
2013/11/20 Wednesday 4PM-5PM
Room 1409

Given a graph, we are interested in studying the problem of finding an induced subgraph of a fixed order with largest number of edges. More generally, let G = (V, E) be an undirected graph, with a weight (budget) function on the vertices, w: V → ℤ+, and a benefit function on vertices and edges b: EV → ℤ. The benefit of a subgraph H =(VH,EH) is b(H) = ∑ v∈VH b(v) + ∑ e∈EH b(e) while its weight is w(H) = ∑ v∈VH w(v). What can be said about the maximum benefit of an induced subgraph with the restriction that its weight is less than W?

This problem is closely related to the Quadratic Knapsack Problem, the Densest Subgraph Problem, and classical problems in Extremal Graph Theory. We will discuss these connections, give applications in resource allocation, and present new results on approximation algorithms using methods from convex optimization and probability. This is joint work with Kapoor.

Suyoung Choi (최수영), The rational Betti number of small covers and its combinatorics

Tuesday, October 29th, 2013
The rational Betti number of small covers and its combinatorics
Suyoung Choi (최수영)
Department of Mathematics, Ajou University
2013/11/13 Wednesday 4PM-5PM
ROOM 1409

A small cover is a topological analogue of real toric varieties, and is an important object in toric topology. It is noted that the formula of the ℤ2-cohomology ring of small cover is well-known. However, the integral cohomology ring of small covers has not been known well.

In this talk, we discuss about the Betti numbers and its torsion of the small covers associated to some nestohedra including graph associahedra. Interestingly, the Betti numbers can be computed by purely combinatorial method (in terms of graphs and hypergraphs). To our surprise, for specific families of graphs, these numbers are deeply related to well-known combinatorial sequences such as the Catalan numbers and Euler zigzag numbers.

Yoshio Okamoto, Geometric weight balancing

Tuesday, October 29th, 2013
Geometric weight balancing
Yoshio Okamoto
Department of Communication Engineering and Informatics, UEC, Japan
2013/11/05 Tuesday 11AM – 12AM
Given a simple polygon P, a point t in P, and a set of positive weights, we want to place the weights on the boundary of P in such a way that their barycenter comes to t. We show that there is always such a placement if the weights are balanced, i.e., no weight is larger than half of the total weight, and the placement can be found efficiently. We also study three-dimensional versions of the problem.

Joint work with Luis Barba, Jean Lou De Carufel, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yuan Tang, Takeshi Tokuyama, Sander Verdonschot, and Tianhao Wang.