1,721,285 research outputs found
All-norms and all-Lp-norms approximation algorithms
Full text linkwork was done while the author was at Max-Planck-Institut für Informatik, Saarbrücken, Germany
Differentially Private Combinatorial Optimization
Full text linkConsider the following problem: given a metric space, some of whose points are ``clients,'' select a set of at most facility locations to minimize the average distance from the clients to their nearest facility. This is just the well-studied -median problem, for which many approximation algorithms and hardness results are known. Note that the objective function encourages opening facilities in areas where there are many clients, and given a solution, it is often possible to get a good idea of where the clients are located. This raises the following quandary: what if the locations of the clients are sensitive information that we would like to keep private? emph{Is it even possible to design good algorithms for this problem that preserve the privacy of the clients?}
In this paper, we initiate a systematic study of algorithms for discrete optimization problems in the framework of differential privacy (which formalizes the idea of protecting the privacy of individual input elements). We show that many such problems indeed have good approximation algorithms that preserve differential privacy; this is even in cases where it is impossible to preserve cryptographic definitions of privacy while computing any non-trivial approximation to even the emph{value} of an optimal solution, let alone the entire solution.
Apart from the -median problem, we consider the problems of vertex and set cover, min-cut, facility location, and Steiner tree, and give approximation algorithms and lower bounds for these problems. We also consider the recently introduced submodular maximization problem, ``Combinatorial Public Projects'' (CPP), shown by Papadimitriou et al. cite{PSS08} to be inapproximable to subpolynomial multiplicative factors by any efficient and emph{truthful} algorithm. We give a differentially private (and hence approximately truthful) algorithm that achieves a logarithmic additive approximation.
Joint work with Anupam Gupta, Katrina Ligett, Frank McSherry and Aaron Roth
Graph Algorithms for Planning and Partitioning
No full textIn this thesis, we present new approximation algorithms as well as hardness of approximation results for several planning and partitioning problems. In planning problems, one is typically given a set of locations to visit, along with timing constraints, such as deadlines for visiting them; The goal is to visit a large number of locations as efficiently as possible. We give the first approximation algorithms for problems such as ORIENTEERING, DEADLINES-TSP, and TIME-WINDOWS-TSP, as well as results for planning in stochastic graphs (Markov decision processes). The goal in partitioning problems is to partition a set of objects into clusters while satisfying "split" or "combine" constraints on pairs of objects. We consider three kinds of partitioning problems, viz. CORRELATIONCLUSTERING, SPARSEST-CUT, and MULTICUT. We give approximation algorithms for the first two, and improved hardness of approximation results for SPARSEST-CUT and MULTICUT. ii To my grandmothers, (late) Smt. Sita Devi Chawla and Smt. Satyawati Malhotra iii iv Acknowledgements I am grateful to my advisor, Prof. Avrim Blum, for being understanding and patient, for being a great source of information and insight, and for giving me the freedom to work at my own pace on topics of my choice. Thanks also to Dr. Cynthia Dwork and Prof. Anupam Gupta for being great mentors and role models. Prof. Moses Charikar and Prof. R. Ravi helped shape a large part of this thesis through numerous discussions; I am grateful to them for their help and advice during the final year of my graduate study. This thesis would not have been possible without the cooperation of my numerous co-authors --- thanks to you all! An enormous thanks to Aditya and Luis for maintaining my sanity (and sometimes making me lose it) during gra..
15-854: Approximations Algorithms Lecturer: Anupam Gupta
No full textWe have seen several randomized approximation algorithms before. Recall that for the MAX-CUT and MAX-3SAT problems we proved that choosing any solution uniformly at random gives a constant factor approximation in the expectation. For MAX-CUT the approximation factor was 2. For MAX-3SAT, a random assignment of truth values to a variable satisfies a given clause with probability 7 8. In the case of MAX-3SAT, it is possible to derandomize the algorithm and get a deterministic performance guarantee of 8 7. Furthermore, this approximation is tight as it has been shown that finding a better approximation is NP-Hard. Today, we will look at two other problems where flipping coins allows us to get a good approximation in the expectation. Specifically, we will be looking at VERTEX-COVER and RENT-OR-BUY. In each of these we will have to be more clever with our randomness than we were for MAX-CUT and MAX-3SAT. 11.2 Two flavors of Performance Guarantee for Randomized Approximations In many cases, we may find that we desire a randomized algorithm that performs well with high probability rather than simply in the expectation. In such cases we want an algorithm A with a guarantee of the form A(I) ≤ ρOP T (11.2.1) with high probability (on the order of 1 − 1 poly(n) ) for all instance I. In general, approximation algorithms that do well in the expectation can be converted to algorithms that do well with high probability. That is, given ɛ> 0, it possible to convert algorithm A with guarantee into an algorithm A ′ with performance guarantee E[A(I)] ≤ ρOP T (11.2.2) A ′ (I) ≤ ρ(1 + ɛ)OP T (11.2.3) with high probability. The method is simply to run the algorithm that does well in the expectation several times and choose the best answer. Let t be the number of times we run the algorithm to get a good answer. We need to show that t is not too large. First we observe the probability that the algorithm performs worse than expected by a factor of more than (1 + ɛ) is bounded by
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Online Algorithm Design Beyond the Worst Case (Invited Talk)
No full textThe analysis of algorithm performance in the worst-case has long been the gold standard of theoretical computer science: it provides a simple, compelling, and robust model, which can often be predictive as well as descriptive. That said, in recent years we have seen an exciting surge in analyzing algorithms using models that go beyond the worst case. Particularly, how can we use ideas from machine learning to inform algorithm design?
In this talk we will discuss some of the results and techniques that come out of this endeavor, in both offline and online settings. For example, we will study covering problems like set cover, load balancing problems like scheduling jobs of machines, and cut problems. We will see some of the modeling decisions in beyond worst-case frameworks, as well as the algorithmic ideas - some old, some new - that can be used to give more nuanced guarantees for these classical problems, complementing our understanding of these problem in the worst-case settings
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk)
No full textAnalyzing the performance of algorithms in both the worst case and the average case are cornerstones of computer science: these are two different ways to understand how well algorithms perform. Over the past two decades, there has been a concerted effort to understand the performance of algorithms in models that go beyond these two extremes. In this talk I will discuss some of the proposed models and approaches, particularly for problems related to online algorithms, where decisions must be made sequentially without knowing future portions of the input
- …
