journal.bib

@comment{{This file has been generated by bib2bib 1.92}}
@comment{{Command line: bib2bib -ob journal.bib -oc /dev/null -c 'type : "journal"' publications.bib}}
@article{borradaile-et-al:jda2012,
  title = {The knapsack problem with neighbour constraints},
  type = {journal},
  journal = {Journal of Discrete Algorithms},
  volume = {16},
  number = {0},
  pages = {224 - 235},
  year = {2012},
  notes = {An \url{./knapsack.pdf}{earlier version} of this paper appeared at IWOCA 2011.},
  issn = {1570-8667},
  doi = {10.1016/j.jda.2012.04.011},
  url = {http://www.sciencedirect.com/science/article/pii/S1570866712000809},
  author = {Glencora Borradaile and Brent Heeringa and Gordon Wilfong},
  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 1-neighbour knapsack
                  problem, an item can be selected only if at least
                  one of its neighbours is also selected. In the
                  all-neighbours knapsack problem, an item can be
                  selected only if all its neighbours are also
                  selected.  We give approximation algorithms and
                  hardness results when the vertices have both uniform
                  and arbitrary weight and profit functions, and when
                  the dependency graph is directed and undirected.}
}
@article{adler-heeringa:algorithmica2011,
  type = {journal},
  author = {Micah Adler and Brent Heeringa},
  affiliation = {Fiksu, Inc., 101 Arch Street, Suite 304, Boston, MA 02110, USA},
  title = {\url{http://link.springer.com/article/10.1007\%2Fs00453-011-9510-9}{Approximating Optimal Binary Decision Trees}},
  journal = {Algorithmica},
  publisher = {Springer New York},
  issn = {0178-4617},
  keyword = {Computer Science},
  pages = {1112-1121},
  url = {http://dx.doi.org/10.1007/s00453-011-9510-9},
  notes = {An \url{./approx2008.pdf}{earlier version} of this paper appeared at APPROX 2008.},
  year = {April 2012},
  volume = {62},
  issue = {3-4},
  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.}
}
@journal{cohenetal:ida2007,
  type = {journal},
  author = {Paul R. Cohen and Niall Adams and \url{http://www.cs.williams.edu/~heeringa}{Brent Heeringa}},
  title = {\url{./voting-experts.pdf}{Voting Experts:  An Unsupervised Algorithm for Segmenting Sequences}},
  journal = {International Journal on Intelligent Data Analysis},
  volume = 11,
  pages = {607--625},
  issue = 6,
  year = 2007,
  abstract = {We describe a statistical signature of chunks and an
algorithm for finding chunks.  While there is no formal definition of
chunks, they may be reliably identified as configurations with low
internal entropy or unpredictability and high entropy at their boundaries. 
We show that the log frequency of a chunk is a measure of its
internal entropy.  The Voting-Experts exploits the signature of chunks
to find word boundaries in text from four languages and episode
boundaries in the activities of a mobile robot}
}