@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}}

@inproceedings{azimi-etal:icml2012, 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.} }

@inproceedings{berardi-et-al:cccg2011, 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.} }

@inproceedings{byers-etal:analco2011, type = {peer-reviewed-conference}, author = {John Byers and \url{http://www.cs.williams.edu/~heeringa}{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. } }

@inproceedings{gerbush-heeringa:ciaa2010, type = {peer-reviewed-conference}, author = {Michael Gerbush and \url{http://www.cs.williams.edu/~heeringa}{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. } }

@inproceedings{borradaile-et-al:arxiv2009, type = {peer-reviewed-conference}, author = {Glencora Borradaile and \url{http://www.cs.williams.edu/~heeringa}{Brent Heeringa} and Gordon Wilfong}, title = {\url{./knapsack.pdf}{The 1-Neighbour Knapsack Problem}}, notes = {\url{http://arxiv.org/abs/0910.0777}{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.} }

@inproceedings{heeringa-et-al:wads2011, 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{http://arxiv.org/abs/1010.1316}{arXiv version}}, bibsource = {DBLP, http://dblp.uni-trier.de}, 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. } }

@inproceedings{adler-heeringa:dt, type = {peer-reviewed-conference}, author = {Micah Adler and \url{http://www.cs.williams.edu/~heeringa}{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.} }

@inproceedings{adler-heeringa:tamc2008, type = {peer-reviewed-conference}, author = {Micah Adler and \url{http://www.cs.williams.edu/~heeringa}{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.} }

@inproceedings{heeringa-adler:icalp2004, type = {peer-reviewed-conference}, author = {\url{http://www.cs.williams.edu/~heeringa}{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 distributions.} }

@inproceedings{cohen-heeringa-adams:icdm2002, type = {peer-reviewed-conference}, author = {Paul R. Cohen and \url{http://www.cs.williams.edu/~heeringa}{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.} }

@inproceedings{oates-heeringa:icgi2002, type = {peer-reviewed-conference}, author = {Tim Oates and \url{http://www.cs.williams.edu/~heeringa}{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 information.} }

@inproceedings{king-et-al:wsc2002, type = {peer-reviewed-conference}, author = {Gary W. King and \url{http://www.cs.williams.edu/~heeringa}{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 timing.} }

@inproceedings{atkin-et-al:aa2001, type = {peer-reviewed-conference}, author = {Marc Atkin and Gary W. King and David Westbrook and \url{http://www.cs.williams.edu/~heeringa}{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.} }

@inproceedings{heeringa-cohen:wsc2000, 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.} }