Arrow Research search

Author name cluster

Stefan Langerman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers
2 author rows

Possible papers

15

TCS Journal 2022 Journal Article

Fragile complexity of adaptive algorithms

  • Prosenjit Bose
  • Pilar Cano
  • Rolf Fagerberg
  • John Iacono
  • Riko Jacob
  • Stefan Langerman

The fragile complexity of a comparison-based algorithm is f ( n ) if each input element participates in O ( f ( n ) ) comparisons. In this paper, we explore the fragile complexity of algorithms adaptive to various restrictions on the input, i. e. , algorithms with a fragile complexity parameterized by a quantity other than the input size n. We show that searching for the predecessor in a sorted array has fragile complexity Θ ( log ⁡ k ), where k is the rank of the query element, both in a randomized and a deterministic setting. For predecessor searches, we also show how to optimally reduce the amortized fragile complexity of the elements in the array. We also prove the following results: Selecting the kth smallest element has expected fragile complexity O ( log ⁡ log ⁡ k ) for the element selected. Deterministically finding the minimum element has fragile complexity Θ ( log ⁡ ( Inv ) ) and Θ ( log ⁡ ( Runs ) ), where Inv is the number of inversions in a sequence and Runs is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity O ( log ⁡ ( Runs ) + log ⁡ log ⁡ n ) and Θ ( log ⁡ ( Inv ) ). Deterministic sorting has fragile complexity Θ ( log ⁡ ( Inv ) ) but it has fragile complexity Θ ( log ⁡ n ) regardless of the number of runs.

Details DOI

SODA Conference 2020 Conference Paper

Competitive Online Search Trees on Trees

  • Prosenjit Bose
  • Jean Cardinal
  • John Iacono
  • Grigorios Koumoutsos
  • Stefan Langerman

We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online O (log log n )-competitive search tree data structure in this model, matching the best known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one which we call Steiner-closed search trees, which may be of independent interest. Moreover our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees, and secondly from these trees into paths.

Details

TCS Journal 2018 Journal Article

Threes!, Fives, 1024!, and 2048 are hard

  • Stefan Langerman
  • Yushi Uno

We analyze the computational complexity of the popular computer games Threes! , 1024! , 2048 and many of their variants. For most known versions expanded to an m × n board, we show that it is NP-hard to decide whether a given starting position can be played to reach a specific (constant) tile value.

Details DOI

SODA Conference 2016 Conference Paper

Weighted dynamic finger in binary search trees

  • John Iacono
  • Stefan Langerman

It is shown that the online binary search tree data structure GreedyASS performs asymptotically as well on a sufficiently long sequence of searches as any static binary search tree where each search begins from the previous search (rather than the root). This bound is known to be equivalent to assigning each item i in the search tree a positive weight w i and bounding the search cost of an item in the search sequence s 1, …, s m This result is the strongest finger-type bound to be proven for binary search trees. By setting the weights to be equal, one observes that our bound implies the dynamic finger bound. Compared to the previous proof of the dynamic finger bound for Splay trees, our result is significantly shorter, stronger, simpler, and has reasonable constants.

Details

SODA Conference 2014 Conference Paper

The Complexity of Order Type Isomorphism

  • Greg Aloupis
  • John Iacono
  • Stefan Langerman
  • Özgür Özkan
  • Stefanie Wuhrer

The order type of a point set in ℝ d maps each ( d +1)-tuple of points to its orientation (e. g. , clockwise or counterclockwise in ℝ 2 ). Two point sets X and Y have the same order type if there exists a mapping f from X to Y for which every ( d +1)-tuple ( a 1, a 2, …, a d +1 ) of X and the corresponding tuple ( f ( a 1 ), f ( a 2 ), …, f ( a d +1 )) in Y have the same orientation. In this paper we investigate the complexity of determining whether two point sets have the same order type. We provide an O ( n d ) algorithm for this task, thereby improving upon the O ( n ⌊3 d /2⌋ ) algorithm of Goodman and Pollack (1983). The algorithm uses only order type queries and also works for abstract order types (or acyclic oriented matroids). Our algorithm is optimal, both in the abstract setting and for realizable points sets if the algorithm only uses order type queries.

Details

SODA Conference 2009 Conference Paper

Decomposition of multiple coverings into more parts

  • Greg Aloupis
  • Jean Cardinal
  • Sébastien Collette
  • Stefan Langerman
  • David Orden
  • Pedro Ramos 0001

We prove that for every centrally symmetric convex polygon Q, there exists a constant α such that any αk -fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Tóth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.

Details

TCS Journal 2009 Journal Article

Improved approximation bounds for edge dominating set in dense graphs

  • Jean Cardinal
  • Stefan Langerman
  • Eythan Levy

We analyze the simple greedy algorithm that iteratively removes the endpoints of a maximum-degree edge in a graph, where the degree of an edge is the sum of the degrees of its endpoints. This algorithm provides a 2-approximation to the minimum edge dominating set and minimum maximal matching problems. We refine its analysis and give an expression of the approximation ratio that is strictly less than 2 in the cases where the input graph has n vertices and at least ϵ ( n 2 ) edges, for ϵ > 1 / 2. This ratio is shown to be asymptotically tight for ϵ > 1 / 2.

Details DOI

TCS Journal 2005 Journal Article

Designing small keyboards is hard

  • Jean Cardinal
  • Stefan Langerman

We study the problem of placing symbols of an alphabet onto the minimum number of keys of a small keyboard so that any word of a given dictionary can be recognized univoquely only by looking at the corresponding sequence of keys. This problem is motivated by the design of small keyboards for mobile devices. We show that the problem is hard in general, and NP-complete even if we only wish to decide whether two keys are sufficient. We also consider two variants of the problem. In the first one, symbols on a key must be contiguous in an ordered alphabet. In the second variant, a well-chosen measure of ambiguity in the recognition of the words is minimized given the number of keys. Hardness and approximability results are given.

Details DOI