Search

In this paper, we study the Orienteering Aisle-graphs Single-access Problem(OASP), a variant of the orienteering problem for a robot moving in a so-calledsingle-access aisle-graph, i.e., a graph consisting of a set of rows that canbe accessed from one side only. Aisle-graphs model, among others, vineyards orwarehouses. Each aisle-graph vertex is associated with a reward that a robotobtains when visits the vertex itself. As the robot's energy is limited, only asubset of vertices can be visited with a fully charged battery. The objectiveis to maximize the total reward collected by the robot with a battery charge.We first propose an optimal algorithm that solves OASP in O(m^2 n^2) time foraisle-graphs with a single access consisting of m rows, each with n vertices.With the goal of designing faster solutions, we propose four greedy sub-optimalalgorithms that run in at most O(mn (m+n)) time. For two of them, we guaranteean approximation ratio of 1/2(1-1/e), where e is the base of the naturallogarithm, on the total reward by exploiting the well-known submodularityproperty. Experimentally, we show that these algorithms collect more than 80%of the optimal reward.

The shortest path problem is formulated as an l1-regularized regression problem, known as lasso. Based on this formulation, a connection is established between Dijkstra's shortest path algorithm and the least angle regression (LARS) for the lasso problem. Specifically, the solution path of the lasso problem, obtained by varying the regularization parameter from infinity to zero (the regularization path), corresponds to shortest path trees that appear in the bi-directional Dijkstra algorithm.

The shortest path problem is formulated as an l1-regularized regression problem, known as lasso. Based on this formulation, a connection is established between Dijkstra's shortest path algorithm and the least angle regression (LARS) for the lasso problem. Specifically, the solution path of the lasso problem, obtained by varying the regularization parameter from infinity to zero (the regularization path), corresponds to shortest path trees that appear in the bi-directional Dijkstra algorithm.

Data-structure dynamization is a general approach for making static datastructures dynamic. It is used extensively in geometric settings and in theguise of so-called merge (or compaction) policies in big-data databases such asGoogle Bigtable and LevelDB (our focus). Previous theoretical work is based onworst-case analyses for uniform inputs -- insertions of one item at a time andconstant read rate. In practice, merge policies must not only handle batchinsertions and varying read/write ratios, they can take advantage of suchnon-uniformity to reduce cost on a per-input basis. To model this, we initiate the study of data-structure dynamization throughthe lens of competitive analysis, via two new online set-cover problems. Foreach, the input is a sequence of disjoint sets of weighted items. The sets arerevealed one at a time. The algorithm must respond to each with a set coverthat covers all items revealed so far. It obtains the cover incrementally fromthe previous cover by adding one or more sets and optionally removing existingsets. For each new set the algorithm incurs build cost equal to the weight ofthe items in the set. In the first problem the objective is to minimize totalbuild cost plus total query cost, where the algorithm incurs a query cost ateach time $t$ equal to the current cover size. In the second problem, theobjective is to minimize the build cost while keeping the query cost fromexceeding $k$ (a given parameter) at any time. We give deterministic onlinealgorithms for both variants, with competitive ratios of $\Theta(\log^* n)$ and$k$, respectively. The latter ratio is optimal for the second variant.

If we pick n random points uniformly in [0, 1] d and connect each point to its c d log n-nearest neighbors, where d ≥ 2 is the dimension and c d is a constant depending on the dimension, then it is well known that the graph is connected with high probability. We prove that it suffices to connect every point to c d,1 log log n points chosen randomly among its c d,2 log n-nearest neighbors to ensure a giant component of size n - o(n) with high probability. This construction yields a much sparser random graph with ~ n log log n instead of ~ n log n edges that has comparable connectivity properties. This result has nontrivial implications for problems in data science where an affinity matrix is constructed: instead of connecting each point to its k nearest neighbors, one can often pick k' ≪ k random points out of the k nearest neighbors and only connect to those without sacrificing quality of results. This approach can simplify and accelerate computation; we illustrate this with experimental results in spectral clustering of large-scale datasets.

The growing deployment of Internet of Things (IoT) systems aims to ease thedaily life of end-users by providing several value-added services. However, IoTsystems may capture and store sensitive, personal data about individuals in thecloud, thereby jeopardizing user-privacy. Emerging legislation, such asCalifornia's CalOPPA and GDPR in Europe, support strong privacy laws to protectan individual's data in the cloud. One such law relates to strict enforcementof data retention policies. This paper proposes a framework, entitled IoTExpunge that allows sensor data providers to store the data in cloud platformsthat will ensure enforcement of retention policies. Additionally, the cloudprovider produces verifiable proofs of its adherence to the retention policies.Experimental results on a real-world smart building testbed show that IoTExpunge imposes minimal overheads to the user to verify the data against dataretention policies.

