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