Author name cluster

Michael Hoffmann

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.

6 papers

1 author row

TCS Journal 2018 Journal Article

Encoding nearest larger values

Michael Hoffmann
John Iacono
Patrick K. Nicholson
Rajeev Raman

In nearest larger value (NLV) problems, we are given an array A [ 1. . n ] of distinct numbers, and need to preprocess A to answer queries of the following form: given any index i ∈ [ 1, n ], return a “nearest” index j such that A [ j ] > A [ i ]. We consider the variant where the values in A are distinct, and we wish to return an index j such that A [ j ] > A [ i ] and | j − i | is minimized, the nondirectional NLV (NNLV) problem. We consider NNLV in the encoding model, where the array A is deleted after preprocessing. The NNLV encoding problem turns out to have an unexpectedly rich structure: the effective entropy (optimal space usage) of the problem depends crucially on details in the definition of the problem. Of particular interest is the tiebreaking rule: if there exist two nearest indices j 1, j 2 such that A [ j 1 ] > A [ i ] and A [ j 2 ] > A [ i ] and | j 1 − i | = | j 2 − i |, then which index should be returned? For the tiebreaking rule where the rightmost (i. e. , largest) index is returned, we encode a path-compressed representation of the Cartesian tree that can answer all NNLV queries in 1. 89997 n + o ( n ) bits, and can answer queries in O ( 1 ) time. An alternative approach, based on forbidden patterns, achieves a very similar space bound for two tiebreaking rules (including the one where ties are broken to the right), and (for a more flexible tiebreaking rule) achieves 1. 81211 n + o ( n ) bits. Finally, we develop a fast method of counting distinguishable configurations for NNLV queries. Using this method, we prove a lower bound of 1. 62309 n − Θ ( 1 ) bits of space for NNLV encodings for the tiebreaking rule where the rightmost index is returned.

Details DOI

TCS Journal 2016 Journal Article

Query-competitive algorithms for cheapest set problems under uncertainty

Thomas Erlebach
Michael Hoffmann
Frank Kammer

Considering the model of computing under uncertainty where element weights are uncertain but can be obtained at a cost by query operations, we study the problem of identifying a cheapest (minimum-weight) set among a given collection of feasible sets using a minimum number of queries of element weights. For the general case we present an algorithm that makes at most d ⋅ OPT + d queries, where d is the maximum cardinality of any given set and OPT is the optimal number of queries needed to identify a cheapest set. For the minimum multi-cut problem in trees with d terminal pairs, we give an algorithm that makes at most d ⋅ OPT + 1 queries. For the problem of computing a minimum-weight base of a given matroid, we give an algorithm that makes at most 2 ⋅ OPT queries, generalizing a known result for the minimum spanning tree problem. For each of the above algorithms we give matching lower bounds. We also settle the complexity of the verification version of the general cheapest set problem and the minimum multi-cut problem in trees under uncertainty.

Details DOI

TCS Journal 2010 Journal Article

Notions of hyperbolicity in monoids

Michael Hoffmann
Richard M. Thomas

We introduce a notion of hyperbolicity in monoids which is a restriction of that suggested by Duncan and Gilman. One advantage is that the notion gives rise to efficient algorithms for dealing with certain questions; for example, the word problem can be solved in time O ( n log n ). We also introduce a new way of defining automatic monoids which provides a uniform framework for the discussion of these concepts. Hyperbolic monoids (in the sense introduced here) turn out to be biautomatic.

Details DOI

TCS Journal 2006 Journal Article

A geometric characterization of automatic semigroups

Michael Hoffmann
Richard M. Thomas

In the study of automatic groups, the geometrical characterization of automaticity (in terms of the “fellow traveller property”) plays a fundamental role. When we move to the study of automatic semigroups, we no longer have this simple formulation. The purpose of this paper is to give a general geometric characterization of automaticity in semigroups.

Details DOI

TCS Journal 2006 Journal Article

Chordless paths through three vertices

Robert Haas
Michael Hoffmann

Consider the following problem, which we call “Chordless path through three vertices” or CP3V, for short: Given a simple undirected graph G = ( V, E ), a positive integer k, and three distinct vertices s, t, and v ∈ V, is there a chordless path of length at most k from s via v to t in G? In a chordless path, no two vertices are connected by an edge that is not in the path. Alternatively, one could say that the subgraph induced by the vertex set of the path in G is the path itself. The problem has arisen in the context of service deployment in communication networks. We resolve the parametric complexity of CP3V by proving it W [ 1 ] -complete with respect to its natural parameter k. Our reduction extends to a number of related problems about chordless paths and cycles. In particular, deciding on the existence of a single directed chordless ( s, t ) -path in a digraph is also W [ 1 ] -complete with respect to the length of the path.

Details DOI

TCS Journal 2006 Journal Article

Coloring octrees

Udo Adamy
Michael Hoffmann
József Solymosi
Miloš Stojaković

An octree is a recursive partition of the unit cube, such that in each step a cube is subdivided into eight smaller cubes. Those cubes that are not further subdivided are the leaves of the octree. We consider the problem of coloring the leaves of an octree using as few colors as possible such that no two of them get the same color if they share a facet. It turns out that the number of colors needed depends on a parameter that we call unbalancedness. Roughly speaking, this parameter measures how much adjacent cubes differ in size. For most values of this parameter we give tight bounds on the minimum number of colors, and extend the results to higher dimensions.

Details DOI