8 citations · 14 across the 9 of their papers we have counts for
9 papers
Fairest Neighbors: Tradeoffs Between Metric Queries
Magnus Lie Hetland, Halvard Hummel
Metric search commonly involves finding objects similar to a given sample object. We explore a generalization, where the desired result is a fair tradeoff between multiple query ob…
Maximin Shares Under Cardinality Constraints
Halvard Hummel, Magnus Lie Hetland
We study the problem of fair allocation of a set of indivisible items among agents with additive valuations, under cardinality constraints. In this setting, the items are partition…
Fair Allocation of Conflicting Items
Halvard Hummel, Magnus Lie Hetland
We study fair allocation of indivisible items, where the items are furnished with a set of conflicts, and agents are not permitted to receive conflicting items. This kind of constr…
Metrics and Ambits and Sprawls, Oh My
Magnus Lie Hetland
A follow-up to my previous tutorial on metric indexing, this paper walks through the classic structures, placing them all in the context of the recently proposed "sprawl of ambits"…
Optimal Metric Search Is Equivalent to the Minimum Dominating Set Problem
Magnus Lie Hetland
In metric search, worst-case analysis is of little value, as the search invariably degenerates to a linear scan for ill-behaved data. Consequently, much effort has been expended on…
Comparison-Based Indexing From First Principles
Magnus Lie Hetland
Basic assumptions about comparison-based indexing are laid down and a general design space is derived from these. An index structure spanning this design space (the sprawl) is desc…
A Real-Time Spatial Index for In-Vehicle Units
Magnus Lie Hetland, Ola Martin Lykkja
We construct a spatial indexing solution for the highly constrained environment of an in-vehicle unit in a distributed vehicle tolling scheme based on satellite navigation (GNSS).…
Simulating Ability: Representing Skills in Games
Magnus Lie Hetland
Throughout the history of games, representing the abilities of the various agents acting on behalf of the players has been a central concern. With increasingly sophisticated games…
Ptolemaic Indexing
Magnus Lie Hetland
This paper discusses a new family of bounds for use in similarity search, related to those used in metric indexing, but based on Ptolemy's inequality, rather than the metric axioms…