Abstract It is natural to generalize the online $$k$$ k -Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family $${\mathcal {S}}\subseteq 2^{[k]}$$ S ⊆ 2 [ k ] of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family $${\mathcal {S}}$$ S : If all request sets are allowed ( $${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ S = 2 [ k ] \ { ∅ } ), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ( $${\mathcal {S}}=\{[k]\}$$ S = { [ k ] } ). As a function of $$|{\mathcal {S}}|$$ | S | and k, the optimal deterministic ratio is polynomial: at most $$O(k^2|{\mathcal {S}}|)$$ O ( k 2 | S | ) and at least $$\Omega (\sqrt{|{\mathcal {S}}|})$$ Ω ( | S | ) . For any laminar family $${\mathcal {S}}$$ S of height h, the optimal ratios are O(hk) (deterministic) and $$O(h^2\log k)$$ O ( h 2 log k ) (randomized). The special case of laminar $${\mathcal {S}}$$ S that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $$\Theta (k)$$ Θ ( k ) . Offline All-or-One Paging is

Given a weighted, ordered query set \(Q\) and a partition of \(Q\) into classes, we study the problem of computing a minimum-cost decision tree that, given any query \(q\in Q\) , uses equality tests and less-than tests to determine \(q\) 's class. Such a tree can be faster and smaller than a conventional search tree and smaller than a lookup table (both of which must identify \(q\) , not just its class). We give the first polynomial-time algorithm for the problem. The algorithm extends naturally to the setting where each query has multiple allowed classes.

It is natural to generalize the online $k$-Server problem by allowing each request to specify not only a point $p$, but also a subset $S$ of servers that may serve it. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page $p$, but also a subset $S$ of cache slots, and is satisfied by having a copy of $p$ in some slot in $S$. We call this problem Slot-Heterogenous Paging. We parameterize the problem by specifying a family $\mathcal S \subseteq 2^{[k]}$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size $k$ and family $\mathcal S$: - If all request sets are allowed ($\mathcal S=2^{[k]}\setminus\{\emptyset\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard \Paging ($\mathcal S=\{[k]\}$). - As a function of $|\mathcal S|$ and $k$, the optimal deterministic ratio is polynomial: at most $O(k^2|\mathcal S|)$ and at least $Ω(\sqrt{|\mathcal S|})$. - For any laminar family $\mathcal S$ of height $h$, the optimal ratios are $O(hk)$ (deterministic) and $O(h^2\log k)$ (randomized). - The special case of laminar $\mathcal S$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $Θ(k)$. Offline All-or-One Paging is NP-hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $\mathcal P of pages, and is satisfied by fetching any page from $\mathcal P into the cache. The optimal ratios for the latter problem (with laminar family of height $h$) are at most $hk$ (deterministic) and $h\,H_k$ (randomized).

Abstract Huang and Wong (Acta Inform 21(1):113–123, 1984) proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can be computed in polynomial time. Spuler (Optimal search trees using two-way key comparisons, PhD thesis, 1994) proposed modifying Huang and Wong’s algorithm to obtain an algorithm for a different problem: computing optimal two-way comparison search trees. We show that the dynamic program underlying Spuler’s algorithm is not valid, in that it does not satisfy the necessary optimal-substructure property and its proposed recurrence relation is incorrect. It remains unknown whether the algorithm is guaranteed to compute a correct overall solution.

We present a simple O(n 4 ) -time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees.

Data-structure dynamization is a general approach for making static data structures dynamic. It is used extensively in geometric settings and in the guise of so-called merge (or compaction) policies in big-data databases such as LevelDB and Google Bigtable. Previous theoretical work is based on worst-case analyses for uniform inputs—insertions of one item at a time and non-varying read rate. In practice, merge policies must not only handle batch insertions and varying read/write ratios, they can take advantage of such non-uniformity to reduce cost on a per-input basis. To model this, we initiate the study of data-structure dynamization through the lens of competitive analysis via two new online set-cover problems. For each, the input is a sequence of disjoint sets of weighted items. The sets are revealed one at a time. The algorithm must respond to each with a set cover that covers all items revealed so far. It obtains the cover incrementally from the previous cover by adding one or more sets and optionally removing existing sets. For each new set the algorithm incurs build cost equal to the weight of the items in the set. In the first problem the objective is to minimize total build cost plus total query cost , where the algorithm incurs a query cost at each time \(t\) equal to the current cover size. In the second problem, the objective is to minimize the build cost while keeping the query cost from exceeding \(k\) (a given parameter) at any time. We give deterministic online algorithms for both variants, with competitive ratios of \(\Theta(\log^{*}n)\) and \(k\) , respectively. The latter ratio is optimal for the second variant.

Abstract Modern NoSQL database systems use log-structured merge (LSM) storage architectures to support high write throughput. LSM architectures aggregate writes in a mutable MemTable (stored in memory), which is regularly flushed to disk, creating a new immutable file called an SSTable. Some of the SSTables are chosen to be periodically merged—replaced with a single SSTable containing their union. A mergepolicy (a.k.a. compaction policy) specifies when to do merges and which SSTables to combine. A bounded depth merge policy is one that guarantees that the number of SSTables never exceeds a given parameter k, typically in the range 3–10. Bounded depth policies are useful in applications where low read latency is crucial, but they and their underlying combinatorics are not yet well understood. This paper compares several bounded depth policies, including representative policies from industrial NoSQL databases and two new ones based on recent theoretical modeling, as well as the standard Tiered policy and Leveled policy. The results validate the proposed theoretical model and show that, compared to the existing policies, the newly proposed policies can have substantially lower write amplification with comparable read amplification.

Modern NoSQL databases use log-structured merge (LSM) storage architectures to support high write throughput. LSM architectures aggregate writes in a mutable MemTabte (stored in memory), which is regularly flushed to disk, creating a new immutable file called an SSTable. Periodically, some of the SSTables are chosen to be merged - replaced with a single SSTable containing their union. A merge policy (a.k.a. compaction policy) specifies when to do merges and which SSTables to combine. A bounded depth merge policy is one that guarantees that the number of SSTables never exceeds a given parameter k, typically in the range 3-10. Bounded-depth policies are useful in applications where low read latency is crucial, but they and their underlying combinatorics are not yet well understood. This paper compares several bounded-depth policies, including representative policies from industrial NoSQL databases and two new ones based on recent theoretical modeling. The results validate the proposed theoretical model and show that, compared to the existing policies, the newly proposed policies can have substantially lower write amplification.

No abstract available.

Minimization of labeling effort for person re-identification in camera networks is an important problem as most of the existing popular methods are supervised and they require large amount of manual annotations, acquiring which is a tedious job. In this work, we focus on this labeling effort minimization problem and approach it as a subset selection task where the objective is to select an optimal subset of image-pairs for labeling without compromising performance. Towards this goal, our proposed scheme first represents any camera network (with k number of cameras) as an edge weighted complete k-partite graph where each vertex denotes a person and similarity scores between persons are used as edge-weights. Then in the second stage, our algorithm selects an optimal subset of pairs by solving a triangle free subgraph maximization problem on the k-partite graph. This sub-graph weight maximization problem is NP-hard (at least for k = 4) which means for large datasets the optimization problem becomes intractable. In order to make our framework scalable, we propose two polynomial time approximately-optimal algorithms. The first algorithm is a 1/2-approximation algorithm which runs in linear time in the number of edges. The second algorithm is a greedy algorithm with sub-quadratic (in number of edges) time-complexity. Experiments on three state-of-the-art datasets depict that the proposed approach requires on an average only 8-15% manually labeled pairs in order to achieve the performance when all the pairs are manually annotated.

We consider the problem of political redistricting: given the locations of people in a geographical area (e.g. a US state), the goal is to decompose the area into subareas, called districts, so that the populations of the districts are as close as possible and the districts are "compact" and "contiguous," to use the terms referred to in most US state constitutions and/or US Supreme Court rulings.

In this Web 2.0 era, there is an ever increasing number of product or service reviews, which must be summarized to help consumers effortlessly make informed decisions. Previous work on reviews summarization has simplified the problem by assuming that features (e.g., "display") are independent of each other and that the opinion for each feature in a review is Boolean: positive or negative. However, in reality features may be interrelated – e.g., "display" and "display color" – and the sentiment takes values in a continuous range – e.g., somewhat vs very positive. We present a novel review summarization framework that advances the state-of-the-art by leveraging a domain hierarchy of concepts to handle the semantic overlap among the features, and by accounting for different sentiment levels. We show that the problem is NP-hard and present bounded approximate algorithms to compute the most representative set of sentences, based on a principled opinion coverage framework. We experimentally evaluate the quality of the summaries using both intuitive coverage measure and a user study.

We give a lower bound on the iteration complexity of a natural class of Lagrangian-relaxation algorithms for approximately solving packing/covering linear programs. We show that, given an input with $m$ random 0/1-constraints on $n$ variables, with high probability, any such algorithm requires $\Omega(\rho \log(m)/\epsilon^2)$ iterations to compute a $(1+\epsilon)$-approximate solution, where $\rho$ is the width of the input. The bound is tight for a range of the parameters $(m,n,\rho,\epsilon)$. The algorithms in the class include Dantzig--Wolfe decomposition, Benders' decomposition, Lagrangian relaxation as developed by Held and Karp for lower-bounding TSP, and many others (e.g., those by Plotkin, Shmoys, and Tardos and Grigoriadis and Khachiyan). To prove the bound, we use a discrepancy argument to show an analogous lower bound on the support size of $(1+\epsilon)$-approximate mixed strategies for random two-player zero-sum 0/1-matrix games.

Can one choose a good Huffman code on the fly, without knowing the underlying distribution? Online Slot Allocation (OSA) 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 pi c(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 + Hn–1 ∼ lnn 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 algorithm (one that allocates codewords on demand, without knowing the underlying probability distribution) that guarantees asymptotically optimal cost: at most opt + 2 log2(1 + opt) + 2.

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.

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 et al. (1985): (i) the integrality gap is bounded by a constant; (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP.

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+\epsilon)$-approximate solution in time $O(n+f(\epsilon)\log^3n)$, where $n$ is the input size.

Time series shapelets are small, local patterns in a time series that are highly predictive of a class and are thus very useful features for building classifiers and for certain visualization and summarization tasks. While shapelets were introduced only recently, they have already seen significant adoption and extension in the community. Despite their immense potential as a data mining primitive, there are two important limitations of shapelets. First, their expressiveness is limited to simple binary presence/absence questions. Second, even though shapelets are computed offline, the time taken to compute them is significant. In this work, we address the latter problem by introducing a novel algorithm that finds shapelets in less time than current methods by an order of magnitude. Our algorithm is based on intelligent caching and reuse of computations, and the admissible pruning of the search space. Because our algorithm is so fast, it creates an opportunity to consider more expressive shapelet queries. In particular, we show for the first time an augmented shapelet representation that distinguishes the data based on conjunctions or disjunctions of shapelets. We call our novel representation Logical-Shapelets. We demonstrate the efficiency of our approach on the classic benchmark datasets used for these problems, and show several case studies where logical shapelets significantly outperform the original shapelet representation and other time series classification techniques. We demonstrate the utility of our ideas in domains as diverse as gesture recognition, robotics, and biometrics.

The paper presents distributed and parallel δ-approximation algorithms for covering problems, where δ is the maximum number of variables on which any constraint depends (for example, δ = 2 for VERTEX COVER).

With fully directional communications, nodes must track the positions of their neighbors so that communication with these neighbors is feasible when needed. Tracking process introduces an overhead, which increases with the number of discovered neighbors. The overhead can be reduced if nodes maintain only a subset of their neighbors; however, this may increase the length of paths between node pairs in the network. In this work, we study the tradeoffs between node degree and path stretch. We first design a topology control algorithm to optimize this tradeoff. Assuming that nodes communicate with their directional neighbors using circular directional transmissions, we model the original graph as a unit disk graph (UDG). Given a UDG G, our algorithm finds a sparse subgraph G' with a maximum degree of 6, and connecting each node pair u,v by a path of length hopsG(u, v) = O(hopsG(u, v) + log Delta), where Delta is the maximum degree in G, hopsG'(u, v) denotes length of the shortest path between u, v in G. We show that this result is near-optimal. Based on the insights gained from this design, we next construct a simpler, more practical scheme that integrates fully-directional neighbor discovery and maintenance with topology control strategy. We simulate both algorithms and compare their performances.

We give an approximation algorithm for 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 I +epsiv of OPT l+ epsiv of OPT (the optimal cost) in time O(n + (r +c) log(n) / epsiv2). For dense problems (with r,c = O(-radicn)) the time is Omega (n log(n) / epsiv2)-linear even as epsiv rarr 0. In comparison, previous Lagrangian-relaxation algorithms generally take at least Omega(n log(n)/epsiv2) time, while (for small epsiv) the Simplex algorithm typically takes at least Omega(n min(r, c)) time.

Dimension attributes in data warehouses are typically hierarchical, and a variety of OLAP applications (such as point-of-sales analysis and decision support) call for summarizing the measure attributes in fact tables along the hierarchies of these attributes. For example, the total sales at different stores can be summarized hierarchically by geographic location (e.g., state/city/zip_code/store), by time (e.g., year/month/day/hour), or by product category (e.g., clothing/outerwear/jackets/brand). Existing OLAP tools help to summarize and navigate the data at different levels of aggregation (e.g., jackets sold in each state during December 2006) via drill-down and roll-up operators. OLAP tools are also used to characterize changes in these hierarchical summaries over time (e.g., the sales in December 2006 compared to sales in December 2005 over different locations) to detect anomalies and characterize trends. When the number of changes identified is large (e.g., the total sales at many locations differed significantly from their expectations), one seeks explanations. In this paper, we are interested in parsimonious explanations of changes in measure attributes aggregated along an associated dimension attribute hierarchy. We propose a natural model of explanation that makes effective use of the dimension hierarchy and describes changes at the leaf nodes of the hierarchy (e.g., individual stores in the location hierarchy) as a composition of "node weights" along each node's root-to-leaf path in the dimension hierarchy; each node weight constitutes an explanatory term. For example, sales in California stores were three times expected sales; sales in San Jose stores were higher by a factor of two (six times expected sales), whereas sales in Los Angeles stores were lower than the statewide increase by a factor of 1.5 (two times expected sales).

Dimension attributes in data warehouses are typically hierarchical (e.g., geographic locations in sales data, URLs in Web traffic logs). OLAP tools are used to summarize the measure attributes (e.g., total sales) along a dimension hierarchy, and to characterize changes (e.g., trends and anomalies) in a hierarchical summary over time. When thenumber of changes identified is large (e.g., total sales in many stores differed from their expected values), a parsimonious explanation of the most significant changes is desirable. In this paper, we propose a natural model of parsimonious explanation, as a composition of node weights along the root-to-leaf paths in a dimension hierarchy, which permits changes to be aggregated with maximal generalization along the dimension hierarchy. We formalize this model of explaining changes in hierarchical summaries and investigate the problem of identifying optimally parsimonious explanations on arbitrary rooted one dimensional tree hierarchies. We show that such explanations can be computed efficiently in time essentially proportional to the number of leaves and the depth of the hierarchy. Further, our method can produce parsimonious explanations from the output of any statistical model that provides predictions and confidence intervals, making it widely applicable. Our experiments use real data sets to demonstrate the utility and robustness of our proposed model for explaining significant changes, as well as its superior parsimony compared to alternatives.

With directional antennas, it is extremely important that a node maintains information with regards to the positions of its neighbors. This would allow the node to "track" the neighbors as they move; otherwise, a node will have to resort to either omnidirectional or circular directional transmissions (or receptions) fairly often. This can be overhead intense and can reduce spatial reuse. Maintaining directional information with regards to a large number of neighbors can itself be expensive; therefore it is important to limit a node's degree. We propose a topology control scheme (Di-ATC) that works with fully directional communications and offers a low degree bound while preserving network connectivity. The key idea is to execute Di-ATC on the discovered neighbors to select and maintain connectivity with only a subset of these neighbors. The members of this subset are those with high angular separations. We perform extensive simulations and demonstrate that our scheme effectively limits node degree while at the same time, preserves network connectivity and achieves low path stretch

Our objective in this paper is to design topology control algorithms such that (i) nodes have low degree and (ii) paths in the network have few hops. Low node degree is desirable in networks equipped with smart antennas and to reduce access contention. Short paths are desirable for minimizing communication delays and for better robustness to channel impairments and to mobility. Given any arbitrary unit-disc graph G representing all feasible links, our algorithms find a sparse subgraph G' having a maximum node degree of six and, for each pair of vertices u, v, having hopsG'(u, v) = O(hopsG(u,v) + logDelta), where Delta is the maximum node degree in G and hopsG(u, v) denotes the shortest path length from u to v in G. This result is near-optimal: (i) there is a connected UDG G in which no connected subgraph has degree less than five, and (ii) for any graph G, any bounded-degree subgraph G' must have hopsG'(u, v) = Omega(hopsG(u, v) + logDelta) for some u, v. Our distributed algorithm scales, preserves link symmetry, does not need node synchronization, and requires only O(n) messages. We perform extensive simulations that quantify the performance of our algorithm in realistic scenarios

Congestion control in the current Internet is accomplished mainly by TCP/IP. To understand the macroscopic network behavior that results from TCP/IP and similar end-to-end protocols, one main analytic technique is to show that the the protocol maximizes some global objective function of the network traffic. We analyze a particular end-to-end MIMD (multiplicative-increase, multiplicative-decrease) protocol. We show that if all users of the network use the protocol, and all connections last for at least logarithmically many rounds, then the total weighted throughput (value of all packets received) is near the maximum possible. Our analysis includes round-trip-times, and (in contrast to most previous analyses) gives explicit convergence rates, allows connections to start and stop, and allows capacities to change.

(MATH) In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding must be prefix free (no codeword is a prefix of any other) and should minimize the weighted average codeword size Σw freq w, |c(w)|. The problem has a well-known polynomial-time algorithm due to Huffman [15].Here we consider the generalization in which the letters of the encoding alphabet may have non-uniform lengths. The goal is to minimize the weighted average codeword length Σw freq (w) cost(c(w)), where cost s is the sum of the (possibly non-uniform) lengths of the letters in s. Despite much previous work, the problem is not known to be NP-hard, nor was it previously known to have a polynomial-time approximation algorithm. Here we describe a polynomial-time approximation scheme (PTAS) for the problem.

In this paper we study approximation algorithms for solving a general covering integer program. An n-vector x of nonnegative integers is sought, which minimizes c/sup T//spl middot/x, subject to Ax/spl ges/b, x/spl les/d. The entries of A, b, c are nonnegative. Let m be the number of rows of A. Covering problems have been heavily studied in combinatorial optimization. We focus on the effect of the multiplicity constraints, x/spl les/d, on approximately. Two longstanding open questions remain for this general formulation with upper bounds on the variables. (i) The integrality gap of the standard LP relaxation is arbitrarily large. Existing approximation algorithms that achieve the well-known O(log m)-approximation with respect to the LP value do so at the expense of violating the upper bounds on the variables by the same O(log m) multiplicative factor. What is the smallest possible violation of the upper bounds that still achieves cost within O(log m) of the standard LP optimum? (ii) The best known approximation ratio for the problem has been O(log(max/sub j//spl Sigma//sub i/A/sub ij/)) since 1982. This bound can be as bad as polynomial in the input size. Is an O(log m)-approximation, like the one known for the special case of Set Cover, possible? We settle these two open questions. To answer the first question we give an algorithm based on the relatively simple new idea of randomly rounding variables to smaller-than-integer units. To settle the second question we give a reduction from approximating the problem while respecting multiplicity constraints to approximating the problem with a bounded violation of the multiplicity constraints.

We describe sequential and parallel algorithms that approximately solve linear programs with no negative coefficients (aka mixed packing and covering problems). For explicitly given problems, our fastest sequential algorithm returns a solution satisfying all constraints within a 1/spl plusmn//spl epsi/ factor in O(mdlog(m)//spl epsi//sup 2/) time, where m is the number of constraints and d is the maximum number of constraints any variable appears in. Our parallel algorithm runs in time polylogarithmic in the input size times /spl epsi//sup -4/ and uses a total number of operations comparable to the sequential algorithm. The main contribution is that the algorithms solve mixed packing and covering problems (in contrast to pure packing or pure covering problems, which have only "/spl les/" or only "/spl ges/" inequalities, but not both) and run in time independent of the so-called width of the problem.

The data broadcast problem is to find a schedule for broadcasting a given set of messages over multiple channels. The goal is to minimize the cost of the broadcast plus the expected response time to clients who periodically and probabilistically tune in to wait for particular messages. The problem models disseminating data to clients in asymmetric communication environments, where there is a much larger capacity from the information source to the clients than in the reverse direction. Examples include satellites, cable TV, internet broadcast, and mobile phones. Such environments favor the ``push-based'' model where the server broadcasts (pushes) its information on the communication medium and multiple clients simultaneously retrieve the specific information of individual interest. This paper presents the first polynomial-time approximation scheme (PTAS) for data broadcast with O(1) channels and when each message has arbitrary probability, unit length and bounded cost. The best previous polynomial-time approximation algorithm for this case has a performance ratio of 9/8.

Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The multiway cut problem is to find a minimum-cost multiway cut. This problem is Max-SNP hard. Recently Calinescu, Karloff, and Rabani (STOC'98) gave a novel geometric relaxation of the problem and a rounding scheme that produced a (3=2 1=k)-approximation algorithm. In this paper, we study their geometric relaxation. In particular, we study the worst-case ratio between the value of the relaxation and the value of the minimum multicut (the so-called integrality gap of the relaxation). For k = 3, we show the integrality gap is 12=11, giving tight upper and lower bounds. That is, we exhibit a graph with integrality gap 12=11 and give an algorithm that finds a cut of value 12=11 times the relaxation value. This is the best possible performance guarantee for any algorithm based purely on the value of the relaxation and improves on Calinescu et al.'s factor of 7/6. We also improve the upper bounds for all larger values of k. For k = 4; 5, our best upper bounds are based on computer constructed and analyzed rounding schemes, while for k > 6 we give an algorithm with performance ratio 1:3438 k . Our results were discovered with the help of computational experiments that we also describe here. MIT Laboratory for Computer Science, Cambridge, MA 02138. [email protected]. Research supported by NSF contract CCR9624239, an Alfred P. Sloane Foundation Fellowship, and a David and Lucille Packard Foundation Fellowship. y Brown University . [email protected]. Research supported by NSF Grant CCR-9700146. z Dartmouth College. [email protected]. Research supported by NSF Caree...

Pattern-matching based document compression systems rely on finding a small set of patterns that can be used to represent all of the ink in the document. Finding an optimal set of patterns is NP-hard; previous compression schemes have resorted to heuristics. We extend the cross-entropy approach, used previously for measuring pattern similarity, to this problem. Using this approach we reduce the problem to the fixed-cost k-median problem, for which we present a new algorithm with a good provable performance guarantee. We test our new algorithm in place of the previous heuristics (First Fit, with and without generalized Lloyd's (k-means) postprocessing steps). The new algorithm generates a better codebook, resulting in an overall improvement in compression performance of almost 17%.

It is well known that every 2-edge-connected graph can be oriented so that the resulting digraph is strongly connected. Here we study the problem of orienting a connected graph with cut edges in order to maximize the number of ordered vertex pairs (x, y) such that there is a directed path from x to y. After transforming this problem, we prove a key theorem about the transformed problem that allows us to obtain a quadratic algorithm for the original orientation problem. We also consider how to orient graphs to minimize the number of ordered vertex pairs joined by a directed path. After showing this problem is equivalent to the comparability graph completion problem, we show both problems are NP-hard, and even NP-hard to approximate to within a factor of 1 + ε, for some ε > 0.

Given a directed graph G = (V, E), a natural problem is to choose a minimum number of the edges in E such that, for any two vertices u and v, if there is a path from u to v in E, then there is a path from u to v among the chosen edges. We show that in graphs having no directed cycle with more than three edges, this problem is equivalent to Maximum Bipartite Matching. This leads to a small improvement in the performance guarantee of the previous best approximation algorithm for the general problem.

We consider the following variant of Huffman coding in which the costs of the letters, rather than the probabilities of the words, are nonuniform “Given an alphabet of r letters of nonuniform length, find a minimum-average-length prefix free set of n codewords over the alphabet”; equivalently, “Find an optimal r-ary search tree with n leaves, where each leaf is accessed with equal probability but the cost to descend from a parent to its ith child depends on i.” We show new structural properties of such codes, leading to an $O(n\log ^2 r)$ time algorithm for finding them, This new algorithm is simpler and faster than the best previously known $O(nr\min \{ \log n,r\} )$ time algorithm, due to Perl Garey, and Even [J. Assoc. Comput. Mach., 22 (1975), pp. 202–214].

Given n points in the plane, the degree-K spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low-weight degree-K spanning trees for $K > 2$. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree 3 whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of degree 4 whose weight is at most 1.25 times the weight of a minimum spanning tree. These results solve open problems posed by Papadimitriou and Vazirani. Moreover, if a minimum spanning tree is given as part of the input, the trees can be computed in $O(n)$ time. The results are generalized to points in higher dimensions. It is shown that for any $d \geqslant 3$, an arbitrary collection of points in $\Re ^d $ contains a spanning tree of degree 3 whose weight is at most ${5 / 3}$ times the weight of a minimum spanning tree. This is the first paper that achieves factors better than 2 for these problems.

The minimum equivalent graph (MEG) problem is as follows: given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes. This problem is NP-hard; this paper gives an approximation algorithm achieving a performance guarantee of about 1.64 in polynomial time. The algorithm achieves a performance guarantee of 1.75 in the time required for transitive closure. The heart of the MEG problem is the minimum strongly connected spanning subgraph (SCSS) problem—the MEG problem restricted to strongly connected digraphs. For the minimum SCSS problem, the paper gives a practical, nearly linear-time implementation achieving a performance guarantee of 1.75. The algorithm and its analysis are based on the simple idea of contracting long cycles. The analysis applies directly to 2-Exchange, a general “local improvement” algorithm, showing that its performance guarantee is 1.75.

. Given n points in the plane, the degree-K spanning tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low-weight degree-K spanning trees for K ? 2. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree three whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of degree four whose weight is at most 1.25 times the weight of a minimum spanning tree. These results solve open problems posed by Papadimitriou and Vazirani. Moreover, if a minimum spanning tree is given as part of the input, the trees can be computed in O(n) time. The results are generalized to points in higher dimensions. It is shown that for any d 3, an arbitrary collection of points in ! d contains a spanning tree of degree three, whose weight is at most 5/3 times the weight of a minimum spanning tre...

Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. This paper gives an elementary proof that each player has a near-optimal mixed strategy that chooses uniformly at random from a multiset of pure strategies of size logarithmic in the number of pure strategies available to the opponent. For exponentially large games, for which even representing an optimal mixed strategy can require exponential space, it follows that there are near-optimal, linear-size strategies. These strategies are easy to play and serve as small witnesses to the approximate value of the game. As a corollary, it follows that every language has small ``hard'' multisets of inputs certifying that small circuits can't decide the language. For example, if SAT does not have polynomial-size circuits, then, for each n and c, there is a set of n^(O(c)) Boolean formulae of size n such that no circuit of size n^c (or algorithm running in time n^c) classifies more than two-thirds of the formulae succesfully.

Abstract We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum‐balance algorithm to obtain a faster minimum‐balance algorithm. For a graph with n vertices and m edges, our parametric shortest path algorithm and our minimum‐balance algorithm both run in O(nm + n2 log n) time, improved from O(nm log n) for the parametric shortest path algorithm of Karp and Orlin and O(n2m) for the minimum‐balance algorithm of Schneider and Schneider. An important application of the parametric shortest path algorithm is in finding a minimum mean cycle. Experiments on random graphs suggest that the expected time for finding a minimum mean cycle with our algorithm is O(n log n + m).