@conference {17564, title = {Approximation algorithms for throughput maximization in wireless networks with delay constraints}, booktitle = {2011 Proceedings IEEE INFOCOM}, year = {2011}, month = {2011/04/10/15}, pages = {1116 - 1124}, publisher = {IEEE}, organization = {IEEE}, abstract = {We study the problem of throughput maximization in multi-hop wireless networks with end-to-end delay constraints for each session. This problem has received much attention starting with the work of Grossglauser and Tse (2002), and it has been shown that there is a significant tradeoff between the end-to-end delays and the total achievable rate. We develop algorithms to compute such tradeoffs with provable performance guarantees for arbitrary instances, with general interference models. Given a target delay-bound Δ(c) for each session c, our algorithm gives a stable flow vector with a total throughput within a factor of O (logΔm/log log Δm) of the maximum, so that the per-session (end-to-end) delay is O ((logΔm/log log Δm Δ(c))2), where Δm = maxc{Δ(c)}; note that these bounds depend only on the delays, and not on the network size, and this is the first such result, to our knowledge.}, keywords = {Approximation algorithms, Approximation methods, approximation theory, Delay, delay constraints, delays, general interference model, Interference, multihop wireless networks, optimisation, Optimized production technology, radio networks, radiofrequency interference, target delay bound, Throughput, throughput maximization, Wireless networks}, isbn = {978-1-4244-9919-9}, doi = {10.1109/INFCOM.2011.5934887}, author = {Guanhong Pei and Anil Kumar,V. S and Parthasarathy,S. and Srinivasan, Aravind} } @conference {13383, title = {Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems}, booktitle = {2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS)}, year = {2011}, month = {2011/10/22/25}, pages = {797 - 806}, publisher = {IEEE}, organization = {IEEE}, abstract = {We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input dataset are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, and minimum weight matchings over probabilistic graphs, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of risk averse or risk-prone behaviors, and instead we consider a more general objective which is to maximize the expected utility of the solution for some given utility function, rather than the expected weight (expected weight becomes a special case). We show that we can obtain a polynomial time approximation algorithm with additive error ϵ for any ϵ >; 0, if there is a pseudopolynomial time algorithm for the exact version of the problem (This is true for the problems mentioned above) and the maximum value of the utility function is bounded by a constant. Our result generalizes several prior results on stochastic shortest path, stochastic spanning tree, and stochastic knapsack. Our algorithm for utility maximization makes use of the separability of exponential utility and a technique to decompose a general utility function into exponential utility functions, which may be useful in other stochastic optimization problems.}, keywords = {Approximation algorithms, Approximation methods, combinatorial problems, Fourier series, knapsack problems, optimisation, OPTIMIZATION, polynomial approximation, polynomial time approximation algorithm, Polynomials, Random variables, stochastic combinatorial optimization, stochastic knapsack, stochastic shortest path, stochastic spanning tree, vectors}, isbn = {978-1-4577-1843-4}, doi = {10.1109/FOCS.2011.33}, author = {Li,Jian and Deshpande, Amol} } @article {15262, title = {Achieving anonymity via clustering}, journal = {ACM Trans. Algorithms}, volume = {6}, year = {2010}, month = {2010/07//}, pages = {49:1{\textendash}49:19 - 49:1{\textendash}49:19}, abstract = {Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of deidentifying records is to remove identifying fields such as social security number, name, etc. However, recent research has shown that a large fraction of the U.S. population can be identified using nonkey attributes (called quasi-identifiers) such as date of birth, gender, and zip code. The k-anonymity model protects privacy via requiring that nonkey attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k-1 other records having exactly the same values for quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a prespecified number of data records. This technique is more general since we have a much larger choice for cluster centers than k-anonymity. In many cases, it lets us release a lot more information without compromising privacy. We also provide constant factor approximation algorithms to come up with such a clustering. This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k. We further observe that a few outlier points can significantly increase the cost of anonymization. Hence, we extend our algorithms to allow an ε fraction of points to remain unclustered, that is, deleted from the anonymized publication. Thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. Our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.}, keywords = {anonymity, Approximation algorithms, clustering, privacy}, isbn = {1549-6325}, doi = {10.1145/1798596.1798602}, url = {http://doi.acm.org/10.1145/1798596.1798602}, author = {Aggarwal,Gagan and Panigrahy,Rina and Feder,Tom{\'a}s and Thomas,Dilys and Kenthapadi,Krishnaram and Khuller, Samir and Zhu,An} } @article {15566, title = {Approximation algorithm for the kinetic robust K-center problem}, journal = {Computational Geometry}, volume = {43}, year = {2010}, month = {2010/08//}, pages = {572 - 586}, abstract = {Two complications frequently arise in real-world applications, motion and the contamination of data by outliers. We consider a fundamental clustering problem, the k-center problem, within the context of these two issues. We are given a finite point set S of size n and an integer k. In the standard k-center problem, the objective is to compute a set of k center points to minimize the maximum distance from any point of S to its closest center, or equivalently, the smallest radius such that S can be covered by k disks of this radius. In the discrete k-center problem the disk centers are drawn from the points of S, and in the absolute k-center problem the disk centers are unrestricted.We generalize this problem in two ways. First, we assume that points are in continuous motion, and the objective is to maintain a solution over time. Second, we assume that some given robustness parameter 0 \< t ⩽ 1 is given, and the objective is to compute the smallest radius such that there exist k disks of this radius that cover at least ⌈ t n ⌉ points of S. We present a kinetic data structure (in the KDS framework) that maintains a ( 3 + ε ) -approximation for the robust discrete k-center problem and a ( 4 + ε ) -approximation for the robust absolute k-center problem, both under the assumption that k is a constant. We also improve on a previous 8-approximation for the non-robust discrete kinetic k-center problem, for arbitrary k, and show that our data structure achieves a ( 4 + ε ) -approximation. All these results hold in any metric space of constant doubling dimension, which includes Euclidean space of constant dimension. }, keywords = {Approximation algorithms, clustering, kinetic data structures, robust statistics}, isbn = {0925-7721}, doi = {10.1016/j.comgeo.2010.01.001}, url = {http://www.sciencedirect.com/science/article/pii/S0925772110000027}, author = {Friedler,Sorelle A. and Mount, Dave} } @conference {13391, title = {On Computing Compression Trees for Data Collection in Wireless Sensor Networks}, booktitle = {2010 Proceedings IEEE INFOCOM}, year = {2010}, month = {2010/03/14/19}, pages = {1 - 9}, publisher = {IEEE}, organization = {IEEE}, abstract = {We address the problem of efficiently gathering correlated data from a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding how close we can get to the known theoretical lower bounds. Our proposed approach is based on finding an optimal or a near-optimal compression tree for a given sensor network: a compression tree is a directed tree over the sensor network nodes such that the value of a node is compressed using the value of its parent. We focus on broadcast communication model in this paper, but our results are more generally applicable to a unicast communication model as well. We draw connections between the data collection problem and a previously studied graph concept called weakly connected dominating sets, and we use this to develop novel approximation algorithms for the problem. We present comparative results on several synthetic and real-world datasets showing that our algorithms construct near-optimal compression trees that yield a significant reduction in the data collection cost.}, keywords = {Approximation algorithms, Base stations, Communications Society, Computer networks, Computer science, computing compression trees, Costs, data collection, Data communication, data compression, designing algorithms, Educational institutions, Entropy, graph concept, Monitoring, Protocols, trees (mathematics), weakly connected dominating sets, Wireless sensor networks}, isbn = {978-1-4244-5836-3}, doi = {10.1109/INFCOM.2010.5462035}, author = {Li,Jian and Deshpande, Amol and Khuller, Samir} } @conference {15621, title = {A dynamic data structure for approximate range searching}, booktitle = {Proceedings of the 2010 annual symposium on Computational geometry}, series = {SoCG {\textquoteright}10}, year = {2010}, month = {2010///}, pages = {247 - 256}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {In this paper, we introduce a simple, randomized dynamic data structure for storing multidimensional point sets, called a quadtreap. This data structure is a randomized, balanced variant of a quadtree data structure. In particular, it defines a hierarchical decomposition of space into cells, which are based on hyperrectangles of bounded aspect ratio, each of constant combinatorial complexity. It can be viewed as a multidimensional generalization of the treap data structure of Seidel and Aragon. When inserted, points are assigned random priorities, and the tree is restructured through rotations as if the points had been inserted in priority order. In any fixed dimension d, we show it is possible to store a set of n points in a quadtreap of space O(n). The height h of the tree is O(log n) with high probability. It supports point insertion in time O(h). It supports point deletion in worst-case time O(h2) and expected-case time O(h), averaged over the points of the tree. It can answer ε-approximate spherical range counting queries over groups and approximate nearest neighbor queries in time O(h + (1/ε)d-1).}, keywords = {Approximation algorithms, dynamic data structures, geometric data structures, quadtrees, Range searching}, isbn = {978-1-4503-0016-2}, doi = {10.1145/1810959.1811002}, url = {http://doi.acm.org/10.1145/1810959.1811002}, author = {Mount, Dave and Park,Eunhui} } @conference {17633, title = {New Constructive Aspects of the Lovasz Local Lemma}, booktitle = {2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS)}, year = {2010}, month = {2010/10/23/26}, pages = {397 - 406}, publisher = {IEEE}, organization = {IEEE}, abstract = {The Lov{\textquoteright}{a}sz Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of {\textquoteleft}{\textquoteleft}bad{\textquoteright}{\textquoteright} events, with positive probability. A series of results have provided algorithms to efficiently construct structures whose existence is non-constructively guaranteed by the LLL, culminating in the recent breakthrough of Moser \& Tardos. We show that the output distribution of the Moser-Tardos algorithm well-approximates the emph{conditional LLL-distribution} {\textendash} the distribution obtained by conditioning on all bad events being avoided. We show how a known bound on the probabilities of events in this distribution can be used for further probabilistic analysis and give new constructive and non-constructive results. We also show that when an LLL application provides a small amount of slack, the number of resamplings of the Moser-Tardos algorithm is nearly linear in the number of underlying independent variables (not events!), and can thus be used to give efficient constructions in cases where the underlying proof applies the LLL to super-polynomially many events. Even in cases where finding a bad event that holds is computationally hard, we show that applying the algorithm to avoid a polynomial-sized {\textquoteleft}{\textquoteleft}core{\textquoteright}{\textquoteright} subset of bad events leads to a desired outcome with high probability. We demonstrate this idea on several applications. We give the first constant-factor approximation algorithm for the Santa Claus problem by making an LLL-based proof of Feige constructive. We provide Monte Carlo algorithms for acyclic edge coloring, non-repetitive graph colorings, and Ramsey-type graphs. In all these applications the algorithm falls directly out of the non-constructive LLL-based proof. Our algorithms are very simple, often provide better bounds than previous algorithms, and are in several cases the first efficient algorithms known. As a second type of application we consider settings beyond the critical dependency threshold of the LLL: - - avoiding all bad events is impossible in these cases. As the first (even non-constructive) result of this kind, we show that by sampling from the LLL-distribution of a selected smaller core, we can avoid a fraction of bad events that is higher than the expectation. MAX $k$-SAT is an example of this.}, keywords = {acyclic edge coloring, Algorithm design and analysis, Approximation algorithms, Approximation methods, computational complexity, Computer science, constant factor approximation algorithm, graph colouring, Linearity, Lovasz Local Lemma, MAX k-SAT, Monte Carlo Algorithm, Monte Carlo methods, Moser-Tardos algorithm, nonrepetitive graph coloring, output distribution, polynomial sized core subset, Polynomials, Probabilistc Method, probabilistic analysis, probabilistic logic, probability, Ramsey type graph, Sampling methods, Santa Claus Problem}, isbn = {978-1-4244-8525-3}, doi = {10.1109/FOCS.2010.45}, author = {Haeupler,B. and Saha,B. and Srinivasan, Aravind} } @conference {13385, title = {Minimizing Communication Cost in Distributed Multi-query Processing}, booktitle = {IEEE 25th International Conference on Data Engineering, 2009. ICDE {\textquoteright}09}, year = {2009}, month = {2009/04/29/March}, pages = {772 - 783}, publisher = {IEEE}, organization = {IEEE}, abstract = {Increasing prevalence of large-scale distributed monitoring and computing environments such as sensor networks, scientific federations, Grids etc., has led to a renewed interest in the area of distributed query processing and optimization. In this paper we address a general, distributed multi-query processing problem motivated by the need to minimize the communication cost in these environments. Specifically we address the problem of optimally sharing data movement across the communication edges in a distributed communication network given a set of overlapping queries and query plans for them (specifying the operations to be executed). Most of the problem variations of our general problem can be shown to be NP-Hard by a reduction from the Steiner tree problem. However, we show that the problem can be solved optimally if the communication network is a tree, and present a novel algorithm for finding an optimal data movement plan. For general communication networks, we present efficient approximation algorithms for several variations of the problem. Finally, we present an experimental study over synthetic datasets showing both the need for exploiting the sharing of data movement and the effectiveness of our algorithms at finding such plans.}, keywords = {Approximation algorithms, Communication networks, Computer science, Cost function, Data engineering, distributed communication network, distributed databases, distributed multi-query processing, grid computing, Large-scale systems, NP-hard, optimisation, Polynomials, Publish-subscribe, publish-subscribe systems, Query optimization, Query processing, sensor networks, Steiner tree problem, Tree graphs, trees (mathematics)}, isbn = {978-1-4244-3422-0}, doi = {10.1109/ICDE.2009.85}, author = {Li,Jian and Deshpande, Amol and Khuller, Samir} } @article {17549, title = {A unified approach to scheduling on unrelated parallel machines}, journal = {J. ACM}, volume = {56}, year = {2009}, month = {2009/08//}, pages = {28:1{\textendash}28:31 - 28:1{\textendash}28:31}, abstract = {We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. This algorithm leads to the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria; (ii) better-than-two approximation guarantees for scheduling to minimize the Lp norm of the vector of machine-loads, for all 1 < p < $\infty$; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and any given collection of integer Lp norms. Our algorithm has a natural interpretation as a melding of linear-algebraic and probabilistic approaches. Via this view, it yields a common generalization of rounding theorems due to Karp et al. [1987] and Shmoys \& Tardos [1993], and leads to improved approximation algorithms for the problem of scheduling with resource-dependent processing times introduced by Grigoriev et al. [2007].}, keywords = {Approximation algorithms, Randomized rounding, scheduling under multiple criteria}, isbn = {0004-5411}, doi = {10.1145/1552285.1552289}, url = {http://doi.acm.org/10.1145/1552285.1552289}, author = {Kumar,V. S. Anil and Marathe,Madhav V. and Parthasarathy,Srinivasan and Srinivasan, Aravind} } @conference {17559, title = {Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints}, booktitle = {IEEE INFOCOM 2008. The 27th Conference on Computer Communications}, year = {2008}, month = {2008/04/13/18}, pages = {1166 - 1174}, publisher = {IEEE}, organization = {IEEE}, abstract = {A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting.}, keywords = {Algorithm design and analysis, approximation algorithm, Approximation algorithms, approximation theory, Computer networks, Computer science, graph theory, graph-based model, Interference constraints, polynomial time algorithm, Propagation losses, Protocols, radio networks, radiofrequency interference, signal to interference plus noise ratio, Signal to noise ratio, Throughput, wireless interference, wireless network, Wireless networks}, isbn = {978-1-4244-2025-4}, doi = {10.1109/INFOCOM.2008.172}, author = {Chafekar,D. and Kumart,V. S.A and Marathe,M. V and Parthasarathy,S. and Srinivasan, Aravind} } @article {15572, title = {A practical approximation algorithm for the LMS line estimator}, journal = {Computational Statistics \& Data Analysis}, volume = {51}, year = {2007}, month = {2007/02/01/}, pages = {2461 - 2486}, abstract = {The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Robust estimators are widely used because of their lack of sensitivity to outlying data points. The least median-of-squares (LMS) regression line estimator is among the best known robust estimators. Given a set of n points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0 \< q ⩽ 1 . This problem is equivalent to finding the strip defined by two parallel lines of minimum vertical separation that encloses at least half of the points.The best known exact algorithm for this problem runs in O ( n 2 ) time. We consider two types of approximations, a residual approximation, which approximates the vertical height of the strip to within a given error bound ε r ⩾ 0 , and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound ε q ⩾ 0 . We present two randomized approximation algorithms for the LMS line estimator. The first is a conceptually simple quantile approximation algorithm, which given fixed q and ε q \> 0 runs in O ( n log n ) time. The second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. We prove that when used as a quantile approximation, this algorithm{\textquoteright}s expected running time is O ( n log 2 n ) . We present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm. }, keywords = {Approximation algorithms, least median-of-squares regression, line arrangements, line fitting, randomized algorithms, robust estimation}, isbn = {0167-9473}, doi = {10.1016/j.csda.2006.08.033}, url = {http://www.sciencedirect.com/science/article/pii/S0167947306002921}, author = {Mount, Dave and Netanyahu,Nathan S. and Romanik,Kathleen and Silverman,Ruth and Wu,Angela Y.} } @conference {15244, title = {Achieving anonymity via clustering}, booktitle = {Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems}, series = {PODS {\textquoteright}06}, year = {2006}, month = {2006///}, pages = {153 - 162}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying records is to remove identifying fields such as social security number, name etc. However, recent research has shown that a large fraction of the US population can be identified using non-key attributes (called quasi-identifiers) such as date of birth, gender, and zip code [15]. Sweeney [16] proposed the k-anonymity model for privacy where non-key attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k-1 other records having exactly the same values for quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a pre-specified number of data records. This technique is more general since we have a much larger choice for cluster centers than k-Anonymity. In many cases, it lets us release a lot more information without compromising privacy. We also provide constant-factor approximation algorithms to come up with such a clustering. This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k. We further observe that a few outlier points can significantly increase the cost of anonymization. Hence, we extend our algorithms to allow an ε fraction of points to remain unclustered, i.e., deleted from the anonymized publication. Thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. Our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.}, keywords = {anonymity, Approximation algorithms, clustering, privacy}, isbn = {1-59593-318-2}, doi = {10.1145/1142351.1142374}, url = {http://doi.acm.org/10.1145/1142351.1142374}, author = {Aggarwal,Gagan and Feder,Tom{\'a}s and Kenthapadi,Krishnaram and Khuller, Samir and Panigrahy,Rina and Thomas,Dilys and Zhu,An} } @conference {15642, title = {On the importance of idempotence}, booktitle = {Proceedings of the thirty-eighth annual ACM symposium on Theory of computing}, series = {STOC {\textquoteright}06}, year = {2006}, month = {2006///}, pages = {564 - 573}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {Range searching is among the most fundamental problems in computational geometry. An n-element point set in Rd is given along with an assignment of weights to these points from some commutative semigroup. Subject to a fixed space of possible range shapes, the problem is to preprocess the points so that the total semigroup sum of the points lying within a given query range η can be determined quickly. In the approximate version of the problem we assume that η is bounded, and we are given an approximation parameter ε > 0. We are to determine the semigroup sum of all the points contained within η and may additionally include any of the points lying within distance ε {\textbullet} diam(η) of η{\textquoteright}s boundar.In this paper we contrast the complexity of range searching based on semigroup properties. A semigroup (S,+) is idempotent if x + x = x for all x ∈ S, and it is integral if for all k >= 2, the k-fold sum x + ... + x is not equal to x. For example, (R, min) and (0,1, ∨) are both idempotent, and (N, +) is integral. To date, all upper and lower bounds hold irrespective of the semigroup. We show that semigroup properties do indeed make a difference for both exact and approximate range searching, and in the case of approximate range searching the differences are dramatic.First, we consider exact halfspace range searching. The assumption that the semigroup is integral allows us to improve the best lower bounds in the semigroup arithmetic model. For example, assuming O(n) storage in the plane and ignoring polylog factors, we provide an Ω*(n2/5) lower bound for integral semigroups, improving upon the best lower bound of Ω*(n1/3), thus closing the gap with the O(n1/2) upper bound.We also consider approximate range searching for Euclidean ball ranges. We present lower bounds and nearly matching upper bounds for idempotent semigroups. We also present lower bounds for range searching for integral semigroups, which nearly match existing upper bounds. These bounds show that the advantages afforded by idempotency can result in major improvements. In particular, assuming roughly linear space, the exponent in the ε-dependencies is smaller by a factor of nearly 1/2. All our results are presented in terms of space-time tradeoffs, and our lower and upper bounds match closely throughout the entire spectrum.To our knowledge, our results provide the first proof that semigroup properties affect the computational complexity of range searching in the semigroup arithmetic model. These are the first lower bound results for any approximate geometric retrieval problems. The existence of nearly matching upper bounds, throughout the range of space-time tradeoffs, suggests that we are close to resolving the computational complexity of both idempotent and integral approximate spherical range searching in the semigroup arithmetic model.}, keywords = {Approximation algorithms, Idempotence, Range searching}, isbn = {1-59593-134-1}, doi = {10.1145/1132516.1132598}, url = {http://doi.acm.org/10.1145/1132516.1132598}, author = {Arya,Sunil and Malamatos,Theocharis and Mount, Dave} } @article {15249, title = {An improved approximation algorithm for vertex cover with hard capacities}, journal = {Journal of Computer and System Sciences}, volume = {72}, year = {2006}, month = {2006/02//}, pages = {16 - 33}, abstract = {We study the capacitated vertex cover problem, a generalization of the well-known vertex-cover problem. Given a graph G = ( V , E ) , the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex-cover problem. Previously, approximation algorithms with an approximation factor of 2 were developed with the assumption that an arbitrary number of copies of a vertex may be chosen in the cover. If we are allowed to pick at most a fixed number of copies of each vertex, the approximation algorithm becomes much more complex. Chuzhoy and Naor (FOCS, 2002) have shown that the weighted version of this problem is at least as hard as set cover; in addition, they developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy{\textendash}Naor bound of three and matching (up to lower-order terms) the best approximation ratio known for the vertex-cover problem.}, keywords = {Approximation algorithms, Capacitated covering, Linear programming, Randomized rounding, Set cover, Vertex cover}, isbn = {0022-0000}, doi = {10.1016/j.jcss.2005.06.004}, url = {http://www.sciencedirect.com/science/article/pii/S0022000005000747}, author = {Gandhi,Rajiv and Halperin,Eran and Khuller, Samir and Kortsarz,Guy and Srinivasan, Aravind} } @article {14008, title = {Very fast optimal bandwidth selection for univariate kernel density estimation}, journal = {Technical Reports from UMIACS UMIACS-TR-2005-73}, year = {2006}, month = {2006/01/03/T15:1}, abstract = {Most automatic bandwidth selection procedures for kernel density estimates require estimation of quantities involvingthe density derivatives. Estimation of modes and inflexion points of densities also require derivative estimates. The computational complexity of evaluating the density derivative at M evaluation points given N sample points from the density is O(MN). In this paper we propose a computationally efficient $\epsilon$-exact approximation algorithm for univariate, Gaussian kernel based, density derivative estimation that reduces the computational complexity from O(MN) to linear order (O(N+M)). The constant depends on the desired arbitrary accuracy, $\epsilon$. We apply the density derivative evaluation procedure to estimate the optimal bandwidth for kernel density estimation, a process that is often intractable for large data sets. For example for N = M = 409,600 points while the direct evaluation of the density derivative takes around 12.76 hours the fast evaluation requires only 65 seconds with an error of around $10^{-12)$. Algorithm details, error bounds, procedure to choose the parameters and numerical experiments are presented. We demonstrate the speedup achieved on the bandwidth selection using the {\textquoteleft}{\textquoteleft}solve-the-equation plug-in method{\textquoteright}{\textquoteright} [18]. We also demonstrate that the proposed procedure can be extremely useful for speeding up exploratory projection pursuit techniques. }, keywords = {Approximation algorithms, computational statistics, fast gauss transform, kernel density estimation, projection pursuit}, url = {http://drum.lib.umd.edu/handle/1903/3028}, author = {Raykar,Vikas Chandrakant and Duraiswami, Ramani} } @conference {15243, title = {Broadcasting on networks of workstations}, booktitle = {Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures}, series = {SPAA {\textquoteright}05}, year = {2005}, month = {2005///}, pages = {279 - 288}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {Broadcasting and multicasting are fundamental operations. In this work we develop algorithms for performing broadcast and multicast in clusters of workstations. In this model, sending a message from one machine to another machine in the same cluster takes 1 time unit, and sending a message to a machine in a different cluster takes C time units. Lowekamp and Beguelin proposed heuristics for this model, but their algorithms may produce broadcast times that are arbitrarily worse than optimal. We develop the first constant factor approximation algorithms for this model. Algorithm LCF (Largest Cluster First) for the basic model is simple, efficient and has a worst case approximation guarantee of 2. We then extend these models to more complex models where we remove the assumption that an unbounded amount of simultaneous communication may happen using the global network. The algorithms for these models build on the LCF method developed for the basic problem. Finally, we develop broadcasting algorithms for the postal model where the sending processor does not block for C time units when the message is in transit. Moreover, we assume that the messages are small and so the bottleneck is the latency.}, keywords = {Approximation algorithms, Broadcasting, multicasting}, isbn = {1-58113-986-1}, doi = {10.1145/1073970.1074017}, url = {http://doi.acm.org/10.1145/1073970.1074017}, author = {Khuller, Samir and Kim,Yoo-Ah and Wan,Yung-Chun Justin} } @article {17561, title = {Approximation algorithms for partial covering problems}, journal = {Journal of Algorithms}, volume = {53}, year = {2004}, month = {2004/10//}, pages = {55 - 84}, abstract = {We study a generalization of covering problems called partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-partial set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-partial set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-partial vertex cover) in polynomial time. Without making any assumption about the number of sets an element is in, for instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-partial vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-partial vertex cover on planar graphs, and for covering k points in Rd by disks.}, keywords = {Approximation algorithms, Partial covering, Primal-dual methods, Randomized rounding, Set cover, Vertex cover}, isbn = {0196-6774}, doi = {10.1016/j.jalgor.2004.04.002}, url = {http://www.sciencedirect.com/science/article/pii/S0196677404000689}, author = {Gandhi,Rajiv and Khuller, Samir and Srinivasan, Aravind} } @article {15241, title = {Equivalence of two linear programming relaxations for broadcast scheduling}, journal = {Operations Research Letters}, volume = {32}, year = {2004}, month = {2004/09//}, pages = {473 - 478}, abstract = {A server needs to compute a broadcast schedule for n pages whose request times are known in advance. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. In this paper, we show the equivalence of two apparently different relaxations that have been considered for this problem.}, keywords = {Approximation algorithms, Broadcasting, Linear programming, scheduling}, isbn = {0167-6377}, doi = {10.1016/j.orl.2003.11.012}, url = {http://www.sciencedirect.com/science/article/pii/S016763770300169X}, author = {Khuller, Samir and Kim,Yoo-Ah} } @article {17637, title = {On the approximability of clique and related maximization problems}, journal = {Journal of Computer and System Sciences}, volume = {67}, year = {2003}, month = {2003/11//}, pages = {633 - 651}, abstract = {We consider approximations of the form n1-o(1) for the Maximum Clique problem, where n is the number of vertices in the input graph and where the {\textquotedblleft}o(1){\textquotedblright} term goes to zero as n increases. We show that sufficiently strong negative results for such problems, which we call strong inapproximability results, have interesting consequences for exact computation. A simple sampling method underlies most of our results.}, keywords = {Approximation algorithms, Clique, Inapproximability, Independent set, Packing integer programs, random sampling}, isbn = {0022-0000}, doi = {10.1016/S0022-0000(03)00110-7}, url = {http://www.sciencedirect.com/science/article/pii/S0022000003001107}, author = {Srinivasan, Aravind} } @conference {17583, title = {Dependent rounding in bipartite graphs}, booktitle = {The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings}, year = {2002}, month = {2002///}, pages = {323 - 332}, publisher = {IEEE}, organization = {IEEE}, abstract = {We combine the pipage rounding technique of Ageev \& Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.}, keywords = {Application software, Approximation algorithms, bipartite graph, bipartite graphs, broadcast channels, broadcast scheduling, Broadcasting, capacitated vertex cover, Character generation, computational complexity, Computer science, Delay, edge-sets, Educational institutions, fair scheduling, fractional vectors, graph theory, per-user fairness properties, pipage rounding technique, Processor scheduling, Random variables, random-graph models, randomized rounding approach, rounding method, scheduling, Scheduling algorithm, telecommunication computing, unrelated parallel machines}, isbn = {0-7695-1822-2}, doi = {10.1109/SFCS.2002.1181955}, author = {Gandhi,R. and Khuller, Samir and Parthasarathy,S. and Srinivasan, Aravind} } @conference {15624, title = {A local search approximation algorithm for k-means clustering}, booktitle = {Proceedings of the eighteenth annual symposium on Computational geometry}, series = {SCG {\textquoteright}02}, year = {2002}, month = {2002///}, pages = {10 - 18}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {In k-means clustering we are given a set of n data points in d-dimensional space Rd and an integer k, and the problem is to determine a set of k points in {\'O}C;d, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+\&egr;)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-\&egr;). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd{\textquoteright}s algorithm, this heuristic performs quite well in practice.}, keywords = {Approximation algorithms, clustering, computational geometry, k-means, local search}, isbn = {1-58113-504-1}, doi = {10.1145/513400.513402}, url = {http://doi.acm.org/10.1145/513400.513402}, author = {Kanungo,Tapas and Mount, Dave and Netanyahu,Nathan S. and Piatko,Christine D. and Silverman,Ruth and Wu,Angela Y.} } @article {17670, title = {Wavelength rerouting in optical networks, or the Venetian Routing problem}, journal = {Journal of Algorithms}, volume = {45}, year = {2002}, month = {2002/11//}, pages = {93 - 125}, abstract = {Wavelength rerouting has been suggested as a viable and cost-effective method to improve the blocking performance of wavelength-routed wavelength-division multiplexing (WDM) networks. This method leads to the following combinatorial optimization problem, dubbed Venetian Routing. Given a directed multigraph G along with two vertices s and t and a collection of pairwise arc-disjoint paths, we wish to find an st-path which arc-intersects the smallest possible number of the given paths. In this paper we prove the computational hardness of this problem even in various special cases, and present several approximation algorithms for its solution. In particular we show a non-trivial connection between Venetian Routing and Label Cover.}, keywords = {Approximation algorithms, Label Cover, Optical networks, Shortest paths, Wavelength rerouting, Wavelength-division multiplexing}, isbn = {0196-6774}, doi = {10.1016/S0196-6774(02)00214-6}, url = {http://www.sciencedirect.com/science/article/pii/S0196677402002146}, author = {Caprara,Alberto and Italiano,Giuseppe F. and Mohan,G. and Panconesi,Alessandro and Srinivasan, Aravind} } @conference {17586, title = {Distributions on level-sets with applications to approximation algorithms}, booktitle = {42nd IEEE Symposium on Foundations of Computer Science, 2001. Proceedings}, year = {2001}, month = {2001/10/08/11}, pages = {588 - 597}, publisher = {IEEE}, organization = {IEEE}, abstract = {We consider a family of distributions on fixed-weight vectors in {0, 1}t; these distributions enjoy certain negative correlation properties and also satisfy pre-specified conditions on their marginal distributions. We show the existence of such families, and present a linear-time algorithm to sample from them. This yields improved approximation algorithms for the following problems: (a) low-congestion multi-path routing; (b) maximum coverage versions of set cover; (c) partial vertex cover problems for bounded-degree graphs; and (d) the Group Steiner Tree problem. For (a) and (b), the improvement is in the approximation ratio; for (c), we show how to speedup existing approximation algorithms while preserving the best-known approximation ratio; we also improve the approximation ratio for certain families of instances of unbounded degree. For (d), we derive an approximation algorithm whose approximation guarantee is at least as good as what is known; our algorithm is shown to have a better approximation guarantee for the worst known input families for existing algorithms.}, keywords = {Approximation algorithms, approximation guarantee, approximation theory, bounded-degree graphs, computational geometry, Concrete, fixed-weight vectors, group Steiner tree problem, level-sets, linear-time algorithm, low-congestion multi-path routing, marginal distributions, maximum coverage versions, negative correlation properties, partial vertex cover problems, trees (mathematics)}, isbn = {0-7695-1116-3}, doi = {10.1109/SFCS.2001.959935}, author = {Srinivasan, Aravind} } @article {15563, title = {Approximate range searching}, journal = {Computational Geometry}, volume = {17}, year = {2000}, month = {2000/12//}, pages = {135 - 152}, abstract = {The range searching problem is a fundamental problem in computational geometry, with numerous important applications. Most research has focused on solving this problem exactly, but lower bounds show that if linear space is assumed, the problem cannot be solved in polylogarithmic time, except for the case of orthogonal ranges. In this paper we show that if one is willing to allow approximate ranges, then it is possible to do much better. In particular, given a bounded range Q of diameter w and ε\>0, an approximate range query treats the range as a fuzzy object, meaning that points lying within distance εw of the boundary of Q either may or may not be counted. We show that in any fixed dimension d, a set of n points in Rd can be preprocessed in O(n+logn) time and O(n) space, such that approximate queries can be answered in O(logn(1/ε)d) time. The only assumption we make about ranges is that the intersection of a range and a d-dimensional cube can be answered in constant time (depending on dimension). For convex ranges, we tighten this to O(logn+(1/ε)d-1) time. We also present a lower bound for approximate range searching based on partition trees of Ω(logn+(1/ε)d-1), which implies optimality for convex ranges (assuming fixed dimensions). Finally, we give empirical evidence showing that allowing small relative errors can significantly improve query execution times.}, keywords = {Approximation algorithms, Box-decomposition trees, Partition trees, Range searching}, isbn = {0925-7721}, doi = {10.1016/S0925-7721(00)00022-5}, url = {http://www.sciencedirect.com/science/article/pii/S0925772100000225}, author = {Arya,Sunil and Mount, Dave} } @article {17555, title = {Approximating low-congestion routing and column-restricted packing problems}, journal = {Information Processing Letters}, volume = {74}, year = {2000}, month = {2000/04//}, pages = {19 - 25}, abstract = {We contribute to a body of research asserting that the fractional and integral optima of column-sparse integer programs are {\textquotedblleft}nearby{\textquotedblright}. This yields improved approximation algorithms for some generalizations of the knapsack problem, with applications to low-congestion routing in networks, file replication in distributed databases, and other packing problems.}, keywords = {algorithms, Approximation algorithms, integer programming, Packing, Routing}, isbn = {0020-0190}, doi = {10.1016/S0020-0190(00)00033-8}, url = {http://www.sciencedirect.com/science/article/pii/S0020019000000338}, author = {Baveja,Alok and Srinivasan, Aravind} } @article {17560, title = {Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems}, journal = {Mathematics of Operations ResearchMathematics of Operations Research}, volume = {25}, year = {2000}, month = {2000/05/01/}, pages = {255 - 280}, abstract = {Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improved approximation algorithms and/or integrality gaps for all problems considered; the central theme of this work is the underlying multicommodity flow relaxation. Applications of these techniques to approximating families of packing integer programs are also presented.}, keywords = {Approximation algorithms, Disjoint paths, integer programming, Linear programming, multicommodity flow, Packing, randomized algorithms, rounding, Routing, unsplittable flow}, isbn = {0364-765X, 1526-5471}, doi = {10.1287/moor.25.2.255.12228}, url = {http://mor.journal.informs.org/content/25/2/255}, author = {Baveja,Alok and Srinivasan, Aravind} } @article {15234, title = {Fault tolerant K-center problems}, journal = {Theoretical Computer Science}, volume = {242}, year = {2000}, month = {2000/07/06/}, pages = {237 - 245}, abstract = {The basic K-center problem is a fundamental facility location problem, where we are asked to locate K facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. This problem is known to be NP-hard, and several optimal approximation algorithms that achieve an approximation factor of 2 have been developed for it. We focus our attention on a generalization of this problem, where each vertex is required to have a set of α (α⩽K) centers close to it. In particular, we study two different versions of this problem. In the first version, each vertex is required to have at least α centers close to it. In the second version, each vertex that does not have a center placed on it is required to have at least α centers close to it. For both these versions we are able to provide polynomial time approximation algorithms that achieve constant approximation factors for any α. For the first version we give an algorithm that achieves an approximation factor of 3 for any α, and achieves an approximation factor of 2 for α\<4. For the second version, we provide algorithms with approximation factors of 2 for any α. The best possible approximation factor for even the basic K-center problem is 2, assuming P/=NP. In addition, we give a polynomial time approximation algorithm for a generalization of the K-supplier problem where a subset of at most K supplier nodes must be selected as centers so that every demand node has at least α centers close to it. For this version our approximation factor is 3. The best possible approximation factor for even the basic K-supplier problem is 3, assuming P/=NP.}, keywords = {Approximation algorithms, Facility location, Fault-tolerance, K-center}, isbn = {0304-3975}, doi = {10.1016/S0304-3975(98)00222-9}, url = {http://www.sciencedirect.com/science/article/pii/S0304397598002229}, author = {Khuller, Samir and Pless,Robert and Sussmann,Yoram J.} } @conference {17669, title = {The value of strong inapproximability results for clique}, booktitle = {Proceedings of the thirty-second annual ACM symposium on Theory of computing}, series = {STOC {\textquoteright}00}, year = {2000}, month = {2000///}, pages = {144 - 152}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, keywords = {P vs. NP, Approximation algorithms, Clique, inapproximabilit, Independent set, Packing integer programs, random sampling}, isbn = {1-58113-184-4}, doi = {10.1145/335305.335322}, url = {http://doi.acm.org/10.1145/335305.335322}, author = {Srinivasan, Aravind} } @conference {17609, title = {Improved bounds and algorithms for hypergraph two-coloring}, booktitle = {39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings}, year = {1998}, month = {1998/11/08/11}, pages = {684 - 693}, publisher = {IEEE}, organization = {IEEE}, abstract = {We show that for all large n, every n-uniform hypergraph with at most 0.7√(n/lnn){\texttimes}2n edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC1 versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n1/3-0(1){\texttimes}2n due to Beck (1978). We further generalize this to a {\textquotedblleft}local{\textquotedblright} version, improving on one of the first applications of the Lovasz Local Lemma}, keywords = {algorithms, Application software, Approximation algorithms, bounds, computational geometry, Computer science, Contracts, Erbium, graph colouring, History, hypergraph two-coloring, Lab-on-a-chip, MATHEMATICS, n-uniform hypergraph, Parallel algorithms, Polynomials, probability}, isbn = {0-8186-9172-7}, doi = {10.1109/SFCS.1998.743519}, author = {Radhakrishnan,J. and Srinivasan, Aravind} } @article {15611, title = {An optimal algorithm for approximate nearest neighbor searching fixed dimensions}, journal = {Journal of the ACM (JACM)}, volume = {45}, year = {1998}, month = {1998/11//}, pages = {891 - 923}, abstract = {Consider a set of S of n data points in real d-dimensional space, Rd, where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q ∈ Rd, is the closest point of S to q can be reported quickly. Given any positive real \&egr;, data point p is a (1 +\&egr;)-approximate nearest neighbor of q if its distance from q is within a factor of (1 + \&egr;) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in Rd in O(dn log n) time and O(dn) space, so that given a query point q ∈ Rd, and \&egr; > 0, a (1 + \&egr;)-approximate nearest neighbor of q can be computed in O(cd, \&egr; log n) time, where cd,\&egr;<=d 1 + 6d/e;d is a factor depending only on dimension and \&egr;. In general, we show that given an integer k >= 1, (1 + \&egr;)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n) time.}, keywords = {Approximation algorithms, Box-decomposition trees, closet-point queries, nearest neighbor searching, post-office problem, priority search}, isbn = {0004-5411}, doi = {10.1145/293347.293348}, url = {http://doi.acm.org/10.1145/293347.293348}, author = {Arya,Sunil and Mount, Dave and Netanyahu,Nathan S. and Silverman,Ruth and Wu,Angela Y.} } @conference {17545, title = {A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria}, booktitle = {Proceedings of the twenty-ninth annual ACM symposium on Theory of computing}, series = {STOC {\textquoteright}97}, year = {1997}, month = {1997///}, pages = {636 - 643}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, keywords = {Approximation algorithms, covering integer programs, discrete ham-sandwich theorems, Linear programming, packet routing, randomized algorithms, Randomized rounding, rounding theorems}, isbn = {0-89791-888-6}, doi = {10.1145/258533.258658}, url = {http://doi.acm.org/10.1145/258533.258658}, author = {Srinivasan, Aravind and Teo,Chung-Piaw} } @conference {17607, title = {Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems}, booktitle = {, 38th Annual Symposium on Foundations of Computer Science, 1997. Proceedings}, year = {1997}, month = {1997/10/20/22}, pages = {416 - 425}, publisher = {IEEE}, organization = {IEEE}, abstract = {We present improved approximation algorithms for a family of problems involving edge-disjoint paths and unsplittable flow, and for some related routing problems. The central theme of all our algorithms is the underlying multi-commodity flow relaxation}, keywords = {Approximation algorithms, Bandwidth, Channel allocation, computational complexity, Computer science, edge-disjoint paths, graph theory, High speed integrated circuits, IEL, Image motion analysis, Information systems, multi-commodity flow relaxation, Multiprocessor interconnection networks, network routing, Optical fiber networks, Routing, routing problems, unsplittable flow}, isbn = {0-8186-8197-7}, doi = {10.1109/SFCS.1997.646130}, author = {Srinivasan, Aravind} } @conference {15625, title = {A practical approximation algorithm for the LMS line estimator}, booktitle = {Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms}, series = {SODA {\textquoteright}97}, year = {1997}, month = {1997///}, pages = {473 - 482}, publisher = {Society for Industrial and Applied Mathematics}, organization = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, keywords = {Approximation algorithms, least median-of-squares regression, line arrangements, line fitting, randomized algorithms, robust estimation}, isbn = {0-89871-390-0}, url = {http://dl.acm.org/citation.cfm?id=314161.314349}, author = {Mount, Dave and Netanyahu,Nathan S. and Romanik,Kathleen and Silverman,Ruth and Wu,Angela Y.} }