@comment{{This file has been generated by bib2bib 1.92}}
@comment{{Command line: bib2bib -ob peer-reviewed-conf.bib -oc /dev/null -c 'type : "peer-reviewed-conference"' publications.bib}}
  type = {peer-reviewed-conference},
  author = {Javad Azimi and Alan Fern and Xiaoli Z. Fern and Glencora Borradaile and Brent Heeringa},
  booktitle = {Proceedings of the $29^{th}$ International Conference on Machine Learning (ICML)},
  year = 2012,
  title = {\url{./icml2012.pdf}{Batch Active Learning via Coordinated Matching}},
  abstract = {We propose a novel batch active learning method that leverages the availability of high-quality and efficient sequential active-learning policies by approximating their behavior when applied for $k$ steps. Specifically, our algorithm uses Monte-Carlo simulation to estimate the distribution of unlabeled examples selected by a sequential policy over $k$ steps. The algorithm then selects $k$ examples that best matches this distribution, leading to a combinatorial optimization problem that we term ``bounded coordinated matching.'' While we show this problem is NP-hard, we give an efficient greedy solution, which inherits approximation bounds from supermodular minimization theory. Experiments on eight benchmark datasets show that the proposed approach is highly effective.}
  type = {peer-reviewed-conference},
  author = {Matthew Berardi and Brent Heeringa and Justin Malestein and Louis Theran},
  booktitle = {Proceedings of the $23^{rd}$ Annual Canadian Conference on Computational Geometry (CCCG)},
  year = 2011,
  title = {\url{./cccg.pdf}{Rigid Components in Fixed-Latice and Cone Frameworks}},
  abstract = {We study the fundamental algorithmic rigidity problems for generic frameworks
periodic with respect to a fixed lattice or a finite-order rotation in the plane.
For fixed-lattice frameworks we give an $O(n^2)$ algorithm for deciding generic rigidity and
an $O(n^3)$ algorithm for computing rigid components.  If the order of rotation
is part of the input, we give an $O(n^4)$ algorithm for deciding rigidity; in the case
where the rotation's order is $3$, a more specialized algorithm solves all the
fundamental algorithmic rigidity problems in $O(n^2)$ time.}
  type = {peer-reviewed-conference},
  author = {John Byers and \url{}{Brent Heeringa} and Michael Mitzenmacher and Giorgos Zervas},
  booktitle = {Proceedings of the 8th Annual Workshop on Analytic Algorithmics and Combinatorics (ANALCO)},
  title = {\url{./heap.pdf}{Heapable Sequences and Subsequences}},
  year = 2011,
  abstract = { Let us call a sequence of numbers heapable if they can
                  be sequentially inserted to form a binary tree with
                  the heap property, where each insertion subsequent
                  to the first occurs at a previously placed
                  number. In this paper we consider a variety of
                  problems related to heapable sequences and
                  subsequences that do not appear to have been studied
                  previously. Our motivation for introducing these
                  concepts is two-fold. First, such problems
                  correspond to natural extensions of the well-known
                  secretary problem for hiring an organization with a
                  hierarchical structure. Second, from a purely
                  combinatorial perspective, our problems are
                  interesting variations on similar longest increasing
                  subsequence problems, a problem paradigm that has
                  led to many deep mathematical connections.  
                  We provide several basic results. We obtain an
                  efficient algorithm for determining the heapa-
                  bility of a sequence, and also prove that the
                  question of whether a sequence can be arranged in a
                  complete binary heap is NP-hard. Regarding
                  subsequences we show that, with high probability,
                  the longest heapable subsequence of a random
                  permutation of $n$ numbers has length $(1 − o(1))n$, and
                  a subsequence of length $(1 − o(1))n$ can in fact be
                  found online with high probability. We similarly
                  show that for a random permutation a subsequence
                  that yields a perfect heap of size $\alpha n$ for a constant
                  $\alpha$ can be found with high probability. Our work
                  highlights the interesting structure underlying this
                  class of subsequence problems, and we leave many
                  further interesting variations open for future work.
  type = {peer-reviewed-conference},
  author = {Michael Gerbush and \url{}{Brent Heeringa}},
  booktitle = {Proceedings of the 15th International Conference on Implementation and Application of Automata (CIAA)},
  title = {\url{./ciaa.pdf}{Approximating Minimum Reset Sequences}},
  year = 2010,
  abstract = {We consider the problem of finding minimum reset
                  sequences in synchronizing automata.  The well-known
                  Cerny conjecture states that {\em every $n$-state
                  synchronizing automaton has a reset sequence with
                  length at most $(n-1)^{2}$}.  While this conjecture
                  gives an upper bound on the length of every reset
                  sequence, it does not directly address the problem
                  of finding the {\em shortest} reset sequence.  We
                  call this the \mrs (\MRS) problem.  We give an
                  $O(kmn^{k}+n^{4}/k)$-time $\lceil \frac{n-1}{k-1}
                  \rceil$-approximation for the \MRS problem for any
                  $k \geq 2$.  We also show that our analysis is
                  tight.  When $k=2$ our algorithm reduces to
                  Eppstein's algorithm and yields an
                  $(n-1)$-approximation.  When $k=n$ our algorithm is
                  the familiar exponential-time, exact algorithm.  We
                  define a non-trivial class of \MRS which we call
                  \stackcover.  We show that \stackcover naturally
                  generalizes two classic optimization problems: {\sc
                  min} \setcover and \scs.  Both these problems are
                  known to be hard to approximate, although at
                  present, \setcover has a slightly stronger lower
                  bound.  In particular, it is $\mathbf{NP}$-hard to
                  approximate \setcover to within a factor of $c \cdot
                  \log n$ for some $c>0$.  Thus, the \mrs problem is
                  as least as hard to approximate as \setcover.  This
                  improves the previous best lower bound which showed
                  that it was $\mathbf{NP}$-hard to approximate the \MRS on
                  binary alphabets to within any constant factor.  Our
                  result requires an alphabet of arbitrary size.  }
  type = {peer-reviewed-conference},
  author = {Glencora Borradaile and \url{}{Brent Heeringa} and Gordon Wilfong},
  title = {\url{./knapsack.pdf}{The 1-Neighbour Knapsack Problem}},
  notes = {\url{}{arXiv version}},
  year = {2011},
  booktitle = {Proceedings of the 22nd International Workshop on Combinatorial Algorithms (IWOCA)},
  abstract = {We study a constrained version of the knapsack problem in
                  which dependencies between items are given by the
                  adjacencies of a graph.  In the {\em 1-neighbour
                  knapsack problem}, an item can be selected only if
                  at least one of its neighbours is also selected. We
                  give approximation algorithms and hardness results
                  when the nodes have both uniform and arbitrary
                  weight and profit functions, and when the dependency
                  graph is directed and undirected.}
  type = {peer-reviewed-conference},
  author = {Brent Heeringa and
               Marius Catalin Iordan and
               Louis Theran},
  title = {\url{./lltree.pdf}{Searching in Dynamic Tree-Like Partial Orders}},
  booktitle = {Proceedings of the 12th Algorithms and Data Structures
                  Symposium (formerly WADS)},
  year = {2011},
  notes = {\url{}{arXiv version}},
  bibsource = {DBLP,},
  abstract = {We give the first data structure for the problem of
                  maintaining a dynamic set of $n$ elements drawn from
                  a partially ordered universe described by a tree.
                  We define the {\sc Line-Leaf Tree}, a linear-sized
                  data structure that supports the operations: {\em
                  insert; delete; test membership; and predecessor}.
                  The performance of our data structure is within an
                  $O(\log w)$-factor of optimal. Here $w \leq n$ is
                  the width of the partial-order---a natural obstacle
                  in searching a partial order.  }
  type = {peer-reviewed-conference},
  author = {Micah Adler and \url{}{Brent Heeringa}},
  title = {\url{./approx2008.pdf}{Approximating Optimal Binary Decision Trees}},
  booktitle = {Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)},
  year = 2008,
  pages = {1--9},
  abstract = {We give a $(\ln n +1)$-approximation for the decision
  tree (DT) problem.  An instance of DT is a set of $m$ binary tests
  $T=(T_{1}, \ldots, T_{m})$ and a set of $n$ items $X=(X_{1}, \ldots,
  X_{n})$.  The goal is to output a binary tree where each internal
  node is a test, each leaf is an item and the total external path
  length of the tree is minimized.  Total external path length is the
  sum of the depths of all the leaves in the tree.  DT has a long
  history in computer science with applications ranging from medical
  diagnosis to experiment design.  It also generalizes the problem of
  finding optimal average-case search strategies in partially ordered
  sets which includes several alphabetic tree problems.  Our work
  decreases the previous upper bound on the approximation ratio by a
  constant factor.  We provide a new analysis of the greedy algorithm
  that uses a simple accounting scheme to spread the cost of a tree
  among pairs of items split at a particular node.  We conclude by
  showing that our upper bound also holds for the DT problem with
  weighted tests.}
  type = {peer-reviewed-conference},
  author = {Micah Adler and \url{}{Brent Heeringa}},
  title = {\url{./heeringa-tamc.pdf}{Search Space Reductions for Nearest-Neighbor Queries}},
  booktitle = {Proceedings of the 5th Annual Conference on the Theory and Application of Models of Computation (TAMC)},
  year = {2008},
  pages = {554--567},
  abstract = {The vast number of applications featuring multimedia and
  geometric data has made the R-tree a ubiquitous data structure in
  databases.  A popular and fundamental operation on R-trees is
  nearest neighbor search.  While nearest neighbor on R-trees has
  received considerable experimental attention, it has received
  somewhat less theoretical consideration.  We study pruning
  heuristics for nearest neighbor queries on R-trees.  Our primary
  result is the construction of non-trivial families of R-trees where
  $k$-nearest neighbor queries based on pessimistic (i.e. min-max)
  distance estimates provide exponential speedup over queries based
  solely on optimistic (i.e. min) distance estimates.  The exponential
  speedup holds even when $k=1$.  This result provides strong
  theoretical evidence that min-max distance heuristics are an
  essential component to depth-first nearest-neighbor queries.  In
  light of this, we also consider the time-space tradeoffs of
  depth-first versus best-first nearest neighbor queries and construct
  a family of R-trees where best-first search performs exponentially
  better than depth-first search even when depth-first employs min-max
  distance heuristics.}
  type = {peer-reviewed-conference},
  author = {\url{}{Brent Heeringa} and Micah Adler},
  title = {\url{./heeringa-icalp2004.pdf}{Optimal Website Design with the Constrained Subtree Selection Problem}},
  booktitle = {Proceedings of the 31st Annual International Colloquium \
               on Automata, Languages and Programming (ICALP)},
  year = {2004},
  notes = {A complete version of this paper is available as \
\url{./04-09.pdf}{University of Massachusetts Technical Report 04-09}},
  abstract = {We introduce the Constrained Subtree Selection (CSS) problem as a
model for the optimal design of websites.  Given a hierarchy of topics
represented as a DAG G and a probability distribution over the
topics, we select a subtree of the transitive closure of G which
minimizes the expected path cost.  We define path cost as the sum of
the page costs along a path from the root to a leaf.  Page cost,
gamma, is a function of the number of links on a page.  We give a
sufficient condition for gamma which makes CSS NP-Complete.  This
result holds even for the uniform probability distribution.  We give a
polynomial time algorithm for instances of CSS where G does not
constrain the choice of subtrees and gamma favors pages with at
most k links.  We show that CSS remains NP-Hard for constant degree
DAGs and a class of degree costs and give an O(log(k)gamma(d+1))
approximation for any gamma favoring pages with at most k links
and for any G with maximum degree d.  We give complete
characterizations of the optimal trees for the linear degree cost in
unconstrained graphs and uniform probability distributions, and the
logarithmic degree cost in arbitrary DAGs and uniform probability
  type = {peer-reviewed-conference},
  author = {Paul R. Cohen and \url{}{Brent Heeringa} and Niall Adams},
  title = {\url{icdm2002.pdf}{An Unsupervised Algorithm for 
           Segmenting Categorical 
           Time Series into Episodes}},
  booktitle = {Proceedings of the 2002 IEEE International 
               Conference on Data Mining (ICDM 2002)},
  pages = {99--106},
  year = {2002},
  notes = {An earlier version is available in the \
           Working Notes of the 2002 ESF Exploratory \
           Workshop on Pattern Detection and Discovery in Data Mining},
  abstract = {This paper describes an unsupervised algorithm for \ segmenting
              categorical time series into episodes.  \ The
              Voting-Experts algorithm first collects statistics \
              about the frequency and boundary entropy of ngrams, then
              \ passes a window over the series and has two \ ``expert
              methods'' decide where in the window boundaries \ should
              be drawn.  The algorithm successfully segments \ text
              into words in four languages.  The algorithm also \
              segments time series of robot sensor data into
              subsequences\ that represent episodes in the life of the
              robot. We claim that {\sc Voting-Experts} finds
              meaningful episodes \ in categorical time series because
              it exploits two statistical \ characteristics of
              meaningful episodes.}
  type = {peer-reviewed-conference},
  author = {Tim Oates and \url{}{Brent Heeringa}},
  title = {\url{./oates-heeringa-icgi2002.pdf}{Estimating Grammar Parameters using Bounded Memory}},
  booktitle = {Proceedings of the Sixth International \
               Colloquium on Grammatical Inference (ICGI)},
  pages = {185--198},
  editor = {P. Adriaans and H. Fernau and M. van Zaanen},
  date = {January 2002},
  year = {2002},
  publisher = {Springer-Verlag Heidelberg},
  abstract = {Estimating the parameters of stochastic context-free grammars 
(SCFGs) from data is an important, well-studied problem.  Almost without
exception, existing approaches make repeated passes over the training
data.  The memory requirements of such algorithms are ill-suited for
embedded agents exposed to large amounts of training data over long
periods of time.  We present a novel algorithm, called HOLA, for
estimating the parameters of SCFGs that computes summary statistics
for each string as it is observed and then discards the string.  The
memory used by HOLA is bounded by the size of the grammar, not by the
amount of training data.  Empirical results show that HOLA performs
as well as the Inside-Outside algorithm on a variety of standard
problems, despite the fact that it has access to much less
  type = {peer-reviewed-conference},
  author = {Gary W. King and \url{}{Brent Heeringa} and Joe Catalano \
            and David L. Westbrook and Paul Cohen},
  title = {\url{./wsc2002.pdf}{Models of Defeat}},
  booktitle = {Proceedings of the 2002 Winter Simulation Conference},
  pages = {928--934},
  year = {2002},
  notes = {An earlier version appears in the Proceedings of \
           the Second International Conference on Knowledge \
           Systems for Coalition Operations. Pages 85-90},
  abstract = {Coalition operations are increasingly effects-based, 
which means they apply force only as necessary to achieve political
and psychological effects. Capture the Flag is a war gaming environment
that includes intelligent, autonomous adversaries.  Our planner
previously focused on two goals: occupying objectives and
attrition. But attrition is a means to the defeat of one's enemies,
not an end in itself. For Capture the Flag to plan for defeat, it
needs a model of defeat. We model the ``capacity for conflict'' as a
leaky bucket: when a unit's bucket is full, it has no more capacity
for conflict and it capitulates. Flow into and out of the bucket is
modulated by several factors including attrition and heroism. The
model is inherently dynamical, so it exhibits the time-dependent behaviors one
observes in real conflicts; for example, identical
attacks will have different effects on capitulation as a function of their
  type = {peer-reviewed-conference},
  author = {Marc Atkin and Gary W. King and David Westbrook and \url{}{Brent Heeringa} and Andrew Hannon and Paul Cohen},
  title = {\url{./agents2001.pdf}{Hierarchical Agent Control: 
           A Framework for Defining Agent Behavior}},
  booktitle = {Proceedings of the Fifth International \
               Conference on Autonomous Agents},
  pages = {452--432},
  year = {2001},
  abstract = {The Hierarchical Agent Control Architecture (HAC) is a general toolkit for specifying an agent's behavior.  HAC supports action abstraction, resource management, sensor integration, and is well suited to controlling large numbers of agents in dynamic environments.  It relies on three hierarchies:  action, sensor, and context.  The action hierarchy controls the agent's behavior.  It is organized around tasks to be accomplished, not the agents themselves.  This facilitates the integration of multi-agent actions and planning into the architecture.  The sensor hierarchy provides a principled means for structuring the complexity of reading and transforming sensor information.  Each level of the hierarchy integrates the data coming in from the environment into conceptual chunks appropriate for us by actions at this level.  Actions and sensors are written using the same formalism.  The context hierarchy is a hierarchy of goals.  In addition to their primary goals, most actions are simultaneously trying to achieve a set of implicit assumptions.  These assumptions are made explicit through the context hierarchy and provide the context under which the agent operates.  We have developed a planner, GRASP, implemented within HAC, which is capable of resolving multiple goals in real time.

HAC was intended to have wide applicability.  It has been used to control agents in commercial computer games and physical robots.  Our primary application domain is a simulator of land-based military-engagements called ``Capture the Flag.''  HAC's simulation substrate models physics at an abstract level.  HAC supports any domain in which behaviors can be reduced to a small set of primitive effectors such as MOVE and APPLY-FORCE.   At this time defining agent behavior requires lisp programming skills; we are moving towards more graphical programming languages.}
  type = {peer-reviewed-conference},
  author = {Brent Heeringa and Paul R. Cohen},
  title = {\url{./wsc2000.pdf}{An Underlying Model for Defeat Mechanisms}},
  booktitle = {Proceedings of 2000 Winter Simulation Conference (WSC 2000)},
  pages = {933--939},
  year = {2002},
  notes = {An earlier version appears in Working Notes of the \
           2000 AAAI Fall Symposium on Simulating Human Agents.\  
           Pages 39--45.},
  abstract = {Defeat mechanisms are strategies for achieving victory over an
opponent.  Although defeat mechanisms often rely on influencing the
opponent psychologically and emotionally, most simulations of warfare
do not model these ``soft'' factors, they model only victory by
attrition.  To create more accurate, adaptable, and believable
systems, we must be able to model a variety of defeat mechanisms.  We
propose a model where parameters and attributes that affect emotional
and physical fatigue are combined to produce an overall measure of
fatigue called effective fatigue.  Effective fatigue, along with an
agent's state, is combined by a defeat model to produce probabilities
of surrender.  We create warfare scenarios involving catastrophe and
surprise, and then examine the model's behavior under these scenarios.
We conclude with a discussion of how the model is related to our own
Capture the Flag war gaming system.}