The rapid growth of big spatial data urged the research community to develop several big spatial data systems. Regardless of their architecture, one of the fundamental requirements of all these systems is to spatially partition the data efficiently across machines. The core challenges of big spatial partitioning are building high spatial quality partitions while simultaneously taking advantages of distributed processing models by providing load balanced partitions. Previous works on big spatial partitioning are to reuse existing index search trees as-is, e.g., the R-tree family, STR, Kd-tree, and Quad-tree, by building a temporary tree for a sample of the input and use its leaf nodes as partition boundaries. However, we show in this paper that none of those techniques has addressed the mentioned challenges completely. This paper proposes a novel partitioning method, termed R*-Grove, which can partition very large spatial datasets into high quality partitions with excellent load balance and block utilization. This appealing property allows R*-Grove to outperform existing techniques in spatial query processing. R*-Grove can be easily integrated into any big data platforms such as Apache Spark or Apache Hadoop. Our experiments show that R*-Grove outperforms the existing partitioning techniques for big spatial data systems. With all the proposed work publicly available as open source, we envision that R*-Grove will be adopted by the community to better serve big spatial data research.

The maximization of submodular functions is an NP-Hard problem for certainsubclasses of functions, for which a simple greedy algorithm has been shown toguarantee a solution whose quality is within 1/2 of the optimal. When thisalgorithm is implemented in a distributed way, agents sequentially makedecisions based on the decisions of all previous agents. This work explores howlimited access to the decisions of previous agents affects the quality of thesolution of the greedy algorithm. Specifically, we provide tight upper andlower bounds on how well the algorithm performs, as a function of theinformation available to each agent. Intuitively, the results show thatperformance roughly degrades proportionally to the size of the largest group ofagents which make decisions independently. Additionally, we consider the casewhere a system designer is given a set of agents and a global limit on theamount of information that can be accessed. Our results show that the bestdesigns partition the agents into equally-sized sets and allow agents to accessthe decisions of all previous agents within the same set.

In this paper, we consider the Constant-cost Orienteering Problem (COP) wherea robot, constrained by a limited travel budget, aims at selecting a path withthe largest reward in an aisle-graph. The aisle-graph consists of a set ofloosely connected rows where the robot can change lane only at either end, butnot in the middle. Even when considering this special type of graphs, theorienteering problem is known to be NP-hard. We optimally solve in polynomialtime two special cases, COP-FR where the robot can only traverse full rows, andCOP-SC where the robot can access the rows only from one side. To solve thegeneral COP, we then apply our special case algorithms as well as a newheuristic that suitably combines them. Despite its light computationalcomplexity and being confined into a very limited class of paths, the optimalsolutions for COP-FR turn out to be competitive even for COP in both real andsynthetic scenarios. Furthermore, our new heuristic for the general caseoutperforms state-of-art algorithms, especially for input with highlyunbalanced rewards.

Huang and Wong [1984] proposed a polynomial-time dynamic-programmingalgorithm for computing optimal generalized binary split trees. We show thattheir algorithm is incorrect. Thus, it remains open whether such trees can becomputed in polynomial time. Spuler [1994] proposed modifying Huang and Wong'salgorithm to obtain an algorithm for a different problem: computing optimaltwo-way-comparison search trees. We show that the dynamic program underlyingSpuler's algorithm is not valid, in that it does not satisfy the necessaryoptimal-substructure property and its proposed recurrence relation isincorrect. It remains unknown whether the algorithm is guaranteed to compute acorrect overall solution.

Motivation The variation graph toolkit (VG) represents genetic variation as a graph. Although each path in the graph is a potential haplotype, most paths are nonbiological, unlikely recombinations of true haplotypes. Results We augment the VG model with haplotype information to identify which paths are more likely to exist in nature. For this purpose, we develop a scalable implementation of the graph extension of the positional Burrows–Wheelertransform (GBWT). We demonstrate the scalability of the new implementation by building a whole-genome index of the 5,008 haplotypes of the 1000 Genomes Project, and an index of all 108,070 TOPMed Freeze 5 chromosome 17 haplotypes. We also develop an algorithm for simplifying variation graphs for k-mer indexing without losing any k-mers in the haplotypes. Availability Our software is available at https://github.com/vgteam/vg , https://github.com/jltsiren/gbwt , and https://github.com/jltsiren/gcsa2 . Contact jouni.siren@iki.fi Supplementary information Supplementary data are available.

