Warning, /office/kbibtex-testset/bib/general-collection.bib is written in an unsupported language. File is not indexed.

 @comment{x-kbibtex-encoding=utf-8}
 
 @inproceedings{DKP10-distr-const-factor-dynamic-flp,
         abstract = "We present a distributed, local solution to the dynamic facility location problem in general metrics, where each node is able to act as a facility or a client. To decide which role it should take, each node keeps up a simple invariant in its local neighborhood. This guarantees a global constant factor approximation when the invariant is satisfied at all nodes. Due to the changing distances between nodes, invariants can be violated. We show that restoring the invariants is bounded to a constant neighborhood, takes logarithmic (in the number of nodes) asynchronous rounds and affects each node at most twice per violation.",
         author = "Degener, Bastian and Kempkes, Barbara and Pietrzyk, Peter",
         booktitle = "{Proceedings of IPDPS 2010}",
         crossref = "DGL08_Kinetic-Facility-Location",
         file = "Pre-Print:/home/phoenixx/Studium/MasterThesis/DKP10\_local\_distr\_const-factor\_dynamic\_fcp.pdf:PDF",
         keywords = "facility location; dynamic; constant factor approximation; local",
         organization = "IPDPS 2010",
         owner = "phoenixx",
         timestamp = "2010.02.28",
         title = "{A local, distributed constant-factor approximation algorithm for the dynamic facility location problem}",
         year = "2010"
 }
 
 @inproceedings{LMM04_scheduling_against_adversarial_network,
         abstract = "Using idle times of the processors is a well-known approach to run coarse grained parallel algorithms for extremely complex problems. We present on-line algorithms for scheduling the processes of a parallel application that is known off-line on a dynamic network in which the idle times of the processors are dictated by an adversary. We also take communication and synchronization costs into account. Our first contribution consists of a formal model to restrict the adversary in a reasonable way. We then show a constant factor approximation for the off-line scheduling problem. As this problem has to take communication cost into account, it can be seen as a generalization of many NP-hard parallel machine scheduling problems. Finally, we present on-line algorithms for different models with constant or with nearly constant competitive ratio.",
         added-at = "2006-02-15T00:00:00.000+0100",
         author = "Leonardi, Stefano and Marchetti-Spaccamela, Alberto and auf der Heide, Friedhelm Meyer",
         booktitle = "{Proceedings of the 16th ACM Symposium of Parallelism in Algorithms and Architectures (SPAA '04)}",
         crossref = "conf/spaa/2004",
         date = "2006-02-15",
         description = "dblp",
         editor = "Gibbons, Phillip B. and Adler, Micah",
         interhash = "67ad1818fa8dd30668085b8325c87a18",
         intrahash = "ec240ce81d095bc052ea751d502e87c5",
         isbn = "1-58113-840-7",
         keywords = Scheduling # "Online Algorithm; Competitive Analysis",
         month = jun,
         pages = "151–159",
         publisher = "ACM",
         title = "{Scheduling against an adversarial network}",
         url = "http://dblp.uni-trier.de/db/conf/spaa/spaa2004.html#LeonardiMH04; http://doi.acm.org/10.1145/1007912.1007936; http://www.bibsonomy.org/bibtex/2ec240ce81d095bc052ea751d502e87c5/dblp",
         year = 2004
 }
 
 @inproceedings{DGNR09_online_story_scheduling_in_web_advertising,
         abstract = "We study an online job scheduling problem motivated by \emph{storyboarding} in web advertising, where an advertiser derives value from having uninterrupted sequential access to a user surfing the web. The user ceases to browse with probability $1-\beta$ at each step, independently. Stories (jobs) arrive online; job $s$ has a length $\ell\_s$ and a per-unit value $\v\_s$. We get a value $\v\_s$ for every unit of the job that we schedule consecutively without interruption, discounted for the time at which it is scheduled. Jobs can be preempted, with no further value derived from the residual unscheduled units of the job. We seek an online algorithm whose total reward is competitive against that of the offline scheduler that knows all jobs in advance. We consider two models based on the maximum delay that can be allowed between the arrival and scheduling of a job. In the first, a job can be scheduled anytime after its arrival; in the second a job is lost unless scheduled immediately upon arrival, pre-empting a currently running job if needed. The two settings correspond to two natural models of how long an advertiser retains interest in a relevant user. We show that there is, in fact, a {\em sharp separation} between what an online scheduler can achieve in these two settings. In the first setting with no deadlines, we give a natural deterministic algorithm with a constant competitive ratio against the offline scheduler. In contrast, we show that in the sharp deadline setting, no (deterministic or randomized) online algorithm can achieve better than a polylogarithmic ratio.",
         added-at = "2009-01-24T00:00:00.000+0100",
         address = "Philadelphia, PA, USA",
         author = "Dasgupta, Anirban and Ghosh, Arpita and Nazerzadeh, Hamid and Raghavan, Prabhakar",
         booktitle = "{Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms}",
         crossref = "conf/soda/2009",
         date = "2009-01-24",
         description = "dblp",
         editor = "Mathieu, Claire",
         interhash = "490caba3eaab01862d082cde767d83f1",
         intrahash = "08ee0846d5114cf38c925410c15d1303",
         keywords = "dblp",
         location = "New York, New York",
         pages = "1275–1284",
         publisher = "Society for Industrial and Applied Mathematics (SIAM)",
         series = "{SODA '09}",
         title = "{Online story scheduling in web advertising}",
         url = "http://dblp.uni-trier.de/db/conf/soda/soda2009.html#DasguptaGNR09; http://doi.acm.org/10.1145/1496770.1496908; http://www.bibsonomy.org/bibtex/208ee0846d5114cf38c925410c15d1303/dblp",
         year = 2009
 }
 
 @inproceedings{AB09_coresets-and-approximate-clustering-for-bregman-divergences,
         added-at = "2009-01-24T00:00:00.000+0100",
         author = "Ackermann, Marcel R. and Blömer, Johannes",
         booktitle = "{SODA}",
         crossref = "conf/soda/2009",
         date = "2009-01-24",
         description = "dblp",
         editor = "Mathieu, Claire",
         interhash = "6b56c21640088899e3b246fa7fd9a23a",
         intrahash = "ca82e3e3ba36f49e3d651e9839e4a470",
         keywords = "dblp",
         localfile = "archive/AB09_coresets-and-approximate-clustering-for-bregman-divergences.pdf",
         pages = "1088–1097",
         publisher = "SIAM",
         title = "{Coresets and approximate clustering for Bregman divergences.}",
         url = "http://dblp.uni-trier.de/db/conf/soda/soda2009.html#AckermannB09; http://doi.acm.org/10.1145/1496770.1496888; http://www.bibsonomy.org/bibtex/2ca82e3e3ba36f49e3d651e9839e4a470/dblp",
         year = 2009
 }
 
 @inproceedings{YG01_comparing_hybrid_p2p_systems,
         abstract = {"Peer-to-peer" systems like Napster and Gnutella have recently become popular for sharing information. In this paper, we study the relevant issues and tradeoffs in designing a scalable P2P system. We focus on a subset of P2P systems, known as "hybrid" P2P, where some functionality is still centralized. (In Napster, for example, indexing is centralized, and file exchange is distributed.) We model a file-sharing application, developing a probabilistic model to describe query behavior and expected query result sizes. We also develop an analytic model to describe system performance. Using experimental data collected from a running, publicly available hybrid P2P system, we validate both models. We then present several hybrid P2P system architectures and evaluate them using our model. We discuss the tradeoffs between the architectures and highlight the effects of key parameter values on system performance.},
         added-at = "2002-01-03T00:00:00.000+0100",
         author = "Yang, Beverly and Garcia-Molina, Hector",
         booktitle = "{VLDB}",
         crossref = "conf/vldb/2001",
         date = "2002-01-03",
         description = "dblp",
         editor = "Apers, Peter M. G. and Atzeni, Paolo and Ceri, Stefano and Paraboschi, Stefano and Ramamohanarao, Kotagiri and Snodgrass, Richard T.",
         interhash = "12560ac0ed3053a9b50c851f02419244",
         intrahash = "364cc66f5b65bfc7fa41a3e885cde33c",
         isbn = "1-55860-804-4",
         keywords = "dblp",
         note = "Evaluation",
         pages = "561––570",
         publisher = "Morgan Kaufmann",
         title = "{Comparing Hybrid Peer-to-Peer Systems.}",
         url = "http://dblp.uni-trier.de/db/conf/vldb/vldb2001.html#YangG01; http://www.vldb.org/conf/2001/P561.pdf; http://www.bibsonomy.org/bibtex/2364cc66f5b65bfc7fa41a3e885cde33c/dblp",
         year = 2001
 }
 
 @inproceedings{conf/icalp/ChaintreauFL08,
         abstract = "We propose a dynamic process for network evolution, aiming at explaining the emergence of the small world phenomenon, i.e., the statistical observation that any pair of individuals are linked by a short chain of acquaintances computable by a simple decentralized routing algorithm, known as greedy routing. Our model is based on the combination of two dynamics: a random walk (spatial) process, and an harmonic forgetting (temporal) process. Both processes reflect natural behaviors of the individuals, viewed as nodes in the network of inter-individual acquaintances. We prove that, in k-dimensional lattices, the combination of these two processes generates long-range links mutually independently distributed as a k-harmonic distribution. We analyze the performances of greedy routing at the stationary regime of our process, and prove that the expected number of steps for routing from any source to any target in any multidimensional lattice is a polylogarithmic function of the distance between the two nodes in the lattice. Up to our knowledge, these results are the first formal proof that navigability in small worlds can emerge from a dynamic process for network evolution. Our dynamica process can find practical applications to the design of spatial gossip and resource location protocols.",
         added-at = "2008-07-08T00:00:00.000+0200",
         address = "Berlin, Heidelberg",
         author = "Chaintreau, Augustin and Fraigniaud, Pierre and Lebhar, Emmanuelle",
         booktitle = "{Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I}",
         crossref = "conf/icalp/2008-1",
         date = "2008-07-08",
         description = "dblp",
         editor = "Aceto, Luca and Damgård, Ivan and Goldberg, Leslie Ann and Halldórsson, Magnús M. and Ingólfsdóttir, Anna and Walukiewicz, Igor",
         interhash = "a4081126ff934cce0ed38ddf8db6af2a",
         intrahash = "40906a7e2ffb9fd967400d38b8bdd1c6",
         isbn = "978-3-540-70574-1",
         keywords = "Small world phenomenon; dynamic process; random walks; resource location; routing; spatial gossip",
         localfile = "archive/CFL08_networks_become_navigable_as_nodes_move_and_forget.pdf",
         location = "Reykjavik, Iceland",
         pages = "133–144",
         publisher = "Springer-Verlag",
         series = "{Lecture Notes in Computer Science}",
         title = "{Networks Become Navigable as Nodes Move and Forget}",
         url = "http://dx.doi.org/10.1007/978-3-540-70575-8_12; http://portal.acm.org/citation.cfm?id=1427911; http://dblp.uni-trier.de/db/conf/icalp/icalp2008-1.html#ChaintreauFL08",
         volume = 5125,
         year = 2008
 }
 
 @inproceedings{GJRSST10_distr-graph-linearization,
         abstract = "Topological self-stabilization is an important concept to build robust open distributed systems (such as peer-to-peer systems) where nodes can organize themselves into meaningful network topologies. The goal is to devise distributed algorithms that converge quickly to such a desirable topology, independently of the initial network state. This paper proposes a new model to study the parallel convergence time. Our model sheds light on the achievable parallelism by avoiding bottlenecks of existing models that can yield a distorted picture. As a case study, we consider local graph linearization—i.e., how to build a sorted list of the nodes of a connected graph in a distributed and self-stabilizing manner. We propose two variants of a simple algorithm, and provide an extensive formal analysis of their worst-case and best-case parallel time complexities, as well as their performance under a greedy selection of the actions to be executed.",
         added-at = "2010-07-21T16:01:11.000+0200",
         author = "Gall, Dominik and Jacob, Riko and Richa, Andréa W. and Scheideler, Christian and Schmid, Stefan and Täubig, Hanjo",
         booktitle = "{LATIN 2010: Theoretical Informatics}",
         crossref = "conf/latin/2010",
         date = "2010-04-27",
         editor = "López-Ortiz, Alejandro",
         interhash = "485f14443b751421dc44d051dfe304b7",
         intrahash = "d004e207935c5358f56f76b8ffebe657",
         isbn = "978-3-642-12199-9",
         keywords = "graph linearization",
         localfile = "archive/GJRSST10_distr-graph-linearization.pdf",
         pages = "294–305",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         title = "{Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization.}",
         url = "http://dblp.uni-trier.de/db/conf/latin/latin2010.html#GallJRSST10; http://dx.doi.org/10.1007/978-3-642-12200-2_27; http://www.bibsonomy.org/bibtex/2d004e207935c5358f56f76b8ffebe657/dblp",
         volume = 6034,
         year = 2010
 }
 
 @article{J01_factor-2-approx-GSNP,
         abstract = "We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, which is also known as the survivable network design problem. Our algorithm first solves the linear relaxation of this problem, and then iteratively rounds off the solution. The key idea in rounding off is that in a basic solution of the LP relaxation, at least one edge gets included at least to the extent of half. We include this edge into our integral solution and solve the residual problem. ",
         affiliation = "College of Computing, Georgia Institute of Technology; USA; E-mail: kjain@cc.gatech.edu US",
         author = "Jain, Kamal",
         issn = "0209-9683",
         issue = "1",
         journal = "Combinatorica",
         keyword = "Mathematics and Statistics",
         keywords = "Steiner tree; approximation algorithm",
         localfile = "archive/J01_factor-2-approx-GSNP.pdf",
         note = "10.1007/s004930170004",
         pages = "39–60",
         publisher = "Springer Berlin / Heidelberg",
         title = "{A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem}",
         url = "http://dx.doi.org/10.1007/s004930170004",
         volume = "21",
         year = "2001"
 }
 
 @article{agrawal1995trees,
         author = "Agrawal, A. and Klein, PN and Ravi, R.",
         journal = "Comput",
         keywords = "GNWS - Generalized Node-Weighted Steiner Tree Problem",
         pages = "440–456",
         title = "{When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks,(preliminary version appeared in Proc. 23nd STOC,(1991), 134-144), the journal version appeared in SIAM J}",
         volume = "24",
         x-fetchedfrom = "Google Scholar",
         year = "1995"
 }
 
 @article{JRSS09_selfstabilizing_delaunay-graphs,
         author = "Jacob, Riko and Ritscher, Stephan and Scheideler, Christian and Schmid, Stefan",
         booktitle = "{Algorithms and Computation}",
         pages = "771–780",
         publisher = "Springer-Verlag",
         series = "{Lecture Notes in Computer Science}",
         title = "{A Self-stabilizing and Local Delaunay Graph Construction}",
         url = "http://dx.doi.org/10.1007/978-3-642-10631-6_78",
         volume = "5878",
         year = "2009"
 }
 
 @incollection{AEMN06_constant_factor_dom_sets_udg,
         abstract = "For a given graph with weighted vertices, the goal of the minimum-weight dominating set problem is to compute a vertex subset of smallest weight such that each vertex of the graph is contained in the subset or has a neighbor in the subset. A unit disk graph is a graph in which each vertex corresponds to a unit disk in the plane and two vertices are adjacent if and only if their disks have a non-empty intersection. We present the first constant-factor approximation algorithm for the minimum-weight dominating set problem in unit disk graphs, a problem motivated by applications in wireless ad-hoc networks. The algorithm is obtained in two steps: First, the problem is reduced to the problem of covering a set of points located in a small square using a minimum-weight set of unit disks. Then, a constant-factor approximation algorithm for the latter problem is obtained using enumeration and dynamic programming techniques exploiting the geometry of unit disks. Furthermore, we also show how to obtain a constant-factor approximation algorithm for the minimum-weight connected dominating set problem in unit disk graphs.",
         affiliation = "Department of Computer Science, University of Liverpool",
         author = "Ambühl, Christoph and Erlebach, Thomas and Mihalák, Matúš and Nunkesser, Marc",
         booktitle = "{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques}",
         doi = "10.1007/11830924_3; 10.1007/11830924_3",
         editor = "Díaz, Josep and Jansen, Klaus and Rolim, José and Zwick, Uri",
         file = "Full Paper Springer:/home/phoenixx/Studium/MasterThesis/mastercola/papers/AEMN06\_constant\_factor\_dom\_sets\_udg.pdf:PDF",
         owner = "phoenixx",
         pages = "3–14",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         timestamp = "2010.09.03",
         title = "{Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs}",
         url = "http://www.springerlink.com/content/h68246294j8pr8p3",
         volume = "4110",
         year = "2006"
 }
 
 @inproceedings{ASY05_formation_problems,
         author = "Ando, H. and Suzuki, Ichiro and Yamashita, Masafumi",
         doi = "10.1109/ISIC.1995.525098",
         journal = "Intelligent Control, 1995., Proceedings of the 1995 IEEE International Symposium on",
         keywords = "agreement problems; correctness proofs; formation problems; limited visibility; mobile processor; synchronous mobile robots; distributed control; graph theory; mobile robots; path planning",
         month = "August",
         owner = "phoenixx",
         pages = "453–460",
         timestamp = "2010.10.09",
         title = "{Formation and agreement problems for synchronous mobile robots with limited visibility}",
         year = "1995"
 }
 
 @article{BMP05_performance_compare_protocols_for_clustering_and_backbone_ad_hoc_nets,
         abstract = {This paper concerns the comparative performance evaluation of protocols for clustering and backbone formation in ad hoc networks characterized by a large number of resource-constrained nodes. Our aim is twofold: we provide the first simulation-based detailed investigation of techniques for clustering and backbone formation that are among the most representative of this area of ad hoc research. Second, we delve into the nature of the selected protocols to assess the effects of the "degree of localization" on their operations, i.e., how being able to execute the protocol based only on local information affects the overall protocol performance. Extensive ns2-based simulation results show that highly localized protocols are rewarded with good performance with respect to all metrics of interest which include protocol duration, energy consumption, message overhead, route length, and backbone size.},
         author = "Basagni, S. and Mastrogiovanni, M. and Panconesi, A. and Petrioli, C.",
         doi = "10.1109/TPDS.2006.52",
         file = "Full Article (IEEE):/home/phoenixx/Studium/MasterThesis/mastercola/papers/BMP06\_performance\_compare\_protocols\_for\_clustering\_and\_backbone\_ad\_hoc\_nets.pdf:PDF",
         issn = "1045-9219",
         journal = "Parallel and Distributed Systems, IEEE Transactions on",
         keywords = "ad hoc clustering; ad hoc networks; backbone formation; localized protocols; ns2-based simulation; performance evaluation; resource-constrained nodes; ad hoc networks; performance evaluation; protocols; workstation clusters",
         month = "April",
         number = "4",
         owner = "phoenixx",
         pages = "292–306",
         timestamp = "2010.10.11",
         title = "{Localized protocols for ad hoc clustering and backbone formation: a performance comparison}",
         volume = "17",
         year = "2006"
 }
 
 @inproceedings{BEKLPR09_SINR_diagrams,
         abstract = "The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference \& noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard. SINR diagrams appear to be fundamental to understanding the behavior of wireless networks, and may play a key role in the development of suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams in the study of proximity queries and related issues in computational geometry. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified graph-based models such as the unit disk graph (UDG) model, which conveniently abstract away interference-related complications, and make it easier to handle algorithmic issues, but consequently fail to capture accurately some important aspects of wireless networks. The current paper focuses on obtaining some basic understanding of SINR diagrams, their properties and their usability in algorithmic applications. Specifically, based on some algebraic properties of the polynomials defining the reception zones we show that assuming uniform power transmissions, the reception zones are convex and relatively well-rounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks.",
         author = "Ben, Chen Avin and Emek, Yuval and Kantor, Erez and Lotker, Zvi and Peleg, David and Roditty, Liam",
         booktitle = "{Annual ACM Symposium on Principles of Distributed Computing Proceedings of the 28th ACM symposium on Principles of distributed computing}",
         doi = "10.1145/1582716.1582750",
         file = "Full Paper:/home/phoenixx/Studium/MasterThesis/mastercola/papers/p200-avin.pdf:PDF",
         owner = "phoenixx",
         pages = "200–209",
         publisher = "ACM New York, NY, USA",
         review = "Bastian meinte, dass ich mir hier die Modellierungen für unebene Gelände anschauen sollte.",
         timestamp = "2010.04.19",
         title = "{SINR diagrams: towards algorithmically usable SINR models of wireless networks}",
         year = "2009"
 }
 
 @inproceedings{BBKS00_mobility_facility_location,
         address = "New York, NY, USA",
         author = "Bespamyatnikh, S. and Bhattacharya, B. and Kirkpatrick, D. and Segal, M.",
         booktitle = "{DIALM '00: Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications}",
         doi = "10.1145/345848.345858",
         file = "Full Article (ACM Portal):/home/phoenixx/Studium/MasterThesis/mastercola/papers/BBKM00\_mobilr\_facility\_location.pdf:PDF",
         isbn = "1-58113-301-4",
         location = "Boston, Massachusetts, United States",
         owner = "phoenixx",
         pages = "46–53",
         publisher = "ACM",
         timestamp = "2010.10.05",
         title = "{Mobile facility location (extended abstract)}",
         year = "2000"
 }
 
 @inproceedings{BT10_parallel_approx_algos_for_flp,
         __markedentry = "[phoenixx]",
         address = "New York, NY, USA",
         author = "Blelloch, Guy E. and Tangwongsan, Kanat",
         booktitle = "{SPAA '10: Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures}",
         doi = "10.1145/1810479.1810535",
         isbn = "978-1-4503-0079-7",
         localfile = "archive/BT10_parallel_approx_algos_for_flp.pdf",
         location = "Thira, Santorini, Greece",
         owner = "phoenixx",
         pages = "315–324",
         publisher = "ACM",
         timestamp = "2010.10.13",
         title = "{Parallel approximation algorithms for facility-location problems}",
         year = "2010"
 }
 
 @incollection{BCIS05_facility_location_sublinear_time,
         abstract = "In this paper we present a randomized constant factor approximation algorithm for the problem of computing the optimal cost of the metric Minimum Facility Location problem, in the case of uniform costs and uniform demands, and in which every point can open a facility. By exploiting the fact that we are approximating the optimal cost without computing an actual solution, we give the first algorithm for this problem with running time O(n log2n), where n is the number of metric space points. Since the size of the representation of an n-point metric space is Θ(n2), the complexity of our algorithm is sublinear with respect to the input size. We consider also the general version of the metric Minimum Facility Location problem and we show that there is no o(n2)-time algorithm, even a randomized one, that approximates the optimal solution to within any factor. This result can be generalized to some related problems, and in particular, the cost of minimum-cost matching, the cost of bi-chromatic matching, or the cost of n/2-median cannot be approximated in o(n2)-time.",
         author = "Bădoiu, Mihai and Czumaj, Artur and Indyk, Piotr and Sohler, Christian",
         booktitle = "{Automata, Languages and Programming}",
         doi = "10.1007/11523468",
         editor = "et al., L. Caires",
         file = "Full Chapter:/home/phoenixx/Studium/MasterThesis/mastercola/papers/BCIS05\_facility\_location\_sublinear\_time.pdf:PDF",
         note = "ISSN 0302-9743 (Print) 1611-3349 (Online) ISBN 978-3-540-27580-0",
         owner = "phoenixx",
         pages = "866–877",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         timestamp = "2010.03.06",
         title = "{Facility Location in Sublinear Time}",
         url = "http://www.springerlink.com/content/22qfq41ftupd0wd6",
         volume = "3580/2005",
         year = "2005"
 }
 
 @incollection{C98_improved_approximation_algorithms_for_uncap_flp,
         abstract = "We consider the uncapacitated facility location problem. In this problem, there is a set of locations at which facilities can be built; a fixed cost f i is incurred if a facility is opened at location i. Further- more, there is a set of demand locations to be serviced by the opened facilities; if the demand location j is assigned to a facility at location i, then there is an associated service cost of cij. The objective is to de- termine which facilities to open and an assignment of demand points to the opened facilities, so as to minimize the total cost. We assume that the service costs c ij are symmetric and satisfy the triangle inequality. For this problem we obtain a (1 + 2/e)-approximation algorithm, where 1 + 2/e ≈ 1.736, which is a significant improvement on the previously known approximation guarantees. The algorithm works by rounding an optimal fractional solution to a linear programming relaxation. Our techniques use properties of opti- mal solutions to the linear program, randomized rounding, as well as a generalization of the decomposition techniques of Shmoys, Tardos, and Aardal.",
         affiliation = "Cornell University School of Operations Research \& Industrial Engineering Ithaca NY 14853 USA",
         author = "Chudak, Fabián",
         booktitle = "{Integer Programming and Combinatorial Optimization}",
         editor = "Bixby, Robert and Boyd, E. and Ríos-Mercado, Roger",
         owner = "phoenixx",
         pages = "180–194",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         timestamp = "2010.10.12",
         title = "{Improved Approximation Algorithms for Uncapacitated Facility Location}",
         url = "http://dx.doi.org/10.1007/3-540-69346-7_14",
         volume = "1412",
         year = "1998"
 }
 
 @incollection{CS99_improved_approximation_algorithms_for_cap_flp,
         address = "Baltimore, Md.",
         affiliation = "Cornell University School of Operations Research \& Industrial Engineering Ithaca NY 14853 USA",
         author = "Chudak, Fabián and Shmoys, David B.",
         booktitle = "{Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms}",
         month = "Jan. 17–19",
         owner = "phoenixx",
         pages = "875–876",
         publisher = "ACM New York, NY, USA",
         timestamp = "2010.10.12",
         title = "{Improved Approximation Algorithms for the Capacitated Facility Location}",
         year = "1999"
 }
 
 @incollection{CFPS03_solving_robots_gathering_problem,
         abstract = "Consider a set of n \> 2 simple autonomous mobile robots (decentralized, asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, deterministic) moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of gathering them at a point not fixed in advance (Gathering Problem). In the literature, most contributions are simulation-validated heuristics. The existing algorithmic contributions for such robots are limited to solutions for n ≤ 4 or for restricted sets of initial configurations of the robots. In this paper, we present the first algorithm that solves the Gathering Problem for any initial configuration of the robots.",
         affiliation = "ETH Zurich Zurich",
         author = "Cieliebak, Mark and Flocchini, Paola and Prencipe, Giuseppe and Santoro, Nicola",
         booktitle = "{Automata, Languages and Programming}",
         editor = "Baeten, Jos and Lenstra, Jan and Parrow, Joachim and Woeginger, Gerhard",
         file = "Springer Article:/home/phoenixx/Studium/MasterThesis/mastercola/papers/CFPS03\_solving\_robots\_gathering\_problem.pdf:PDF",
         owner = "phoenixx",
         pages = "1181–1196",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         timestamp = "2010.08.22",
         title = "{Solving the Robots Gathering Problem}",
         url = "http://dx.doi.org/10.1007/3-540-45061-0_90",
         volume = "2719",
         year = "2003"
 }
 
 @article{CCJ90_udg,
         abstract = "Unit disk graphs are the intersection graphs of equal sized circles in the plane: they provide a graph-theoretic model for broadcast networks (cellular networks) and for some problems in computational geometry. We show that many standard graph theoretic problems remain NP-complete on unit disk graphs, including coloring, independent set, domination, independent domination, and connected domination; NP-completeness for the domination problem is shown to hold even for grid graphs, a subclass of unit disk graphs. In contrast, we give a polynomial time algorithm for finding cliques when the geometric representation (circles in the plane) is provided.",
         author = "Clark, Brent N. and Colbourn, Charles J. and Johnson, David S.",
         doi = "10.1016/0012-365X(90)90358-O",
         file = "/home/phoenixx/Studium/MasterThesis/mastercola/papers/CCJ90\_udg.pdf",
         issn = "0012-365X",
         journal = "Discrete Mathematics",
         localfile = "/home/phoenixx/Studium/MasterThesis/mastercola/papers/CCJ90_udg.pdf",
         number = "1–3",
         owner = "phoenixx",
         pages = "165–177",
         timestamp = "2010.09.04",
         title = "{Unit disk graphs}",
         url = "http://www.sciencedirect.com/science/article/B6V00-45GN4W9-K/2/1ac54dd6410c091d3594a2282aa4c7d3",
         volume = "86",
         year = "1990"
 }
 
 @article{COG05_journal,
         author = "Cohen, Reuven and Peleg, David",
         doi = "10.1137/S0097539704446475",
         journal = "SIAM Journal on Computing",
         keywords = "robot swarms; autonomous mobile robots; convergence",
         number = "6",
         owner = "phoenixx",
         pages = "1516–1528",
         publisher = "SIAM",
         review = "Cohen/Peleg Journal Version, beides, zudem asynchrones UMmin (Konvergenz + Konvergenzgeschwindigkeit)",
         timestamp = "2010.08.22",
         title = "{Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems}",
         url = "http://link.aip.org/link/?SMJ/34/1516/1",
         volume = "34",
         year = "2005"
 }
 
 @incollection{CGP06_gathering_few_fat_robots,
         abstract = "Autonomous identical robots represented by unit discs move deterministically in the plane. They do not have any common coordinate system, do not communicate, do not have memory of the past and are totally asynchronous. Gathering such robots means forming a configuration for which the union of all discs representing them is connected. We solve the gathering problem for at most four robots. This is the first algorithmic result on gathering robots represented by two-dimensional figures rather than points in the plain: we call such robots fat.",
         affiliation = "Département d’informatique, Université du Québec en Outaouais, Gatineau, Québec J8X 3X7 Canada Canada",
         author = "Czyzowicz, Jurek and Gasieniec, Leszek and Pelc, Andrzej",
         booktitle = "{Principles of Distributed Systems}",
         editor = "Shvartsman, Alexander",
         owner = "phoenixx",
         pages = "350–364",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         timestamp = "2010.10.08",
         title = "{Gathering Few Fat Mobile Robots in the Plane}",
         url = "http://dx.doi.org/10.1007/11945529_25",
         volume = "4305",
         year = "2006"
 }
 
 @article{DGL10_Kinetic-Facility-Location,
         abstract = "We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the accumulated cost for the whole point set is at most a constant factor larger than the optimal cost. In our scenario, each point can change its status between client and facility and moves continuously along a known trajectory in a d-dimensional Euclidean space, where d is a constant. Our kinetic data structure requires $\mathcal{O}(n(\log^{d}(n)+\log (nR)))$ space in total, where $R:=\frac{\max_{p_{i}\in\mathcal{P}}\{f_{i}}\cdot\max_{\p_{i}\in\mathcal{\P\}\}\{\d_{i}}\}{min_{\p_{i}\in\mathcal\ \ {P\}}\{\f_{i}}\cdot\min_{\p_{i}\in\mathcal{\P\}}\{\d_{i}}}$ , ℘={p 1,p 2,…,p n } is the set of given points, and f i , d i are the maintenance cost and the demand of a point p i , respectively. In case that each trajectory can be described by a bounded degree polynomial, we process $\mathcal{O}(n^{2}\log^{2}(nR))$ events, each requiring $\mathcal{O}(\log^{d+1}(n)\cdot\log(nR))$ time and $\mathcal {O}(\log(nR))$ status changes.",
         address = "Secaucus, NJ, USA",
         author = "Degener, Bastian and Gehweiler, Joachim and Lammersen, Christiane",
         doi = "10.1007/s00453-008-9250-7",
         file = "Journal Article:/home/phoenixx/Studium/MasterThesis/DGL08\_Kinetic-Facility-Location.pdf:PDF",
         journal = "Algorithmica",
         keywords = "facility location; kinetic data structure; approximation algorithm; deterministic algorithm",
         month = "July",
         number = "3",
         owner = "phoenixx",
         pages = "562–584",
         publisher = "Springer-Verlag New York, Inc.",
         timestamp = "2010.03.02",
         title = "{Kinetic Facility Location}",
         url = "http://www.springerlink.com/content/341q657424x70uq2",
         volume = "57",
         year = "2010"
 }
 
 @inproceedings{DGL08_Kinetic-Facility-Location,
         abstract = "We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the accumulated cost for the whole point set is at most a constant factor larger than the optimal cost. In our scenario, each point can change its status between client and facility and moves continuously along a known trajectory in a d-dimensional Euclidean space, where d is a constant. Our kinetic data structure requires $\mathcal{O}(n(\log^{d}(n)+\log (nR)))$ space in total, where $R:=\frac{\max_{p_{i}\in\mathcal{P}}\{f_{i}}\cdot\max_{\p_{i}\in\mathcal{\P\}}\{\d_{i}}\}{\min_{\p_{i}\in\mathcal{P}}\{\f_{i}}\cdot\min_{\p_{i}\in\mathcal{\P\}}\{\d_{i}}}$ , ℘={p 1,p 2,…,p n } is the set of given points, and f i , d i are the maintenance cost and the demand of a point p i , respectively. In case that each trajectory can be described by a bounded degree polynomial, we process $\mathcal{O}(n^{2}\log^{2}(nR))$ events, each requiring $\mathcal{O}(\log^{d+1}(n)\cdot\log(nR))$ time and $\mathcal {O}(\log(nR))$ status changes.",
         address = "Berlin, Heidelberg",
         author = "Degener, Bastian and Gehweiler, Joachim and Lammersen, Christiane",
         booktitle = "{SWAT '08: Proceedings of the 11th Scandinavian workshop on Algorithm Theory}",
         doi = "10.1007/978-3-540-69903-3_34",
         file = "Journal Article:/home/phoenixx/Studium/MasterThesis/DGL08\_Kinetic-Facility-Location.pdf:PDF",
         journal = "Algorithmica",
         keywords = "facility location; kinetic data structure; Approximation algorithm; Deterministic algorithm",
         owner = "phoenixx",
         pages = "378–389",
         publisher = "Springer-Verlag",
         timestamp = "2010.03.02",
         title = "{The Kinetic Facility Location}",
         year = "2008"
 }
 
 @inproceedings{DKM10_local_o2_gathering,
         abstract = "The gathering problem, where $n$ autonomous robots with restricted capabilities are required to meet in a single point of the plane, is widely studied. We consider the case that robots are limited to see only robots within a bounded vicinity and present an algorithm achieving gathering in O(n2) rounds in expectation. A round consists of a movement of all robots, in random order. All previous algorithms with a proven time bound assume global view on the configuration of all robots.",
         address = "New York, NY, USA",
         author = "Degener, Bastian and Kempkes, Barbara and {Meyer auf der Heide}, Friedhelm",
         booktitle = "{SPAA '10: Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures}",
         doi = "10.1145/1810479.1810523",
         file = "Full Article ACM Portal:/home/phoenixx/Studium/MasterThesis/mastercola/papers/DKM10_local_n2_gathering_algo.pdf:PDF",
         isbn = "978-1-4503-0079-7",
         location = "Thira, Santorini, Greece",
         pages = "217–223",
         publisher = "ACM",
         review = "Round model is same as DKP10",
         title = "{A local O($n^2$) gathering algorithm}",
         url = "http://portal.acm.org/citation.cfm?id=1810479.1810523",
         year = "2010"
 }
 
 @inproceedings{FR07_distr_flp_for_flex_wlansensors,
         abstract = "Many self-configuration problems that occur in sensor networks, such as clustering or operator placement for in-network data aggregation, can be modeled as facility location problems. Unfortunately, existing distributed facility location algorithms are hardly applicable to multi-hop sensor networks. Based on an existing centralized algorithm, we therefore devise equivalent distributed versions which, to our knowledge, represent the first distributed approximations of the facility location problem that can be practicably implemented in multihop sensor networks with local communication. Through simulation studies, we demonstrate that, for typical instances derived from sensor-network configuration problems, the algorithms terminate in only few communication rounds, the runtime does not increase with the network size, and, finally, that our implementation requires only local communication confined to small network neighborhoods. In addition, we propose simple extensions to our algorithms to support dynamic networks with varying link qualities and node additions and deletions. Using link quality traces collected from a real sensor network deployment, we demonstrate the effectiveness of our algorithms in realistic multi-hop sensor networks.",
         address = "Berlin, Heidelberg",
         author = "Frank, Christian and Römer, Kay",
         booktitle = "{DCOSS'07: Proceedings of the 3rd IEEE international conference on Distributed computing in sensor systems}",
         file = "Full Paper ACM Portal:/home/phoenixx/Studium/MasterThesis/mastercola/papers/FR07_distr_flp_for_flex_wlansensors.pdf:PDF",
         isbn = "978-3-540-73089-7",
         location = "Santa Fe, NM, USA",
         owner = "phoenixx",
         pages = "124–141",
         publisher = "Springer-Verlag",
         timestamp = "2010.09.02",
         title = "{Distributed facility location algorithms for flexible configuration of wireless sensor networks}",
         url = "http://portal.acm.org/citation.cfm?id=1769096",
         year = "2007"
 }
 
 @inproceedings{GLS06-distr-approx-uniform-location,
         abstract = "In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.",
         address = "New York, NY, USA",
         author = "Gehweiler, Joachim and Lammersen, Christiane and Sohler, Christian",
         booktitle = "{SPAA '06: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures}",
         doi = "10.1145/1148109.1148152",
         file = "Conference Paper:/home/phoenixx/Studium/MasterThesis/GLS06\_distributed_algo_facility_location_problem.pdf:PDF",
         journal = "Electronic Notes in Discrete Matehamatics",
         keywords = "facility location; distribued approximation; randomized algorithm",
         owner = "phoenixx",
         pages = "237–243",
         publisher = "ACM",
         review = "* Bounded message size to log(n) * 3 communication rounds * only uniform facility location problem * also for powers of metrics",
         timestamp = "2010.02.28",
         title = "{A distributed O(1)-approximation algorithm for the uniform facility location problem}",
         url = "http://portal.acm.org/citation.cfm?id=1148109.1148152",
         volume = "25",
         year = "2006"
 }
 
 @inproceedings{GK98_greedy_strikes_back,
         address = "Philadelphia, PA, USA",
         author = "Guha, Sudipto and Khuller, Samir",
         booktitle = "{SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms}",
         file = "Full Text:/home/phoenixx/Studium/MasterThesis/mastercola/papers/p649-guha\_greedy_strikes_back.pdf:PDF",
         owner = "phoenixx",
         pages = "649–657",
         publisher = "Society for Industrial and Applied Mathematics",
         timestamp = "2010.04.28",
         title = "{Greedy strikes back: improved facility location algorithms}",
         url = "http://portal.acm.org/citation.cfm?id=314613.315037&coll=portal&dl=ACM&type=series&idx=SERIES422&part=series&WantType=Proceedings&title=SODA&CFID=86304211&CFTOKEN=72612016",
         year = "1998"
 }
 
 @article{HBF08_kinetic_mobility_mgmt_ad_hoc_nets,
         abstract = "Vehicular Ad Hoc Networks (VANETs) are a particular category of mobile ad hoc networks (MANETs) characterized by a high mobility and a reduced connectivity. In order to develop protocols for vehicular networks, the community may either create VANET specific approaches, or adapt already existing protocols to VANET. While the former may provide efficient specialized solutions, the latter offers an increased interoperability and universality, which is a key issue for industrial partners involved in the deployment of VANET and Intelligent Transportation Systems (ITS). An important aspect in the porting of ad hoc networks solutions to VANET and ITS is an efficient management of vehicular mobility. Mobility Management is a principle aimed at updating network routes or structures in order to keep them coherent with mobile topologies. Mobility management may be proactive or reactive, depending if the updates are triggered with or without topology changes, or if and only if a change in the topology effectively requires to update the structure. Failure to develop efficient mobility management heuristics leads to a waste of network resources and suboptimal routes or structures. The optimal solution is obviously the reactive mobility management, as updates are optimally triggered only when necessary. However, due to its complexity, the reactive mobility management has not attracted as much attention as its proactive counterpart. In this paper, we introduce a location-aware framework, called Kinetic Graphs, that may be followed by ad hoc protocols in order to implement a reactive mobility management. The Kinetic Graph framework is able to capture the dynamics of mobile structures, and is composed of four steps: (i) a representation of the trajectories, (ii) a common message format for the posting of these trajectories, (iii) a time varying weight for building the kinetic structures, (iv) an aperiodic neighborhood maintenance. We eventually provide a example of a successful application of this framework to broadcasting and routing in VANET.",
         author = "Härri, Jérôme and Bonnet, Christian and Filali, Fethi",
         doi = "10.1016/j.comcom.2008.01.060",
         file = "Full Paper:/home/phoenixx/Studium/MasterThesis/mastercola/papers/HBF08\_kinetic_mobility_management_on_ad_hoc_nets.pdf:PDF",
         issn = "0140-3664",
         journal = "Computer Communications",
         keywords = "Reactive mobility management",
         note = "Mobility Protocols for ITS/VANET",
         number = "12",
         pages = "2907–2924",
         title = "{Kinetic mobility management applied to vehicular ad hoc network protocols}",
         url = "http://www.sciencedirect.com/science/article/B6TYP-4RSYC9K-1/2/6184d66ad7a0e5537a92b86973455d55",
         volume = "31",
         year = "2008"
 }
 
 @article{03jmmav_greedy_flp_using_duals,
         abstract = "In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O(m log m) and O(n3), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.",
         author = "Jain, Kamal and Mahdian, Mohammad and Markakis, Evangelos and Saberi, Amin and Vazirani, Vijay V.",
         doi = "10.1145/950620.950621",
         file = "Full Article:/home/phoenixx/Studium/MasterThesis/mastercola/papers/03jmms_greedy_p795-jain.pdf:PDF",
         journal = "Journal of the ACM (JACM)",
         month = "November",
         note = "ISSN:0004-5411",
         number = "6",
         owner = "phoenixx",
         pages = "795–824",
         timestamp = "2010.07.21",
         title = "{Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP}",
         url = "http://portal.acm.org/citation.cfm?id=950621",
         volume = "50",
         year = "2003"
 }
 
 @article{JMMSV03_greedy_flp_using_dual_fitting_with_factor-revealing_lp,
         address = "New York, NY, USA",
         author = "Jain, Kamal and Mahdian, Mohammad and Markakis, Evangelos and Saberi, Amin and Vazirani, Vijay V.",
         doi = "10.1145/950620.950621",
         file = "Full Article (Portal ACM):/home/phoenixx/Studium/MasterThesis/mastercola/papers/JMMSV03_greedy_flp_using_dual_fitting_with_factor-revealing_lp.pdf:PDF",
         issn = "0004-5411",
         journal = "Journal of the ACM (JACM)",
         number = "6",
         owner = "phoenixx",
         pages = "795–824",
         publisher = "ACM",
         timestamp = "2010.10.13",
         title = "{Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP}",
         volume = "50",
         year = "2003"
 }
 
 @article{JV01_primal_dual_metric_flp,
         abstract = "We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m logm) and O(m logm(L + log (n))) respectively, where n and m are the total number of vertices and edges in the underlying complete bipartite graph on cities and facilities. The main algorithmic ideas are a new extension of the primal-dual schema and the use of Lagrangian relaxation to derive approximation algorithms.",
         author = "Jain, Kamal and Vazirani, Vijay V.",
         comment = "ISSN:0004-5411",
         doi = "10.1145/375827.375845",
         file = "Journal Version of Jain and Vazirani Paper:/home/phoenixx/Studium/MasterThesis/mastercola/papers/JV01\_journal.pdf:PDF",
         journal = "Journal of the ACM (JACM)",
         owner = "phoenixx",
         pages = "274–296",
         timestamp = "2010.07.10",
         title = "{Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation}",
         url = "http://portal.acm.org/citation.cfm?id=375827.375845",
         volume = "48",
         year = "2001"
 }
 
 @book{KW05_sensor_networks,
         author = "Karl, Holger and Willig, Andreas",
         owner = "phoenixx",
         publisher = "Wiley",
         timestamp = "2010.10.11",
         title = "{Protocols and Architectures for Wireless Sensor Networks}",
         year = "2007"
 }
 
 @article{KPR98_microeconomic_view_of_datamining,
         abstract = "We present a rigorous framework, based on optimization, for evaluating data mining operations such as associations and clustering, in terms of their utility in decision-making. This framework leads quickly to some interesting computational problems related to sensitivity analysis, segmentation and the theory of games.",
         author = "Kleinberg, Jon and Papadimitriou, Christos and Raghavan, Prabhakar",
         issn = "1384-5810",
         journal = "Data Mining and Knowledge Discovery",
         keyword = "Computer Science",
         note = "10.1023/A:1009726428407",
         number = "4",
         owner = "phoenixx",
         pages = "311–324",
         publisher = "Springer Netherlands",
         timestamp = "2010.10.04",
         title = "{A Microeconomic View of Data Mining}",
         url = "http://dx.doi.org/10.1023/A:1009726428407",
         volume = "2",
         year = "1998"
 }
 
 @article{KH63_heuristic_program_for_locating_warehouses,
         abstract = "The linear programing algorithms available for optimizing the routing of shipments in multi-plant, multi-destination systems cannot, in the current state of knowledge, be applied directly to the more general problem of determining the number and location of regional warehouses in large-scale distribution networks. This paper outlines a heuristic computer program for locating warehouses and compares it with recently published efforts at solving the problem either by means of simulation or as a variant of linear programing. The heuristic approach outlined in this paper appears to offer significant advantages in the solution of this class of problems in that it (1) provides considerable flexibility in the specification (modeling) of the problem to be solved, (2) can be used to study large-scale problems, that is, complexes with several hundred potential warehouse sites and several thousand shipment destinations, and (3) is economical of computer time. The results obtained in applying the program to small scale problems have been equal to or better than those provided by the alternative methods considered.",
         author = "Kuehn, Alfred A. and Hamburger, Michael J.",
         copyright = "Copyright © 1963 INFORMS",
         issn = "00251909",
         journal = "Management Science",
         jstor_articletype = "research-article",
         jstor_formatteddate = "Jul., 1963",
         language = "English",
         number = "4",
         owner = "phoenixx",
         pages = "643–666",
         publisher = "INFORMS",
         timestamp = "2010.10.12",
         title = "{A Heuristic Program for Locating Warehouses}",
         url = "http://www.jstor.org/stable/2627368",
         volume = "9",
         year = "1963"
 }
 
 @inproceedings{KWZ03_ad-hoc_networks_beyond_unit-disk-graphs,
         abstract = "In this paper we study a model for ad-hoc networks close enough to reality as to represent existing networks, being at the same time concise enough to promote strong theoretical results. The Quasi Unit Disk Graph model contains all edges shorter than a parameter d between 0 and 1 and no edges longer than 1.We show that .in comparison to the cost known on Unit Disk Graphs .the complexity results in this model contain the additional factor 1 /d2. We prove that in Quasi Unit Disk Graphs flooding is an asymptotically message-optimal routing technique, provide a geometric routing algorithm being more efficient above all in dense networks, and show that classic geometric routing is possible with the same performance guarantees as for Unit Disk Graphs if d = 1/v2.",
         address = "New York, NY, USA",
         author = "Kuhn, Fabian and Wattenhofer, Roger and Zollinger, Aaron",
         booktitle = "{DIALM-POMC '03: Proceedings of the 2003 joint workshop on Foundations of mobile computing}",
         doi = "10.1145/941079.941089",
         isbn = "1-58113-765-6",
         location = "San Diego, CA, USA",
         pages = "69–78",
         publisher = "ACM",
         review = "This is the initial work on quasi-UDGs.",
         title = "{Ad-hoc networks beyond unit disk graphs}",
         url = "http://portal.acm.org/citation.cfm?id=941089&dl=GUIDE,&coll=GUIDE&CFID=100300923&CFTOKEN=55730014",
         year = "2003"
 }
 
 @article{MFHH02_tiny_aggregation_service_for_ad-hoc_nets,
         abstract = "We present the Tiny AGgregation (TAG) service for aggregation in low-power, distributed, wireless environments. TAG allows users to express simple, declarative queries and have them distributed and executed efficiently in networks of low-power, wireless sensors. We discuss various generic properties of aggregates, and show how those properties affect the performance of our in network approach. We include a performance study demonstrating the advantages of our approach over traditional centralized, out-of-network methods, and discuss a variety of optimizations for improving the performance and fault tolerance of the basic solution.",
         address = "New York, NY, USA",
         author = "Madden, Samuel and Franklin, Michael J. and Hellerstein, Joseph M. and Hong, Wei",
         doi = "10.1145/844128.844142",
         issn = "0163-5980",
         journal = "SIGOPS Oper. Syst. Rev.",
         number = "SI",
         owner = "phoenixx",
         pages = "131–146",
         publisher = "ACM",
         timestamp = "2010.10.11",
         title = "{TAG: a Tiny AGgregation service for ad-hoc sensor networks}",
         volume = "36",
         year = "2002"
 }
 
 @inproceedings{MP00_online_median_problem,
         abstract = "We introduce a natural variant of the (metric uncapacitated) k-median problem that we call the online median problem. Whereas the k-median problem involves optimizing the simultaneous placement of k facilities, the on-line median problem imposes the following additional constraints: the facilities are placed one at a time; a facility cannot be moved once it is placed, and the total number of facilities to be placed, k, is not known in advance. The objective of an online median algorithm is to minimize the competitive ratio, that is, the worst-case ratio of the cost of an online placement to that of an optimal offline placement. Our main result is a linear-time constant-competitive algorithm for the online median problem. In addition, we present a related, though substantially simpler linear-time constant-factor approximation algorithm for the (metric uncapacitated) facility location problem. The latter algorithm is similar in spirit to the recent primal-dual-based facility location algorithm of Jain and Vazirani, but our approach is more elementary and yields an improved running time.",
         address = "Washington, DC, USA",
         author = "Mettu, Ramgopal R. and Plaxton, C. Greg",
         booktitle = "{Proceedings of the 41st Annual Symposium on Foundations of Computer Science}",
         citeseerurl = "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.128.4386",
         comment = "ISBN: 0-7695-0850-2",
         doi = "10.1109/SFCS.2000.892122",
         keywords = "approximation theory; competitive ratio; facility location; heuristic programming; k-median problem; linear-time constant-competitive algorithm; linear-time constant-factor approximation algorithm; online median problem; primal-dual-based facility location algorithm; worst-case ratio",
         month = "November",
         organization = "FOCS",
         owner = "phoenixx",
         pages = "pp. 339",
         publisher = "IEEE Computer Society",
         timestamp = "2010.03.08",
         title = "{The Online Median Problem}",
         url = "http://www.computer.org/portal/web/csdl/abs/proceedings/focs/2000/0850/00/08500339abs.htm",
         year = "2000"
 }
 
 @inproceedings{PP09_finding_facilities_fast,
         abstract = "Clustering can play a critical role in increasing the performance and lifetime of wireless networks. The facility location problem is a general abstraction of the clustering problem and this paper presents the first constant-factor approximation algorithm for the facility location problem on unit disk graphs (UDGs), a commonly used model for wireless networks. In this version of the problem, connection costs are not metric, i.e., they do not satisfy the triangle inequality, because connecting to a non-neighbor costs ¿. In non-metric settings the best approximation algorithms guarantee an O(logn)-factor approximation, but we are able to use structural properties of UDGs to obtain a constant-factor approximation. Our approach combines ideas from the primal-dual algorithm for facility location due to Jain and Vazirani (JACM, 2001) with recent results on the weighted minimum dominating set problem for UDGs (Huang et al., J. Comb. Opt., 2008). We then show that the facility location problem on UDGs is inherently local and one can solve local subproblems independently and combine the solutions in a simple way to obtain a good solution to the overall problem. This leads to a distributed version of our algorithm in the $\mathcal{LOCAL}$ model that runs in constant rounds and still yields a constant-factor approximation. Even if the UDG is specified without geometry, we are able to combine recent results on maximal independent sets and clique partitioning of UDGs, to obtain an O(logn)-approximation that runs in O(log* n) rounds.",
         address = "Berlin, Heidelberg",
         author = "Pandit, Saurav and Pemmaraju, Sriram V.",
         booktitle = "{ICDCN '09: Proceedings of the 10th International Conference on Distributed Computing and Networking}",
         doi = "10.1007/978-3-540-92295-7_5",
         isbn = "978-3-540-92294-0",
         location = "Hyderabad, India",
         pages = "11–24",
         publisher = "Springer-Verlag",
         series = "{Lecture Notes in Computer Science}",
         title = "{Finding Facilities Fast}",
         url = "http://www.springerlink.com/content/c2237kh3v339g77w",
         volume = "5408",
         year = "2009"
 }
 
 @book{P00_book_distributed_computing,
         address = "Philadelphia",
         author = "Peleg, David",
         editor = "Hammer, Peter L.",
         owner = "phoenixx",
         publisher = "Society for Industrial and Applied Mathematics (SIAM)",
         series = "{SIAM Monographs on Discrete Mathematics and Applications}",
         timestamp = "2010.10.13",
         title = "{Distributed Computing: A Locality-Sensitive Approach}",
         year = "2000"
 }
 
 @inproceedings{STA97_approx_algorithms_for_flp,
         address = "New York, NY, USA",
         author = "Shmoys, David B. and Tardos, Éva and Aardal, Karen",
         booktitle = "{STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing}",
         doi = "10.1145/258533.258600",
         isbn = "0-89791-888-6",
         location = "El Paso, Texas, United States",
         owner = "phoenixx",
         pages = "265–274",
         publisher = "ACM",
         timestamp = "2010.10.12",
         title = "{Approximation algorithms for facility location problems (extended abstract)}",
         year = "1997"
 }
 
 @article{S63_working_model_for_plant_numbers_and_locations,
         author = "Stollsteimer, John F.",
         copyright = "Copyright © 1963 Agricultural \& Applied Economics Association",
         issn = "10711031",
         journal = "Journal of Farm Economics",
         jstor_articletype = "research-article",
         jstor_formatteddate = "Aug., 1963",
         language = "English",
         number = "3",
         owner = "phoenixx",
         pages = "631–645",
         publisher = "Blackwell Publishing on behalf of the Agricultural \& Applied Economics Association",
         timestamp = "2010.10.12",
         title = "{A Working Model for Plant Numbers and Locations}",
         url = "http://www.jstor.org/stable/1235442",
         volume = "45",
         year = "1963"
 }
 
 @article{SY99_distr_robots_geometric_patterns,
         abstract = "Consider a system of multiple mobile robots in which each robot, at infinitely many unpredictable time instants, observes the positions of all the robots and moves to a new position determined by the given algorithm. The robots are anonymous in the sense that they all execute the same algorithm and they cannot be distinguished by their appearances. Initially they do not have a common x-y coordinate system. Such a system can be viewed as a distributed system of anonymous mobile processes in which the processes (i.e., robots) can “communicate” with each other only by means of their moves. In this paper we investigate a number of formation problems of geometric patterns in the plane by the robots. Specifically, we present algorithms for converging the robots to a single point and moving the robots to a single point in finite steps. We also characterize the class of geometric patterns that the robots can form in terms of their initial configuration. Some impossibility results are also presented.",
         author = "Suzuki, Ichiro and Yamashita, Masafumi",
         doi = "10.1137/S009753979628292X",
         journal = "SIAM Journal on Computing",
         keywords = "distributed algorithms; anonymous robots; mobile robots; multiagent systems; formation of geometric patterns",
         number = "4",
         owner = "phoenixx",
         pages = "1347–1363",
         publisher = "SIAM",
         review = "This is probably the first definition of the FSYNC time model",
         timestamp = "2010.08.22",
         title = "{Distributed Anonymous Mobile Robots: Formation of Geometric Patterns}",
         url = "http://link.aip.org/link/?SMJ/28/1347/1",
         volume = "28",
         year = "1999"
 }
 
 @inproceedings{SY96_distr_formation_and_agreement_problem,
         address = "Waterloo, ON, Canada",
         author = "Suzuki, Ichiro and Yamashita, Masafumi",
         booktitle = "{Proceedings of the 3rd Annual Colloquium on Structural Information and Communication Complexity (SIROCCO '96)}",
         citeseerurl = "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.3191",
         organization = "Carleton Scientific",
         pages = "313–330",
         review = "Probably first annoucement of SSYNC model!",
         title = "{Distributed Anonymous Mobile Robots – Formation and Agreement Problems}",
         year = "1996"
 }
 
 @inproceedings{Y00_kmedians_flp_chernoff-wald_bound,
         address = "Philadelphia, PA, USA",
         author = "Young, Neal E.",
         booktitle = "{SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms}",
         file = "Full Text:/home/phoenixx/Studium/MasterThesis/mastercola/papers/p86-young.pdf:PDF",
         owner = "phoenixx",
         pages = "86–95",
         publisher = "Society for Industrial and Applied Mathematics",
         timestamp = "2010.04.28",
         title = "{K-medians, facility location, and the Chernoff-Wald bound}",
         url = "http://portal.acm.org/citation.cfm?id=338219.338239&coll=portal&dl=ACM&type=series&idx=SERIES422&part=series&WantType=Proceedings&title=SODA&CFID=86304211&CFTOKEN=72612016",
         year = "2000"
 }
 
 @article{Gon01_JXTA_network_programming_framework,
         added-at = "2010-04-06T16:41:10.000+0200",
         address = "Piscataway, NJ, USA",
         author = "Gong, Li",
         doi = "10.1109/4236.935182",
         interhash = "4fe36a0a4c007a8356fb9107dd5bc7e4",
         intrahash = "28e9d43bf0a7e7bae63091ea60cbaf64",
         issn = "1089-7801",
         journal = "IEEE Internet Computing",
         keywords = "imported",
         number = 3,
         pages = "88–95",
         publisher = "IEEE Educational Activities Department",
         title = "{JXTA: A Network Programming Environment}",
         url = "http://www.bibsonomy.org/bibtex/228e9d43bf0a7e7bae63091ea60cbaf64/chesteve",
         volume = 5,
         year = 2001
 }
 
 @inproceedings{EFKR09_online_computation_with_advance,
         abstract = "We consider a model for online computation in which the online algorithm receives, together with each request, some information regarding the future, referred to as advice. The advice provided to the online algorithm may allow an improvement in its performance, compared to the classical model of complete lack of information regarding the future. We are interested in the impact of such advice on the competitive ratio, and in particular, in the relation between the size b of the advice, measured in terms of bits of information per request, and the (improved) competitive ratio. Since b = 0 corresponds to the classical online model, and b = élog|A| ùb=log , where A is the algorithm’s action space, corresponds to the optimal (offline) one, our model spans a spectrum of settings ranging from classical online algorithms to offline ones. In this paper we propose the above model and illustrate its applicability by considering two of the most extensively studied online problems, namely, metrical task systems (MTS) and the k-server problem. For MTS we establish tight (up to constant factors) upper and lower bounds on the competitive ratio of deterministic and randomized online algorithms with advice for any choice of 1 ≤ b ≤ Θ(logn) , where n is the number of states in the system: we prove that any randomized online algorithm for MTS has competitive ratio Ω( log(n) / b) and we present a deterministic online algorithm for MTS with competitive ratio O (log(n) / b) . For the k-server problem we construct a deterministic online algorithm for general metric spaces with competitive ratio k O (1 / b) for any choice of Θ(1) ≤ b ≤ logk .",
         author = "Emek, Yuval and Fraigniaud, Pierre and Korman, Amos and Rosén, Adi",
         booktitle = "{Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP)}",
         doi = "10.1007/978-3-642-02927-1_36",
         issn = "0304-3975",
         journal = "Theoretical Computer Science",
         keywords = "Online; Competitive Analysis; k-Server Problem; Metrical Task System",
         number = "5555",
         pages = "427–438",
         publisher = "Springer",
         series = "{Lecture Notes in Computer Science}",
         title = "{Online computation with advice}",
         year = "2009"
 }
 
 @incollection{Sch07_principles_of_stochastic_local_search,
         abstract = "We set up a general generic framework for local search algorithms. Then we show in this generic setting how heuristic, problem-specific information can be used to improve the success probability of local search by focussing the search process on specific neighbor states. Our main contribution is a result which states that stochastic local search using restarts has a provable complexity advantage compared to deterministic local search. An important side aspect is the insight that restarting (starting the search process all over, not using any information computed before) is a useful concept which was mostly ignored before.",
         author = "Schöning, Uwe",
         booktitle = "{Unconventional Computation}",
         doi = "10.1007/978-3-540-73554-0_17",
         editor = "Akl, Selim and Calude, Cristian and Dinneen, Michael and Rozenberg, Grzegorz and Wareham, H.",
         institution = "Institute of Theoretical Computer Science, Ulm University, 89069 Ulm Germany",
         keywords = "local search; stochastic local search; heuristic information; restart; meta-algorithms",
         pages = "178–187",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         title = "{Principles of Stochastic Local Search}",
         volume = "4618",
         year = "2007"
 }
 
 @article{Jain:1999:DCR:331499.331504,
         abstract = "Clustering is the unsupervised classification of patterns (observations, data items, or feature vectors) into groups (clusters). The clustering problem has been addressed in many contexts and by researchers in many disciplines; this reflects its broad appeal and usefulness as one of the steps in exploratory data analysis. However, clustering is a difficult problem combinatorially, and differences in assumptions and contexts in different communities has made the transfer of useful generic concepts and methodologies slow to occur. This paper presents an overview of pattern clustering methods from a statistical pattern recognition perspective, with a goal of providing useful advice and references to fundamental concepts accessible to the broad community of clustering practitioners. We present a taxonomy of clustering techniques, and identify cross-cutting themes and recent advances. We also describe some important applications of clustering algorithms such as image segmentation, object recognition, and information retrieval.",
         acmid = "331504",
         address = "New York, NY, USA",
         author = "Jain, A. K. and Murty, M. N. and Flynn, P. J.",
         doi = "10.1145/331499.331504",
         issn = "0360-0300",
         issue_date = "Sept. 1999",
         journal = "ACM Comput. Surv.",
         keywords = "cluster analysis; clustering applications; exploratory data analysis; incremental clustering; similarity indices; unsupervised learning",
         month = "September",
         number = "3",
         numpages = "60",
         pages = "264–323",
         publisher = "ACM",
         title = "{Data clustering: a review}",
         url = "http://doi.acm.org/10.1145/331499.331504",
         volume = "31",
         year = "1999"
 }
 
 @inproceedings{YG98_efficient_search_in_p2p_nets,
         abstract = "Peer-to-peer systems have emerged as a popular way to share huge volumes of data. The usability of these systems depends on effective techniques to find and retrieve data; however, current techniques used in existing P2P systems are often very inefficient. In this paper, we present three techniques for efficient search in P2P systems. We present the design of these techniques, and then evaluate them using a combination of experiments over Gnutella, the largest open P2P system in operation, and analysis. We show that while our techniques maintain the same quality of results as currently used techniques, our techniques use up to 5 times fewer resources. In addition, we designed our techniques to be simple in design and implementation, so that they can be easily incorporated into existing systems for immediate impact.",
         added-at = "2005-12-21T09:35:26.000+0100",
         author = "Yang, Beverly and Garcia-Molina, Hector",
         booktitle = "{Proc.\ 22nd International Conference on Distributed Computing Systems, 2 - 5 July, 2002, Vienna, Austria}",
         interhash = "ab216e9f213b3a0d9499dc77f5188e16",
         intrahash = "04fa8a681cbfef5d56a4c9e35ae48745",
         keywords = "superpeer p2p Peer-to-peer; distributed data; search, performance modeling; evaluation",
         misc = "comment = {Lokal vorhanden}",
         organization = "IEEE Computer Society",
         title = "{Efficient Search in Peer-to-Peer Networks}",
         url = "http://www.bibsonomy.org/bibtex/204fa8a681cbfef5d56a4c9e35ae48745/schmitz",
         year = 1998
 }
 
 @article{FBD09_nonneg_matrix_factorization_with_itakura-saito_and_music_application,
         abstract = "This letter presents theoretical, algorithmic, and experimental results about nonnegative matrix factorization (NMF) with the Itakura-Saito (IS) divergence.We describe how IS-NMF is underlaid by a well-defined statistical model of superimposed gaussian components and is equivalent to maximum likelihood estimation of variance parameters. This setting can accommodate regularization constraints on the factors through Bayesian priors. In particular, inverse-gamma and gamma Markov chain priors are considered in this work. Estimation can be carried out using a space-alternating generalized expectation-maximization (SAGE) algorithm; this leads to a novel type of NMF algorithm, whose convergence to a stationary point of the IS cost function is guaranteed. We also discuss the links between the IS divergence and other cost functions used in NMF, in particular, the Euclidean distance and the generalized Kullback-Leibler (KL) divergence. As such,we describe how IS-NMF can also be performed using",
         author = "Févotte, Cédric and Bertin, Nancy and Durrieu, Jean-Louis",
         issn = "08997667",
         journal = "Neural Computation",
         keywords = "FACTORIZATION method (Quantum theory); GAUSSIAN processes; STATISTICS; ESTIMATION theory; BAYESIAN statistical decision theory; MUSICAL analysis",
         localfile = "archive/FBD09_nonneg_matrix_factorization_with_itakura-saito_and_music_application.pdf",
         number = "3",
         pages = "793–830",
         title = "{Nonnegative Matrix Factorization with the Itakura-Saito Divergence: With Application to Music Analysis}",
         url = "http://search.ebscohost.com/login.aspx?direct=true&db=pbh&AN=36785201&site=ehost-live",
         volume = "21",
         year = "2009"
 }
 
 @article{Bregman1967200,
         abstract = "IN this paper we consider an iterative method of finding the common point of convex sets. This method can be regarded as a generalization of the methods discussed in [1-4]. Apart from problems which can be reduced to finding some point of the intersection of convex sets, the method considered can be applied to the approximate solution of problems in linear and convex programming.",
         author = "Bregman, L. M.",
         doi = "10.1016/0041-5553(67)90040-7",
         issn = "0041-5553",
         journal = "USSR Computational Mathematics and Mathematical Physics",
         number = "3",
         pages = "200–217",
         title = "{The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming}",
         url = "http://www.sciencedirect.com/science/article/B75BX-49090J9-7T/2/2c1500ce39d60cfcf0d0962cc7df1d19",
         volume = "7",
         year = "1967"
 }
 
 @book{CZ97_book_parallel-optimization,
         author = "Censor, Y. and Zenios, S. A.",
         location = "New York",
         publisher = "Oxford University Press",
         series = "{Numerical Mathematics and Scientific Computation}",
         title = "{Parallel Optimization: Theory, Algorithms, and Applications}",
         year = "1997"
 }
 
 @article{DBLP:journals/corr/abs-0803-0248,
         author = "Chaintreau, Augustin and Fraigniaud, Pierre and Lebhar, Emmanuelle",
         bibsource = "DBLP, http://dblp.uni-trier.de",
         journal = "CoRR",
         localfile = "archive/CFL08_networks_become_navigable_as_nodes_move_and_forget_EXTENDED_ARCHIVE.pdf",
         title = "{Networks become navigable as nodes move and forget}",
         type = "preprint server version with extended proofs",
         url = "http://arxiv.org/abs/0803.0248",
         volume = "abs/0803.0248",
         year = "2008"
 }
 
 @article{T85_amortized_computational_analysis,
         abstract = {A powerful technique in the complexity analysis of data structures is amortization, or averaging over time. Amortized running time is a realistic but robust complexity measure for which we can obtain surprisingly tight upper and lower bounds on the variety of algorithms. By following the principle of designing algorithms whose amortized complexity is low, we obtain "self-adjusting" data structures that are simple, flexible and efficient. This paper surveys work by several researchers on amortized complexity.},
         acknowledgement = ack-nhfb,
         author = "Tarjan, Robert Endre",
         bibdate = "Sat Apr 11 10:02:33 MDT 1998",
         coden = "SJAMDU",
         fjournal = "SIAM Journal on Algebraic and Discrete Methods",
         issn = "0196-5212",
         keywords = "competitive analysis",
         localfile = "archive/T85_amortized_computational_complexity.pdf",
         mrclass = "68Q15 (68P05)",
         mrnumber = "86i:68046",
         number = "2",
         pages = "306–318",
         title = "{Amortized computational complexity}",
         volume = "6",
         year = "1985"
 }
 
 @article{journals/jacm/Vocking03,
         added-at = "2003-11-20T00:00:00.000+0100",
         author = "Vöcking, Berthold",
         date = "2003-11-20",
         description = "dblp",
         interhash = "e12acde6641fbd29a2be6282564d7b51",
         intrahash = "b4520cb029cfbb218e876fb8014b34cf",
         journal = "Journal of the ACM",
         keywords = "randomized algorithm; probabilistic analysis; balls and bins process",
         localfile = "archive/V03_HowAsymmetryHelpsLoadBalancing.pdf",
         number = 4,
         pages = "568–589",
         title = "{How asymmetry helps load balancing}",
         url = "http://dblp.uni-trier.de/db/journals/jacm/jacm50.html#Vocking03; http://doi.acm.org/10.1145/792538.792546; http://www.bibsonomy.org/bibtex/2b4520cb029cfbb218e876fb8014b34cf/dblp",
         volume = 50,
         year = 2003
 }
 
 @inproceedings{KFT10_optimal_gradient_clock_sync,
         address = "New York, NY, USA",
         author = "Kuhn, Fabian and Lenzen, Christoph and Locher, Tthomas and Oshman, Rotem",
         booktitle = "{Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing}",
         keywords = "clock synchronization; dynamic networks",
         localfile = "archive/KFT10_OptimalGradientClockSynchronizationinDynamicNetworks2010.pdf",
         location = "Zurich, Switzerland",
         organization = "ACM",
         pages = "430–439",
         publisher = "ACM",
         series = "{PODC '10}",
         title = "{Optimal Gradient Clock Synchronization in Dynamic Networks}",
         url = "http://dx.doi.org/10.1145/1835698.1835799; http://doi.acm.org/10.1145/1835698.1835799",
         year = "2010"
 }
 
 @inproceedings{ORS07_linearization_locally_self_stab_sorting_in_graphs,
         abstract = "We consider the problem of designing a distributed algorithm that, given an arbitrary connected graph G of nodes with unique labels, converts G into a sorted list of nodes. This algorithm should be as simple as possible and, for scalability, should guarantee a polylogarithmic runtime as well as at most a polylogarithmic increase in the degree of each node during its execution. Furthermore, it should be self-stabilizing, that is, it should be able to eventually construct a sorted list from any state in which the graph is connected. It turns out that satisfying all of these demands at the same time is not easy. Our basic approach towards this goal is the so-called linearization technique: each node v repeatedly does the following with its neighbors: • for its left (i.e., smaller) neighbors u1 , . . . , uk in the or- der of decreasing labels, v replaces {v, u1 }, . . . , {v, uk } by {v, u1 }, {u1 , u2 }, . . . , {uk−1 , uk }, and • for its right (i.e., larger) neighbors w1 , . . . , w in the or- der of increasing labels, v replaces {v, w1 }, . . . , {v, w } by {v, w1 }, {w1 , w2 }, . . . , {w −1 , w }. As shown in this paper, this technique transforms any connected graph into a sorted list, but there are graphs for which this can take a long time. Hence, we propose several extensions of the linearization technique and experimentally evaluate their performance. Our results indicate that some of these have a polylogarithmic performance, so there is hope that there are distributed algorithms that can achieve all of our goals above.",
         author = "Onus, Melih and Richa, Andrea and Scheideler, Christian",
         booktitle = "{Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics}",
         editor = "Applegate, David and Brodal, Gerth Stølting and Panario, Daniel and Sedgewic, Robert",
         keywords = "Self-Stabilization; Linearization",
         localfile = "archive/ORS07_linearization_locally_self_stab_sorting_in_graphs.pdf",
         location = "New Orleans, LA",
         organization = "SIAM",
         series = "{Proceedings in Applied Mathematics}",
         title = "{Linearization: Locally self-stabilizing sorting in graphs}",
         url = "http://www.siam.org/proceedings/alenex/2007/alenex07.php",
         volume = "126",
         year = "2007"
 }
 
 @article{IMP11_tutorial_to_local_amortized_onlinescheduling,
         address = "New York, NY, USA",
         author = "Im, Sungjin and Moseley, Benjamin and Pruhs, Kirk",
         doi = "10.1145/1998037.1998058",
         issn = "0163-5700",
         journal = "SIGACT News",
         localfile = "archive/IMP11_tutorial_to_local_amortized_onlinescheduling.pdf",
         month = "June",
         number = "2",
         pages = "83–97",
         publisher = "ACM",
         title = "{A tutorial on amortized local competitiveness in online scheduling}",
         volume = "42",
         year = "2011"
 }
 
 @techreport{DBLP:journals/corr/abs-1012-0009,
         author = "Casteigts, Arnaud and Flocchini, Paola and Quattrociocchi, Walter and Santoro, Nicola",
         localfile = "archive/CFQS11_time-varying-graphs-and-dynamic-networks_TR.pdf",
         title = "{Time-Varying Graphs and Dynamic Networks}",
         url = "http://arxiv.org/abs/1012.0009v2"
 }
 
 @article{Aldous1991185,
         author = "Aldous, David J.",
         doi = "10.1016/0304-4149(91)90090-Y",
         issn = "0304-4149",
         journal = "Stochastic Processes and their Applications",
         localfile = "archive/CFL08_networks_become_navigable_as_nodes_move_and_forget.pdf",
         number = "2",
         pages = "185–193",
         title = "{Meeting times for independent Markov chains}",
         url = "http://www.sciencedirect.com/science/article/pii/030441499190090Y",
         volume = "38",
         x-fetchedfrom = "ScienceDirect",
         year = "1991"
 }
 
 @article{Bshouty1999259,
         abstract = "We prove an upper bound on the meeting time of an arbitrary number of random walks in any connected undirected graph in terms of the meeting times of fewer random walks on the same graph. We show that the bound is tight for rings, and that it is both stronger and more general than a bound suggested by Tetali and Winkler (1991).",
         author = "Bshouty, Nader H. and Higham, Lisa and Warpechowska-Gruca, Jolanta",
         doi = "10.1016/S0020-0190(99)00017-4",
         issn = "0020-0190",
         journal = "Information Processing Letters",
         keywords = "distributed computing; analysis of algorithms; random walks; meeting time; hitting time",
         localfile = "archive/BHW99_meeting-times-of-random-walks-on-graphs.pdf",
         number = "5",
         pages = "259–265",
         title = "{Meeting times of random walks on graphs}",
         url = "http://www.sciencedirect.com/science/article/pii/S0020019099000174",
         volume = "69",
         year = "1999"
 }
 
 @article{cooper2009multiple,
         abstract = "We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make the analysis for random regular graphs. The cover time of a random walk on a random r-regular graph was studied in [C. Cooper and A. Frieze, SIAM J. Discrete Math., 18 (2005), pp. 728-740], where it was shown with high probability (whp) that for r ≥ 3 the cover time is asymptotic to θrnlnn, where θr = (r - 1)/(r - 2). In this paper we prove the following (whp) results, arising from the study of multiple random walks on a random regular graph G. For k independent walks on G, the cover time C(k) is asymptotic to CG/k, where CG is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is θrn/(k2). If the walks can communicate when meeting at a vertex, we show that, for most starting positions, the expected time for k walks to broadcast a single piece of information to each other is asymptotic to 21n k/kθrn as k,n → ∞. We also establish properties of walks where there are two types of particles, predator and prey, or where particles interact when they meet at a vertex by coalescing or by annihilating each other. For example, the expected extinction time of k explosive particles (k even) tends to (2ln2) θrn as k → ∞. The case of n coalescing particles, where one particle is initially located at each vertex, corresponds to a voter model defined as follows: Initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. The expected time for a unique opinion to emerge is the same as the expected time for all the particles to coalesce, which is asymptotic to 2θrn. Combining results from the predator-prey and multiple random walk models allows us to compare expected detection times of all prey in the following scenarios: Both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, and the predators move randomly and the prey stays fixed. In all cases, with k predators and l prey the expected detection time is θrHln/k, where Hl is the lth harmonic number. © 2009 Society for Industrial and Applied Mathematics.",
         author = "Cooper, Colin and Frieze, Alan and Radzik, Tomasz",
         booktitle = "{SIAM Journal on Discrete Mathematics }",
         issn = "08954801",
         journal = "Preprint",
         keywords = "multiple walks; random regular graphs; random walks; cover time",
         localfile = "archive/CFR09_multiple-random-walks-in-random-regular-graphs.pdf",
         number = "4",
         pages = "1738–1761",
         publisher = "SIAM",
         title = "{Multiple random walks in random regular graphs}",
         url = "http://dx.doi.org/10.1137/080729542",
         volume = "23",
         x-fetchedfrom = "Google Scholar",
         year = "2009"
 }
 
 @article{lovász1993random,
         author = "Lovász, Láslo",
         journal = "Combinatorics, Paul Erdos is Eighty",
         localfile = "archive/L93_random-walks-a-survey.pdf",
         number = "1",
         pages = "1–46",
         publisher = "János Bolyai Mathematical Society",
         title = "{Random walks on graphs: A survey}",
         volume = "2",
         x-fetchedfrom = "Google Scholar",
         year = "1993"
 }
 
 @inproceedings{Pettie:2010:AFM:1873601.1873719,
         acmid = "1873719",
         address = "Philadelphia, PA, USA",
         author = "Pettie, Seth",
         booktitle = "{Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms}",
         isbn = "978-0-898716-98-6",
         localfile = "archive/P10_applications-of-forbidden-01-matrices-to-search-tree-and-path-compression-based-data-structures.pdf",
         location = "Austin, Texas",
         numpages = "11",
         pages = "1457–1467",
         publisher = "Society for Industrial and Applied Mathematics",
         series = "{SODA '10}",
         title = "{Applications of forbidden 0-1 matrices to search tree and path compression-based data structures}",
         url = "http://portal.acm.org/citation.cfm?id=1873601.1873719",
         year = "2010"
 }
 
 @article{coppersmith1993collisions,
         abstract = {A token located at some vertex v of a connected, undirected graph G on n vertices is said to be taking a "random walk" on G if, whenever it is instructed to move, it moves with equal probability to any of the neighbors of v. The authors consider the following problem: Suppose two tokens are placed on G, and at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying to keep the tokens apart as long as possible. What is the expected time M before they meet? The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing. Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound. The authors use a novel potential function argument to show that in the worst case M=(4/27+o(1))n^3.},
         author = "Coppersmith, Don and Tetali, Prasad and Winkler, Peter",
         booktitle = "{SIAM Journal on Discrete Mathematics }",
         journal = "SIAM Journal on Discrete Mathematics",
         keywords = "random walks; graph; Markov chain; collision; token management",
         localfile = "archive/CTW93_collisions-among-random-walks-on-a-graph.pdf",
         month = "August",
         number = "3",
         pages = "363–374",
         publisher = "Society for Industrial and Applied Mathematics",
         title = "{Collisions among random walks on a graph}",
         url = "http://dx.doi.org/10.1137/0406029",
         volume = "6",
         x-fetchedfrom = "Google Scholar",
         year = "1993"
 }
 
 @inproceedings{ADHL10_basic-netwok-creation-games,
         acmid = "1810502",
         address = "New York, NY, USA",
         author = "Alon, Noga and Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Leighton, Tom",
         booktitle = "{Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures}",
         doi = "10.1145/1810479.1810502",
         isbn = "978-1-4503-0079-7",
         keywords = "nash equilibrium; network design; price of anarchy; routing",
         localfile = "archive/ADHL10_basic-network-creation-games.pdf",
         location = "Thira, Santorini, Greece",
         numpages = "8",
         pages = "106–113",
         publisher = "ACM",
         series = "{SPAA '10}",
         title = "{Basic network creation games}",
         url = "http://doi.acm.org/10.1145/1810479.1810502",
         x-fetchedfrom = "ACM Digital Library",
         year = "2010"
 }
 
 @inproceedings{FLMPS03_on-a-network-creation-game,
         acmid = "872088",
         address = "New York, NY, USA",
         author = "Fabrikant, Alex and Luthra, Ankur and Maneva, Elitza and Papadimitriou, Christos H. and Shenker, Scott",
         booktitle = "{Proceedings of the twenty-second annual symposium on Principles of distributed computing}",
         doi = "10.1145/872035.872088",
         isbn = "1-58113-708-7",
         keywords = "nash equilibrium; distributed network design; game-theoretic models; price of anarchy",
         localfile = "archive/FLMPS03_on-a-network-creation-game.pdf",
         location = "Boston, Massachusetts",
         numpages = "5",
         pages = "347–351",
         publisher = "ACM",
         series = "{PODC '03}",
         title = "{On a network creation game}",
         url = "http://doi.acm.org/10.1145/872035.872088",
         x-fetchedfrom = "ACM Digital Library",
         year = "2003"
 }
 
 @inproceedings{Mehler:2009:POF:1583991.1584072,
         acmid = "1584072",
         address = "New York, NY, USA",
         author = "Mehler, Jan and auf der Heide, Friedhelm Meyer",
         booktitle = "{Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures}",
         doi = "10.1145/1583991.1584072",
         isbn = "978-1-60558-606-9",
         keywords = "amortized analysis; file allocation; mobile ad hoc networks; online algorithms",
         localfile = "archive/MMadH09_power-aware-online-file-allocation-in-mobile-adhoc.pdf",
         location = "Calgary, AB, Canada",
         numpages = "10",
         pages = "347–356",
         publisher = "ACM",
         series = "{SPAA '09}",
         title = "{Power-aware online file allocation in mobile ad hoc networks}",
         url = "http://doi.acm.org/10.1145/1583991.1584072",
         year = "2009"
 }
 
 @article{Bienkowski2009545,
         abstract = "We present an extension of a classical data management subproblem, the page migration. The problem is investigated in dynamic networks, where costs of communication between different nodes may change with time. We construct asymptotically optimal online algorithms for this problem, both in deterministic and randomized scenarios.",
         author = "Bienkowski, Marcin and Byrka, Jaroslaw and Korzeniowski, Miroslaw and auf der Heide, Friedhelm Meyer",
         doi = "10.1016/j.jda.2008.07.006",
         issn = "1570-8667",
         journal = "Journal of Discrete Algorithms",
         keywords = "online algorithms; randomized algorithm; page migration; data management; dynamic networks",
         localfile = "archive/BBKMadH09_optimal-algorithms-for-page-migration-in-dynamic-networks.pdf",
         number = "4",
         pages = "545–569",
         title = "{Optimal algorithms for page migration in dynamic networks}",
         url = "http://www.sciencedirect.com/science/article/pii/S1570866708000518",
         volume = "7",
         year = "2009"
 }
 
 @incollection{springerlink:10.1007/978-3-642-22012-8_7,
         abstract = "This paper considers compact fault-tolerant routing schemes for weighted general graphs, namely, routing schemes that avoid a set of failed (or forbidden) edges. We present a compact routing scheme capable of handling multiple edge failures. Assume a source node s contains a message M designated to a destination target t and assume a set F of edges crashes (unknown to s). Our scheme routes the message to t (provided that s and t are still connected in G ∖ F) over a path whose length is proportional to the distance between s and t in G ∖ F, to |F|3 and to some poly-log factor. The routing table required at a node v is of size proportional to the degree of v in G and some poly-log factor. This improves on the previously known fault-tolerant compact routing scheme for general graphs, which was capable of overcoming at most 2 edge failures.",
         affiliation = "Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel",
         author = "Chechik, Shiri",
         booktitle = "{Automata, Languages and Programming}",
         editor = "Aceto, Luca and Henzinger, Monika and Sgall, Jirí",
         keywords = "routing scheme; fault tolerant; tree cover",
         localfile = "archive/C11_fault-tolerant-routing-schemes-for-general-graphs.pdf",
         note = "10.1007/978-3-642-22012-8\_7",
         pages = "101–112",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         title = "{Fault-Tolerant Compact Routing Schemes for General Graphs}",
         url = "http://dx.doi.org/10.1007/978-3-642-22012-8_7",
         volume = "6756",
         year = "2011"
 }
 
 @inproceedings{ieee1357018,
         abstract = "We analyze the characteristics of overlay routing networks generated by selfish nodes playing competitive network construction games. We explore several networking scenarios - some simplistic, others more realistic - and analyze the resulting Nash equilibrium graphs with respect to topology, performance, and resilience. We find a fundamental tradeoff between performance and resilience, and show that limiting the degree of nodes is of great importance in controlling this balance. Further, by varying the cost function, the game produces widely different topologies; one parameter in particular - the relative cost between maintaining an overlay link and increasing the path length to other nodes - can generate topologies with node-degree distributions whose tails vary from exponential to power-law. We conclude that competitive games can create overlay routing networks satisfying very diverse goals.",
         arnumber = "1357018",
         author = "Chun, Byung-Gon and Fonseca, R. and Stoica, I. and Kubiatowicz, J.",
         booktitle = "{INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies}",
         doi = "10.1109/INFCOM.2004.1357018",
         issn = "0743-166X",
         keywords = "Nash equilibrium graph; network construction game; overlay routing network; graph theory; telecommunication links; telecommunication network routing; telecommunication network topology",
         localfile = "archive/CFSK04_characterizing-selfishly-constructed-overlay-routing-networks.pdf",
         month = "march",
         pages = "1329–1339 vol.2",
         title = "{Characterizing selfishly constructed overlay routing networks}",
         volume = "2",
         x-fetchedfrom = "IEEEXplore",
         year = "2004"
 }
 
 @inproceedings{Moscibroda:2006:TFS:1146381.1146403,
         acmid = "1146403",
         address = "New York, NY, USA",
         author = "Moscibroda, Thomas and Schmid, Stefan and Wattenhofer, Roger",
         booktitle = "{Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing}",
         doi = "10.1145/1146381.1146403",
         isbn = "1-59593-384-0",
         keywords = "NP-hardness; game theory; network creation",
         localfile = "archive/MSW06_on-the-topologies-formed-by-selfish-peers.pdf",
         location = "Denver, Colorado, USA",
         numpages = "10",
         pages = "133–142",
         publisher = "ACM",
         series = "{PODC '06}",
         title = "{On the Topologies Formed by Selfish Peers}",
         url = "http://doi.acm.org/10.1145/1146381.1146403",
         x-fetchedfrom = "ACM Digital Library",
         year = "2006"
 }
 
 @incollection{CLDF11_a-new-approach-for-analyzing-convergence-problems,
         abstract = "Given a set of n mobile robots in the d-dimensional Euclidean space, the goal is to let them converge to a single not predefined point. The challenge is that the robots are limited in their capabilities. Robots can, upon activation, compute the positions of all other robots using an individual affine coordinate system. The robots are indistinguishable, oblivious and may have different affine coordinate systems. A very general discrete time model assumes that robots are activated in arbitrary order. Further, the computation of a new target point may happen much earlier than the movement, so that the movement is based on outdated information about other robot’s positions. Time is measured as the number of rounds, where a round ends as soon as each robot has moved at least once. In [6], the Center of Gravity is considered as target function, convergence was proven, and the number of rounds needed for halving the diameter of the convex hull of the robot’s positions was shown to be and ?(n). We present an easy-to-check property of target functions that guarantee convergence and yields upper time bounds. This property intuitively says that when a robot computes a new target point, this point is significantly within the current axes aligned minimal box containing all robots. This property holds, e.g., for the above-mentioned target function, and improves the above to an asymptotically optimal upper bound. Our technique also yields a constant time bound for a target function that requires all robots having identical coordinate axes.",
         affiliation = "Heinz Nixdorf Institute \& Department of Computer Science, University of Paderborn, Germany",
         author = "Cord-Landwehr, Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes, Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus and {Meyer auf der Heide}, Friedhelm and Raupach, Christoph and Swierkot, Kamil and Warner, Daniel and Weddemann, Christoph and Wonisch, Daniel",
         booktitle = "{Automata, Languages and Programming}",
         editor = "Aceto, Luca and Henzinger, Monika and Sgall, Jirí",
         localfile = "archive/CLDF11_a-new-approach-for-analyzing-convergence-problems.pdf",
         note = "10.1007/978-3-642-22012-8\_52",
         pages = "650–661",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         title = "{A New Approach for Analyzing Convergence Algorithms for Mobile Robots}",
         url = "http://dx.doi.org/10.1007/978-3-642-22012-8_52",
         volume = "6756",
         year = "2011"
 }
 
 @incollection{springerlink:10.1007/978-3-642-18381-2_15,
         affiliation = "Heinz Nixdorf Institute, Computer Science Department, University of Paderborn",
         author = "Cord-Landwehr, Andreas and Degener, Bastian and Fischer, Matthias and Hüllmann, Martina and Kempkes, Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and Märtens, Marcus and auf der Heide, Friedhelm and Raupach, Christoph and Swierkot, Kamil and Warner, Daniel and Weddemann, Christoph and Wonisch, Daniel",
         booktitle = "{SOFSEM 2011: Theory and Practice of Computer Science}",
         doi = "10.1007/978-3-642-18381-2_15",
         editor = "Cerná, Ivana and Gyimóthy, Tibor and Hromkovic, Juraj and Jefferey, Keith and Královic, Rastislav and Vukolic, Marko and Wolf, Stefan",
         isbn = "",
         pages = "178–189",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         title = "{Collisionless Gathering of Robots with an Extent}",
         url = "http://dx.doi.org/10.1007/978-3-642-18381-2_15",
         volume = "6543",
         x-fetchedfrom = "SpringerLink",
         year = "2011"
 }
 
 @inproceedings{ACLD11_local-approximation-algorithms-for-uncap-metric-flp-power-aware,
         author = "Abshoff, Sebastian and Cord-Landwehr, Andreas and Degener, Bastian and Kempkes, Barbara and Pietrzyk, Peter",
         booktitle = "{Proceedings of 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities}",
         note = "(to be published)",
         publisher = "Springer-Verlag",
         series = "{LNCS}",
         title = "{Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks}",
         year = "2011"
 }
 
 @inproceedings{Garey:1976:NGP:800113.803626,
         acmid = "803626",
         address = "New York, NY, USA",
         author = "Garey, M. R. and Graham, R. L. and Johnson, D. S.",
         booktitle = "{Proceedings of the eighth annual ACM symposium on Theory of computing}",
         doi = "10.1145/800113.803626",
         localfile = "archive/G76_some-np-complete-geometric-problems.pdf",
         location = "Hershey, Pennsylvania, United States",
         numpages = "13",
         pages = "10–22",
         publisher = "ACM",
         series = "{STOC '76}",
         title = "{Some NP-complete geometric problems}",
         url = "http://doi.acm.org/10.1145/800113.803626",
         year = "1976"
 }
 
 @inproceedings{CMTV07_constructing-scalable-overlays-for-pub-sub-with-many-topics,
         acmid = "1281118",
         address = "New York, NY, USA",
         author = "Chockler, Gregory and Melamed, Roie and Tock, Yoav and Vitenberg, Roman",
         booktitle = "{Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing}",
         doi = "10.1145/1281100.1281118",
         isbn = "978-1-59593-616-5",
         keywords = "application-level multicast; optimization problems; overlay networks; peer-to-peer; pub/sub",
         localfile = "archive/CMTV07_constructing-scalable-overlays-for-pub-sub-with-many-topics.pdf",
         location = "Portland, Oregon, USA",
         numpages = "10",
         pages = "109–118",
         publisher = "ACM",
         series = "{PODC '07}",
         title = "{Constructing scalable overlays for pub-sub with many topics}",
         url = "http://doi.acm.org/10.1145/1281100.1281118",
         year = "2007"
 }
 
 @inproceedings{springerlink:10.1007/978-3-642-22012-8_8,
         abstract = "We study stable marriage and roommates problems in graphs with locality constraints. Each player is a node in a social network and has an incentive to match with other players. The value of a match is specified by an edge weight. Players explore possible matches only based on their current neighborhood. We study convergence of natural better-response dynamics that converge to locally stable matchings – matchings that allow no incentive to deviate with respect to their imposed information structure in the social network. For every starting state we construct in polynomial time a sequence of polynomially many better-response moves to a locally stable matching. However, for a large class of oblivious dynamics including random and concurrent better-response the convergence time turns out to be exponential. In contrast, convergence time becomes polynomial if we allow the players to have a small amount of random memory, even for many-to-many matchings and more general notions of neighborhood.",
         affiliation = "Dept. of Computer Science, RWTH Aachen University, Germany",
         author = "Hoefer, Martin",
         booktitle = "{Automata, Languages and Programming}",
         doi = "10.1007/978-3-642-22012-8_8",
         editor = "Aceto, Luca and Henzinger, Monika and Sgall, Jirí",
         isbn = "978-3-642-22011-1",
         keyword = "Computer Science",
         localfile = "archive/H11_local-matching-dynamics-in-social-networks_EXTENDED.pdf; archive/H11_local-matching-dynamics-in-social-networks.pdf",
         pages = "113–124",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         title = "{Local Matching Dynamics in Social Networks}",
         url = "http://dx.doi.org/10.1007/978-3-642-22012-8_8",
         volume = "6756",
         x-fetchedfrom = "SpringerLink",
         year = "2011"
 }
 
 @incollection{AH_contribution-games-in-social-networks,
         abstract = "We consider network contribution games , where each agent in a social network has a budget of effort that he can contribute to different collaborative projects. Depending on the contribution of the involved agents a project will be successful to a different degree, and to measure the success we use a reward function for each project. Every agent is trying to maximize the reward from all projects that it is involved in. We consider pairwise equilibria of this game and characterize the existence, computational complexity, and quality of equilibrium based on the types of reward functions involved. For example, when all reward functions are concave, we prove that the price of anarchy is at most 2. For convex functions the same only holds under some special but very natural conditions. A special focus of the paper are minimum effort games, where the success of a project depends only on the minimum effort of any of the participants. Finally, we briefly discuss additional aspects like approximate equilibria and convergence of dynamics.",
         affiliation = "Dept. of Computer Science, Rensselaer Polytechnic Institute, Troy, NY",
         author = "Anshelevich, Elliot and Hoefer, Martin",
         booktitle = "{Algorithms – ESA 2010}",
         editor = "de Berg, Mark and Meyer, Ulrich",
         isbn = "978-3-642-15774-5",
         keyword = "Computer Science",
         localfile = "archive/AH10_contribution-games-in-social-networks.pdf; archive/AH10_contribution-games-in-social-networks_FULLPAPER.pdf",
         note = "10.1007/978-3-642-15775-2\_14",
         pages = "158–169",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         title = "{Contribution Games in Social Networks}",
         url = "http://dx.doi.org/10.1007/978-3-642-15775-2_14",
         volume = "6346",
         year = "2010"
 }
 
 @article{AAABN06_general-approach-to-online-network-opt-problems,
         acmid = "1198522",
         address = "New York, NY, USA",
         author = "Alon, Noga and Awerbuch, Baruch and Azar, Yossi and Buchbinder, Niv and Naor, Joseph (Seffi)",
         doi = "10.1145/1198513.1198522",
         issn = "1549-6325",
         journal = "ACM Trans. Algorithms",
         keywords = "Online network optimization; competitive analysis; facility location; group Steiner; multi-cuts; randomized rounding",
         localfile = "archive/AAZBN06_general-approach-to-online-network-opt-problems.pdf",
         month = "October",
         number = "4",
         numpages = "21",
         pages = "640–660",
         publisher = "ACM",
         title = "{A general approach to online network optimization problems}",
         url = "http://doi.acm.org/10.1145/1198513.1198522",
         volume = "2",
         x-fetchedfrom = "ACM Digital Library",
         year = "2006"
 }
 
 @inproceedings{AKR91_when-trees-collide,
         author = "Agrawal, A. and Klein, P. and Ravi, R.",
         booktitle = "{Proceedings of the twenty-third annual ACM symposium on Theory of computing}",
         keywords = "GNWS - Generalized Node-Weighted Steiner Tree Problem; NWS - Network-Weighted Steiner Tree Problem; network design",
         localfile = "archive/AKR91_when-trees-collide.pdf",
         organization = "ACM",
         pages = "134–144",
         title = "{When trees collide: An approximation algorithm for the generalized Steiner problem on networks}",
         x-fetchedfrom = "Google Scholar",
         year = "1991"
 }
 
 @article{A06_node-weighted-steiner-problem-in-graphs,
         abstract = "In this paper we study a variant of the Node-Weighted Steiner Tree problem in which the weights (costs) of vertices are restricted, in the sense that the ratio of the maximum node weight to the minimum node weight is bounded by a quantity α. This problem has applications in multicast routing where the cost of participating routers must be taken into consideration and the network is relatively homogenous in terms of the cost of the routers. We consider both online and offline versions of the problem. For the offline version we show an upper bound of O( min {logα, logk}) on the approximation ratio of deterministic algorithms (where k is the number of terminals). We also prove that the bound is tight unless P=NP. For the online version we show a tight bound of Θ( max { min {α, k}, logk }), which applies to both deterministic and randomized algorithms. We also show how to apply (and extend to node-weighted graphs) recent work of Alon et al. so as to obtain a randomized online algorithm with competitive ratio O(logm logk), where m is the number of the edges in the graph, independently of the value of α. All our bounds also hold for the Generalized Node-Weighted Steiner Problem, in which only connectivity between pairs of vertices must be guaranteed.",
         author = "Angelopoulos, Spyros",
         booktitle = "{Algorithm Theory – SWAT 2006}",
         editor = "Arge, Lars and Freivalds, Rusins",
         isbn = "978-3-540-35753-7",
         keywords = "NWS - Network-Weighted Steiner Tree Problem; GNWS - Generalized Node-Weighted Steiner Tree Problem; GNWS - Generalized Node-Weighted Steiner Tree Problem; NWS - Network-Weighted Steiner Tree Problem; online algorithms; competitive ratio",
         localfile = "archive/A06_node-weighted-steiner-problem-in-graphs.pdf",
         note = "10.1007/11785293\_21",
         pages = "208–219",
         publisher = "Springer Berlin / Heidelberg",
         series = "{Lecture Notes in Computer Science}",
         title = "{The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights}",
         url = "http://dx.doi.org/10.1007/11785293_21",
         volume = "4059",
         x-fetchedfrom = "Google Scholar",
         year = "2006"
 }
 
 @inproceedings{GHR06_oblivious-network-design,
         acmid = "1109665",
         address = "New York, NY, USA",
         author = "Gupta, Anupam and Hajiaghayi, Mohammad T. and Räcke, Harald",
         booktitle = "{Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm}",
         doi = "10.1145/1109557.1109665",
         isbn = "0-89871-605-5",
         localfile = "archive/GHR06_oblivious-network-design.pdf",
         location = "Miami, Florida",
         numpages = "10",
         pages = "970–979",
         publisher = "ACM",
         series = "{SODA '06}",
         title = "{Oblivious network design}",
         url = "http://doi.acm.org/10.1145/1109557.1109665",
         year = "2006"
 }
 
 @techreport{HKKN11_cobminatorial-algorithms-for-cap-network-design,
         author = "Hajiaghayi, Mohammad Taghi and Khandekar, Rohit and Kortsarz, Guy and Nutov, Zeev",
         bibsource = "DBLP, http://dblp.uni-trier.de",
         journal = "CoRR",
         keywords = "SNDP; CAP-SNDP; group steiner tree; tree cover",
         localfile = "archive/HKKN11_cobminatorial-algorithms-for-cap-network-design.pdf",
         title = "{Combinatorial Algorithms for Capacitated Network Design}",
         url = "http://arxiv.org/abs/1108.1176",
         volume = "abs/1108.1176",
         year = "2011"
 }
 
 @inproceedings{HK03_polylogarithmic-inapproximability,
         abstract = "We provide the first hardness result of a polylogarithmic approximation ratio for a natural NP-hard optimization problem. We show that for every fixed ε>0, the GROUP-STEINER-TREE problem admits no efficient log2-ε k approximation, where k denotes the number of groups (or, alternatively, the input size), unless NP has quasi polynomial Las-Vegas algorithms. This hardness result holds even for input graphs which are Hierarchically Well-Separated Trees, introduced by Bartal [FOCS, 1996]. For these trees (and also for general trees), our bound is nearly tight with the log-squared approximation currently known. Our results imply that for every fixed ε>0, the DIRECTED-STEINER TREE problem admits no log2-ε n–approximation, where n is the number of vertices in the graph, under the same complexity assumption.",
         acmid = "780628",
         address = "New York, NY, USA",
         author = "Halperin, Eran and Krauthgamer, Robert",
         booktitle = "{Proceedings of the thirty-fifth annual ACM symposium on Theory of computing}",
         doi = "10.1145/780542.780628",
         isbn = "1-58113-674-9",
         keywords = "Steiner tree; approximation algorithms; hardness of approximation; integrality ratio; polylogarithmic approximation",
         localfile = "archive/HK03_polylogarithmic-inapproximability.pdf",
         location = "San Diego, CA, USA",
         numpages = "10",
         pages = "585–594",
         publisher = "ACM",
         series = "{STOC '03}",
         title = "{Polylogarithmic inapproximability}",
         url = "http://doi.acm.org/10.1145/780542.780628",
         year = "2003"
 }
 
 @inproceedings{GW92_general-approx-technique-for-constrained-forest-problems,
         abstract = "We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum spanning tree, minimum-weight perfect matching, traveling salesman and Steiner tree problems. Our technique produces approximation algorithms that run in O(n2 log n) time and come within a factor of 2 of optimal for most of these problems. For instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. Our running time of O(n2 log n) time compares favorably with the best strongly polynomial exact algorithms running in O(n3) time for dense graphs. A similar result is obtained for the 2-matching problem and its variants.We also derive the first approximation algorithms for many NP-complete problems, including the non-fixed point-to-point connection problem, the exact path partitioning problem and complex location-design problems. Moreover, for the prize-collecting traveling salesman or Steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [4].",
         acmid = "139468",
         address = "Philadelphia, PA, USA",
         author = "Goemans, Michel X. and Williamson, David P.",
         booktitle = "{Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms}",
         isbn = "0-89791-466-X",
         localfile = "archive/GW92_general-approx-technique-for-constrained-forest-problems.pdf",
         location = "Orlando, Florida, United States",
         numpages = "10",
         pages = "307–316",
         publisher = "Society for Industrial and Applied Mathematics",
         series = "{SODA '92}",
         title = "{A general approximation technique for constrained forest problems}",
         url = "http://dl.acm.org/citation.cfm?id=139404.139468",
         year = "1992"
 }