BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Christophe Weibel

Christophe Weibel appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete MathematicsComputational GeometryData Structures and Algorithmsmath.CO

Catalog footprint

What is connected

6works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2016arXiv

Connectivity graphs of uncertainty regions

We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorable Best-Case Uncertainty (BU), each input point can be chosen from a given set to yield the best possible objective value. In the unfavorable Worst-Case Uncertainty (WU), the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the following Best-Case Connectivity with Uncertainty (BCU) problem: Given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there are n+k regions, where k of the regions are line segments and n of the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the corresponding Worst-Case Connectivity with Uncertainty (WCU) problem: Given a set of uncertainty regions, find the minimal distance r such that for any choice of points, one per region, there is a spanning tree among the points with edge length at most r.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The width of 5-dimensional prismatoids

Santos' construction of counter-examples to the Hirsch Conjecture (2012) is based on the existence of prismatoids of dimension d of width greater than d. Santos, Stephen and Thomas (2012) have shown that this cannot occur in $d \le 4$. Motivated by this we here study the width of 5-dimensional prismatoids, obtaining the following results: - There are 5-prismatoids of width six with only 25 vertices, versus the 48 vertices in Santos' original construction. This leads to non-Hirsch polytopes of dimension 20, rather than the original dimension 43. - There are 5-prismatoids with $n$ vertices and width $Ω(\sqrt{n})$ for arbitrarily large $n$. Hence, the width of 5-prismatoids is unbounded.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks

Let $G=(V,E)$ be a supply graph and $H=(V,F)$ a demand graph defined on the same set of vertices. An assignment of capacities to the edges of $G$ and demands to the edges of $H$ is said to satisfy the \emph{cut condition} if for any cut in the graph, the total demand crossing the cut is no more than the total capacity crossing it. The pair $(G,H)$ is called \emph{cut-sufficient} if for any assignment of capacities and demands that satisfy the cut condition, there is a multiflow routing the demands defined on $H$ within the network with capacities defined on $G$. We prove a previous conjecture, which states that when the supply graph $G$ is series-parallel, the pair $(G,H)$ is cut-sufficient if and only if $(G,H)$ does not contain an \emph{odd spindle} as a minor; that is, if it is impossible to contract edges of $G$ and delete edges of $G$ and $H$ so that $G$ becomes the complete bipartite graph $K_{2,p}$, with $p\geq 3$ odd, and $H$ is composed of a cycle connecting the $p$ vertices of degree 2, and an edge connecting the two vertices of degree $p$. We further prove that if the instance is \emph{Eulerian} --- that is, the demands and capacities are integers and the total of demands and capacities incident to each vertex is even --- then the multiflow problem has an integral solution. We provide a polynomial-time algorithm to find an integral solution in this case. In order to prove these results, we formulate properties of tight cuts (cuts for which the cut condition inequality is tight) in cut-sufficient pairs. We believe these properties might be useful in extending our results to planar graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Flow-Cut Gaps for Integer and Fractional Multiflows

Consider a routing problem consisting of a demand graph H and a supply graph G. If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there is a feasible multiflow for H if each edge of G is given capacity C. The flow-cut gap can be greater than 1 even when G is the (series-parallel) graph K_{2,3}. In this paper we are primarily interested in the "integer" flow-cut gap. What is the minimum value C such that there is a feasible integer valued multiflow for H if each edge of G is given capacity C? We conjecture that the integer flow-cut gap is quantitatively related to the fractional flow-cut gap. This strengthens the well-known conjecture that the flow-cut gap in planar and minor-free graphs is O(1) to suggest that the integer flow-cut gap is O(1). We give several results on non-trivial special classes of graphs supporting this conjecture and further explore the "primal" method for understanding flow-cut gaps. Our results include: - Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is compliant if its endpoints are joined by a directed path in the resulting oriented graph. If the cut condition holds for a compliant instance and G+H is Eulerian, then an integral routing of H exists. - The integer flow-cut gap in series-parallel graphs is 5. We also give an explicit class of instances that shows via elementary calculations that the flow-cut gap in series-parallel graphs is at least 2-o(1); this simplifies the proof by Lee and Raghavendra. - The integer flow-cut gap in k-Outerplanar graphs is c^{O(k)} for some fixed constant c. - A simple proof that the flow-cut gap is O(\log k^*) where k^* is the size of a node-cover in H; this was previously shown by Günlük via a more intricate proof.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Maximal f-vectors of Minkowski sums of large numbers of polytopes

It is known that in the Minkowski sum of $r$ polytopes in dimension $d$, with $r<d$, the number of vertices of the sum can potentially be as high as the product of the number of vertices in each summand. However, the number of vertices for sums of more polytopes was unknown so far. In this paper, we study sums of polytopes in general orientations, and show a linear relation between the number of faces of a sum of $r$ polytopes in dimension $d$, with $r\geq d$, and the number of faces in the sums of less than $d$ of the summand polytopes. We deduce from this exact formula a tight bound on the maximum possible number of vertices of the Minkowski sum of any number of polytopes in any dimension. In particular, the linear relation implies that a sum of $r$ polytopes in dimension $d$ has a number of vertices in $O(n^{d-1})$ of the total number of vertices in the summands, even when $r\geq d$. This bound is tight, in the sense that some sums do have that many vertices.

0 citations0 reviewsNo code linkedOpen access