We consider problems where the input is a set of points in the plane and aninteger $k$, and the task is to find a subset $S$ of the input points of size$k$ such that $S$ satisfies some property. We focus on properties that dependonly on the order type of the points and are monotone under point removals. Weshow that not all such problems are fixed-parameter tractable parameterized by$k$, by exhibiting a property defined by three forbidden patterns for whichfinding a $k$-point subset with the property is $\mathrm{W}[1]$-complete and(assuming the exponential time hypothesis) cannot be solved in time$n^{o(k/\log k)}$. However, we show that problems of this type arefixed-parameter tractable for all properties that include all collinear pointsets, properties that exclude at least one convex polygon, and propertiesdefined by a single forbidden pattern.

In this paper, we mathematically model the multi-hop Peer-to-Peer (P2P) ride-matching problem as a binary program. We formulate this problem as a many-to-many problem in which a rider can travel my transferring between multiple drivers, and a driver can carry multiple riders. We propose a pre-processing procedure to reduce the size of the problem, and devise a decomposition algorithm to solve the original ride-matching problem to optimality by means of solving multiple smaller problems. We conduct extensive numerical experiments to demonstrate the computational efficiency of the proposed algorithm and show its practical applicability to reasonably-sized dynamic ride-matching contexts. Finally, in the interest of even lower solution times, we propose heuristic solution methods, and investigate the trade-offs between solution time and accuracy.

We study a discrete version of a geometric stable marriage problem originallyproposed in a continuous setting by Hoffman, Holroyd, and Peres, in whichpoints in the plane are stably matched to cluster centers, as prioritized bytheir distances, so that each cluster center is apportioned a set of points ofequal area. We show that, for a discretization of the problem to an $n\times n$grid of pixels with $k$ centers, the problem can be solved in time $O(n^2\log^5 n)$, and we experiment with two slower but more practical algorithms anda hybrid method that switches from one of these algorithms to the other to gaingreater efficiency than either algorithm alone. We also show how to combinegeometric stable matchings with a $k$-means clustering algorithm, so as toprovide a geometric political-districting algorithm that views distance ineconomic terms, and we experiment with weighted versions of stable $k$-means inorder to improve the connectivity of the resulting clusters.

Methods of high-dimensional probability play a central role in applicationsfor statistics, signal processing theoretical computer science and relatedfields. These lectures present a sample of particularly useful tools ofhigh-dimensional probability, focusing on the classical and matrix Bernstein'sinequality and the uniform matrix deviation inequality. We illustrate thesetools with applications for dimension reduction, network analysis, covarianceestimation, matrix completion and sparse signal recovery. The lectures aregeared towards beginning graduate students who have taken a rigorous course inprobability but may not have any experience in data science applications.

The GraphBLAS standard (GraphBlas.org) is being developed to bring the potential of matrix-based graph algorithms to the broadest possible audience. Mathematically, the GraphBLAS defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the mathematics of the GraphBLAS. Graphs represent connections between vertices with edges. Matrices can represent a wide range of graphs using adjacency matrices or incidence matrices. Adjacency matrices are often easier to analyze while incidence matrices are often better for representing data. Fortunately, the two are easily connected by matrix multiplication. A key feature of matrix mathematics is that a very small number of matrix operations can be used to manipulate a very wide range of graphs. This composability of a small number of operations is the foundation of the GraphBLAS. A standard such as the GraphBLAS can only be effective if it has low performance overhead. Performance measurements of prototype GraphBLAS implementations indicate that the overhead is low.

Many algorithms for sequence analysis rely on word matching or word statistics. Often, these approaches can be improved if binary patterns representing match and don't-care positions are used as a filter, such that only those positions of words are considered that correspond to the match positions of the patterns. The performance of these approaches, however, depends on the underlying patterns. Herein, we show that the overlap complexity of a pattern set that was introduced by Ilie and Ilie is closely related to the variance of the number of matches between two evolutionarily related sequences with respect to this pattern set. We propose a modified hill-climbing algorithm to optimize pattern sets for database searching, read mapping and alignment-free sequence comparison of nucleic-acid sequences; our implementation of this algorithm is called rasbhari. Depending on the application at hand, rasbhari can either minimize the overlap complexity of pattern sets, maximize their sensitivity in database searching or minimize the variance of the number of pattern-based matches in alignment-free sequence comparison. We show that, for database searching, rasbhari generates pattern sets with slightly higher sensitivity than existing approaches. In our Spaced Words approach to alignment-free sequence comparison, pattern sets calculated with rasbhari led to more accurate estimates of phylogenetic distances than the randomly generated pattern sets that we previously used. Finally, we used rasbhari to generate patterns for short read classification with CLARK-S. Here too, the sensitivity of the results could be improved, compared to the default patterns of the program. We integrated rasbhari into Spaced Words; the source code of rasbhari is freely available at http://rasbhari.gobics.de/.

We study the performance of linear solvers for graph Laplacians based on thecombinatorial cycle adjustment methodology proposed by[Kelner-Orecchia-Sidford-Zhu STOC-13]. The approach finds a dual flow solutionto this linear system through a sequence of flow adjustments along cycles. Westudy both data structure oriented and recursive methods for handling theseadjustments. The primary difficulty faced by this approach, updating and querying longcycles, motivated us to study an important special case: instances where allcycles are formed by fundamental cycles on a length $n$ path. Our methodsdemonstrate significant speedups over previous implementations, and arecompetitive with standard numerical routines.

The problem of exactly summing n floating-point numbers is a fundamentalproblem that has many applications in large-scale simulations and computationalgeometry. Unfortunately, due to the round-off error in standard floating-pointoperations, this problem becomes very challenging. Moreover, all existingsolutions rely on sequential algorithms which cannot scale to the huge datasetsthat need to be processed. In this paper, we provide several efficient parallel algorithms for summing nfloating point numbers, so as to produce a faithfully rounded floating-pointrepresentation of the sum. We present algorithms in PRAM, external-memory, andMapReduce models, and we also provide an experimental analysis of our MapReducealgorithms, due to their simplicity and practical efficiency.

The GraphBLAS standard (GraphBlas.org) is being developed to bring the potential of matrix-based graph algorithms to the broadest possible audience. Mathematically, the GraphBLAS defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the mathematics of the GraphBLAS. Graphs represent connections between vertices with edges. Matrices can represent a wide range of graphs using adjacency matrices or incidence matrices. Adjacency matrices are often easier to analyze while incidence matrices are often better for representing data. Fortunately, the two are easily connected by matrix multiplication. A key feature of matrix mathematics is that a very small number of matrix operations can be used to manipulate a very wide range of graphs. This composability of a small number of operations is the foundation of the GraphBLAS. A standard such as the GraphBLAS can only be effective if it has low performance overhead. Performance measurements of prototype GraphBLAS implementations indicate that the overhead is low.

The Joint Replenishment Problem ($${\hbox {JRP}}$$JRP) is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers’ waiting costs. We study the approximability of $${\hbox {JRP-D}}$$JRP-D, the version of $${\hbox {JRP}}$$JRP with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of $$1.207$$1.207, a stronger, computer-assisted lower bound of $$1.245$$1.245, as well as an upper bound and approximation ratio of $$1.574$$1.574. The best previous upper bound and approximation ratio was $$1.667$$1.667; no lower bound was previously published. For the special case when all demand periods are of equal length, we give an upper bound of $$1.5$$1.5, a lower bound of $$1.2$$1.2, and show APX-hardness.

An improved version of a recently developed stochastic cluster dynamics (SCD) method (Marian and Bulatov, 2012) [6] is introduced as an alternative to rate theory (RT) methods for solving coupled ordinary differential equation (ODE) systems for irradiation damage simulations. SCD circumvents by design the curse of dimensionality of the variable space that renders traditional ODE-based RT approaches inefficient when handling complex defect population comprised of multiple (more than two) defect species. Several improvements introduced here enable efficient and accurate simulations of irradiated materials up to realistic (high) damage doses characteristic of next-generation nuclear systems. The first improvement is a procedure for efficiently updating the defect reaction-network and event selection in the context of a dynamically expanding reaction-network. Next is a novel implementation of the τ-leaping method that speeds up SCD simulations by advancing the state of the reaction network in large time increments when appropriate. Lastly, a volume rescaling procedure is introduced to control the computational complexity of the expanding reaction-network through occasional reductions of the defect population while maintaining accurate statistics. The enhanced SCD method is then applied to model defect cluster accumulation in iron thin films subjected to triple ion-beam (Fe3+, He+ and H+) irradiations, for which standard RT or spatially-resolved kinetic Monte Carlo simulations are prohibitively expensive.

We present a graph processing benchmark suite with the goal of helping tostandardize graph processing evaluations. Fewer differences between graphprocessing evaluations will make it easier to compare different researchefforts and quantify improvements. The benchmark not only specifies graphkernels, input graphs, and evaluation methodologies, but it also providesoptimized baseline implementations. These baseline implementations arerepresentative of state-of-the-art performance, and thus new contributionsshould outperform them to demonstrate an improvement. The input graphs are sized appropriately for shared memory platforms, but anyimplementation on any platform that conforms to the benchmark's specificationscould be compared. This benchmark suite can be used in a variety of settings.Graph framework developers can demonstrate the generality of their programmingmodel by implementing all of the benchmark's kernels and delivering competitiveperformance on all of the benchmark's graphs. Algorithm designers can use theinput graphs and the baseline implementations to demonstrate theircontribution. Platform designers and performance analysts can use the suite asa workload representative of graph processing.

An improved version of a recently developed stochastic cluster dynamics (SCD) method (Marian and Bulatov, 2012) [6] is introduced as an alternative to rate theory (RT) methods for solving coupled ordinary differential equation (ODE) systems for irradiation damage simulations. SCD circumvents by design the curse of dimensionality of the variable space that renders traditional ODE-based RT approaches inefficient when handling complex defect population comprised of multiple (more than two) defect species. Several improvements introduced here enable efficient and accurate simulations of irradiated materials up to realistic (high) damage doses characteristic of next-generation nuclear systems. The first improvement is a procedure for efficiently updating the defect reaction-network and event selection in the context of a dynamically expanding reaction-network. Next is a novel implementation of the τ-leaping method that speeds up SCD simulations by advancing the state of the reaction network in large time increments when appropriate. Lastly, a volume rescaling procedure is introduced to control the computational complexity of the expanding reaction-network through occasional reductions of the defect population while maintaining accurate statistics. The enhanced SCD method is then applied to model defect cluster accumulation in iron thin films subjected to triple ion-beam (Fe3+, He+ and H+) irradiations, for which standard RT or spatially-resolved kinetic Monte Carlo simulations are prohibitively expensive.

We give an approximation algorithm for fractional packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm (with high probability) computes feasible primal and dual solutions whose costs are within a factor of 1+ε of opt (the optimal cost) in time O((r+c)log(n)/ε2+n).

We describe the first nearly linear-time approximation algorithms forexplicitly given mixed packing/covering linear programs, and for (non-metric)fractional facility location. We also describe the first parallel algorithmsrequiring only near-linear total work and finishing in polylog time. Thealgorithms compute $(1+\epsilon)$-approximate solutions in time (and work)$O^*(N/\epsilon^2)$, where $N$ is the number of non-zeros in the constraintmatrix. For facility location, $N$ is the number of eligible client/facilitypairs.

We consider generalizations of Schuetzenberger's promotion operator on theset L of linear extensions of a finite poset of size n. This gives rise to astrongly connected graph on L. By assigning weights to the edges of the graphin two different ways, we study two Markov chains, both of which areirreducible. The stationary state of one gives rise to the uniformdistribution, whereas the weights of the stationary state of the other has anice product formula. This generalizes results by Hendricks on the Tsetlinlibrary, which corresponds to the case when the poset is the anti-chain andhence L=S_n is the full symmetric group. We also provide explicit eigenvaluesof the transition matrix in general when the poset is a rooted forest. This isshown by proving that the associated monoid is R-trivial and then usingSteinberg's extension of Brown's theory for Markov chains on left regular bandsto R-trivial monoids.

We give an exact algorithm for the 0-1 Integer Linear Programming problemwith a linear number of constraints that improves over exhaustive search by anexponential factor. Specifically, our algorithm runs in time$2^{(1-\text{poly}(1/c))n}$ where n is the number of variables and cn is thenumber of constraints. The key idea for the algorithm is a reduction to theVector Domination problem and a new algorithm for that subproblem.

Can one choose a good Huffman code on the fly, without knowing the underlying distribution? Online Slot Allocation (OS A) models this and similar problems: There are n slots, each with a known cost. There are n items. Requests for items are drawn i.i.d. from a fixed but hidden probability distribution p. After each request, if the item, i, was not previously requested, then the algorithm (knowing c and the requests so far, but not p) must place the item in some vacant slot ji, at cost Pic(ji). The goal is to minimize the total cost The optimal offline algorithm is trivial: put the most probable item in the cheapest slot, the second most probable item in the second cheapest slot, etc. The optimal online algorithm is First Come First Served (FCFS): put the first requested item in the cheapest slot, the second (distinct) requested item in the second cheapest slot, etc. The optimal competitive ratios for any online algorithm are 1 4- Hn-1 ∼ In n for general costs and 2 for concave costs. For logarithmic costs, the ratio is, asymptotically, 1: FCFS gives cost OPT + O(logOPT). For Huffman coding, FCFS yields an online algo-rithm (one that allocates codewords on demand, without knowing the underlying probability distribution) that guarantees asymptotically optimal cost: At most OPT + 2 log2(l + OPT) + 2. Copyright © 2014 by the Society for Industrial and Applied Mathematics.

Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation algorithm, and a variety of effective polynomial-time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT. Here we show the first such connections: For an LP formulation due to Dantzig, Hoffman, and Hu [Math. Programming, 31 (1985), pp. 1-14], (i) the integrality gap is constant, and (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP. © 2014 Society for Industrial and Applied Mathematics.

Can one choose a good Huffman code on the fly, without knowing the underlying distribution? Online Slot Allocation (OS A) models this and similar problems: There are n slots, each with a known cost. There are n items. Requests for items are drawn i.i.d. from a fixed but hidden probability distribution p. After each request, if the item, i, was not previously requested, then the algorithm (knowing c and the requests so far, but not p) must place the item in some vacant slot ji, at cost Pic(ji). The goal is to minimize the total cost The optimal offline algorithm is trivial: put the most probable item in the cheapest slot, the second most probable item in the second cheapest slot, etc. The optimal online algorithm is First Come First Served (FCFS): put the first requested item in the cheapest slot, the second (distinct) requested item in the second cheapest slot, etc. The optimal competitive ratios for any online algorithm are 1 4- Hn-1 ∼ In n for general costs and 2 for concave costs. For logarithmic costs, the ratio is, asymptotically, 1: FCFS gives cost OPT + O(logOPT). For Huffman coding, FCFS yields an online algo-rithm (one that allocates codewords on demand, without knowing the underlying probability distribution) that guarantees asymptotically optimal cost: At most OPT + 2 log2(l + OPT) + 2. Copyright © 2014 by the Society for Industrial and Applied Mathematics.

Given a CNF formula and a weight for each assignment of values to variables, two natural problems are weighted model counting and distribution-aware sampling of satisfying assignments. Both problems have a wide variety of important applications. Due to the inherent complexity of the exact versions of the problems, interest has focused on solving them approximately. Prior work in this area scaled only to small problems in practice, or failed to provide strong theoretical guarantees, or employed a computationally-expensive most-probable-explanation (MPE) queries that assumes prior knowledge of a factored representation of the weight distribution. We identify a novel parameter, tilt, which is the ratio of the maximum weight of satisfying assignment to minimum weight of satisfying assignment and present a novel approach that works with a black-box oracle for weights of assignments and requires only an NP-oracle (in practice, a SAT-solver) to solve both the counting and sampling problems when the tilt is small. Our approach provides strong theoretical guarantees, and scales to problems involving several thousand variables. We also show that the assumption of small tilt can be significantly relaxed while improving computational efficiency if a factored representation of the weights is known.

Given a CNF formula and a weight for each assignment of values to variables, two natural problems are weighted model counting and distribution-aware sampling of satisfying assignments. Both problems have a wide variety of important applications. Due to the inherent complexity of the exact versions of the problems, interest has focused on solving them approximately. Prior work in this area scaled only to small problems in practice, or failed to provide strong theoretical guarantees, or employed a computationally-expensive most-probable-explanation (MPE) queries that assumes prior knowledge of a factored representation of the weight distribution. We identify a novel parameter, tilt, which is the ratio of the maximum weight of satisfying assignment to minimum weight of satisfying assignment and present a novel approach that works with a black-box oracle for weights of assignments and requires only an NP-oracle (in practice, a SAT-solver) to solve both the counting and sampling problems when the tilt is small. Our approach provides strong theoretical guarantees, and scales to problems involving several thousand variables. We also show that the assumption of small tilt can be significantly relaxed while improving computational efficiency if a factored representation of the weights is known.

A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon. © 2012 Elsevier B.V. All rights reserved.

A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon. © 2012 Elsevier B.V. All rights reserved.

The movement of data (communication) between levels of a memory hierarchy, orbetween parallel processors on a network, can greatly dominate the cost ofcomputation, so algorithms that minimize communication are of interest.Motivated by this, attainable lower bounds for the amount of communicationrequired by algorithms were established by several groups for a variety ofalgorithms, including matrix computations. Prior work ofBallard-Demmel-Holtz-Schwartz relied on a geometric inequality of Loomis andWhitney for this purpose. In this paper the general theory of discretemultilinear Holder-Brascamp-Lieb (HBL) inequalities is used to establishcommunication lower bounds for a much wider class of algorithms. In some cases,algorithms are presented which attain these lower bounds. Several contributions are made to the theory of HBL inequalities proper. Theoptimal constant in such an inequality for torsion-free Abelian groups is shownto equal one whenever it is finite. Bennett-Carbery-Christ-Tao hadcharacterized the tuples of exponents for which such an inequality is valid asthe convex polyhedron defined by a certain finite list of inequalities. Theproblem of constructing an algorithm to decide whether a given inequality is onthis list, is shown to be equivalent to Hilbert's Tenth Problem over therationals, which remains open. Nonetheless, an algorithm which computes thepolyhedron itself is constructed.

We introduce a new concept of a subgraph class called a superbubble for analyzing assembly graphs, and propose an efficient algorithm for detecting it. Most assembly algorithms utilize assembly graphs like the de Bruijn graph or the overlap graph constructed from reads. From these graphs, many assembly algorithms first detect simple local graph structures (motifs), such as tips and bubbles, mainly to find sequencing errors. These motifs are easy to detect, but they are sometimes too simple to deal with more complex errors. The superbubble is an extension of the bubble, which is also important for analyzing assembly graphs. Though superbubbles are much more complex than ordinary bubbles, we show that they can be efficiently enumerated. We propose an average-case linear time algorithm (i.e., O(n+m) for a graph with n vertices and m edges) for graphs with a reasonable model, though the worst-case time complexity of our algorithm is quadratic (i.e., O(n(n+m))). Moreover, the algorithm is practically very fast: Our experiments show that our algorithm runs in reasonable time with a single CPU core even against a very large graph of a whole human genome.

Kloks, Kratsch, and Spinrad showed how treewidth and minimum-fill, NP-hard combinatorial optimization problems related to minimal triangulations, are broken into subproblems by block subgraphs defined by minimal separators. These ideas were expanded on by Bouchitt\'e and Todinca, who used potential maximal cliques to solve these problems using a dynamic programming approach in time polynomial in the number of minimal separators of a graph. It is known that solutions to the perfect phylogeny problem, maximum compatibility problem, and unique perfect phylogeny problem are characterized by minimal triangulations of the partition intersection graph. In this paper, we show that techniques similar to those proposed by Bouchitt\'e and Todinca can be used to solve the perfect phylogeny problem with missing data, the two- state maximum compatibility problem with missing data, and the unique perfect phylogeny problem with missing data in time polynomial in the number of minimal separators of the partition intersection graph.

We give a short proof that any comparison-based n^(1-epsilon)-approximationalgorithm for the 1-dimensional Traveling Salesman Problem (TSP) requiresOmega(n log n) comparisons.

In streamed graph drawing, a planar graph, G, is given incrementally as a data stream and a straight-line drawing of G must be updated after each new edge is released. To preserve the mental map, changes to the drawing should be minimized after each update, and Binucci et al. show that exponential area is necessary for a number of streamed graph drawings for trees if edges are not allowed to move at all. We show that a number of streamed graph drawings can, in fact, be done with polynomial area, including planar streamed graph drawings of trees, tree-maps, and outerplanar graphs, if we allow for a small number of coordinate movements after each update. Our algorithms involve an interesting connection to a classic algorithmic problem - the file maintenance problem - and we also give new algorithms for this problem in a framework where bulk memory moves are allowed. © 2013 Springer International Publishing Switzerland.

We study a three-dimensional analogue to the well-known graph visualization approach known as arc diagrams. We provide several algorithms that achieve good angular resolution for 3D arc diagrams, even for cases when the arcs must project to a given 2D straight-line drawing of the input graph. Our methods make use of various graph coloring algorithms, including an algorithm for a new coloring problem, which we call localized edge coloring. © 2013 Springer International Publishing Switzerland.

In streamed graph drawing, a planar graph, G, is given incrementally as a data stream and a straight-line drawing of G must be updated after each new edge is released. To preserve the mental map, changes to the drawing should be minimized after each update, and Binucci et al. show that exponential area is necessary for a number of streamed graph drawings for trees if edges are not allowed to move at all. We show that a number of streamed graph drawings can, in fact, be done with polynomial area, including planar streamed graph drawings of trees, tree-maps, and outerplanar graphs, if we allow for a small number of coordinate movements after each update. Our algorithms involve an interesting connection to a classic algorithmic problem - the file maintenance problem - and we also give new algorithms for this problem in a framework where bulk memory moves are allowed. © 2013 Springer International Publishing Switzerland.

We study a three-dimensional analogue to the well-known graph visualization approach known as arc diagrams. We provide several algorithms that achieve good angular resolution for 3D arc diagrams, even for cases when the arcs must project to a given 2D straight-line drawing of the input graph. Our methods make use of various graph coloring algorithms, including an algorithm for a new coloring problem, which we call localized edge coloring. © 2013 Springer International Publishing Switzerland.

Given a satisfiable 3-SAT formula, how hard is it to find an assignment tothe variables that has Hamming distance at most n/2 to a satisfying assignment?More generally, consider any polynomial-time verifier for any NP-completelanguage. A d(n)-Hamming-approximation algorithm for the verifier is one that,given any member x of the language, outputs in polynomial time a string a withHamming distance at most d(n) to some witness w, where (x,w) is accepted by theverifier. Previous results have shown that, if P != NP, then every NP-completelanguage has a verifier for which there is no(n/2-n^(2/3+d))-Hamming-approximation algorithm, for various constants d > 0. Our main result is that, if P != NP, then every paddable NP-complete languagehas a verifier that admits no (n/2+O(sqrt(n log n)))-Hamming-approximationalgorithm. That is, one cannot get even half the bits right. We also considernatural verifiers for various well-known NP-complete problems. They do haven/2-Hamming-approximation algorithms, but, if P != NP, have no(n/2-n^epsilon)-Hamming-approximation algorithms for any constant epsilon > 0. We show similar results for randomized algorithms.

We discuss the method recently proposed by S. Chubanov for the linear feasibility problem. We present new, concise proofs and interpretations of some of his results. We then show how our proofs can be used to find strongly polynomial time algorithms for special classes of linear feasibility problems. Under certain conditions, these results provide new proofs of classical results obtained by Tardos, and Vavasis and Ye.

We present a convex hull algorithm that is accelerated on commodity graphicshardware. We analyze and identify the hurdles of writing a recursive divide andconquer algorithm on the GPU and divise a framework for representing this classof problems. Our framework transforms the recursive splitting step into apermutation step that is well-suited for graphics hardware. Our convex hullalgorithm of choice is Quickhull. Our parallel Quickhull implementation (forboth 2D and 3D cases) achieves an order of magnitude speedup over standardcomputational geometry libraries.

We give a polynomial-time approximation scheme for the generalization of Huffman coding in which codeword letters have nonuniform costs (as in Morse code, where the dash is twice as long as the dot). The algorithm computes a (1 +?)-approximate solution in time O(n+f(?) log3 n), where n is the input size. © 2012 Society for Industrial and Applied Mathematics.

In this paper, we revisit the design of synchronizationprimitives---specifically barriers, mutexes, and semaphores---and how theyapply to the GPU. Previous implementations are insufficient due to thediscrepancies in hardware and programming model of the GPU and CPU. We createnew implementations in CUDA and analyze the performance of spinning on the GPU,as well as a method of sleeping on the GPU, by running a set of memory-systembenchmarks on two of the most common GPUs in use, the Tesla- and Fermi-classGPUs from NVIDIA. From our results we define higher-level principles that arevalid for generic many-core processors, the most important of which is to limitthe number of atomic accesses required for a synchronization operation becauseatomic accesses are slower than regular memory accesses. We use the results ofthe benchmarks to critique existing synchronization algorithms and guide ournew implementations, and then define an abstraction of GPUs to classify any GPUbased on the behavior of the memory system. We use this abstraction to createsuitable implementations of the primitives specifically targeting the GPU, andanalyze the performance of these algorithms on Tesla and Fermi. We then predictperformance on future GPUs based on characteristics of the abstraction. We alsoexamine the roles of spin waiting and sleep waiting in each primitive and howtheir performance varies based on the machine abstraction, then give a set ofguidelines for when each strategy is useful based on the characteristics of theGPU and expected contention.

This paper gives poly-logarithmic-round, distributed δ-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio δ is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with δ = 2). Via duality, the paper also gives poly-logarithmic-round, distributed δ-approximation algorithms for Fractional Packing linear programs (where δ is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where δ is the maximum size of any of the hyperedges; for graphs δ = 2). The paper also gives parallel (RNC) 2-approximation algorithms for CMIP with two variables per constraint and Weighted Vertex Cover. The algorithms are randomized. All of the approximation ratios exactly match those of comparable centralized algorithms. © 2011 Springer-Verlag.

We consider the problem of choosing Euclidean points to maximize the sum oftheir weighted pairwise distances, when each point is constrained to a ballcentered at the origin. We derive a dual minimization problem and show strongduality holds (i.e., the resulting upper bound is tight) when some locallyoptimal configuration of points is affinely independent. We sketch a polynomialtime algorithm for finding a near-optimal set of points.