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

0001 @comment{x-kbibtex-encoding=utf-8}
0002 
0003 @inproceedings{DKP10-distr-const-factor-dynamic-flp,
0004         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.",
0005         author = "Degener, Bastian and Kempkes, Barbara and Pietrzyk, Peter",
0006         booktitle = "{Proceedings of IPDPS 2010}",
0007         crossref = "DGL08_Kinetic-Facility-Location",
0008         file = "Pre-Print:/home/phoenixx/Studium/MasterThesis/DKP10\_local\_distr\_const-factor\_dynamic\_fcp.pdf:PDF",
0009         keywords = "facility location; dynamic; constant factor approximation; local",
0010         organization = "IPDPS 2010",
0011         owner = "phoenixx",
0012         timestamp = "2010.02.28",
0013         title = "{A local, distributed constant-factor approximation algorithm for the dynamic facility location problem}",
0014         year = "2010"
0015 }
0016 
0017 @inproceedings{LMM04_scheduling_against_adversarial_network,
0018         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.",
0019         added-at = "2006-02-15T00:00:00.000+0100",
0020         author = "Leonardi, Stefano and Marchetti-Spaccamela, Alberto and auf der Heide, Friedhelm Meyer",
0021         booktitle = "{Proceedings of the 16th ACM Symposium of Parallelism in Algorithms and Architectures (SPAA '04)}",
0022         crossref = "conf/spaa/2004",
0023         date = "2006-02-15",
0024         description = "dblp",
0025         editor = "Gibbons, Phillip B. and Adler, Micah",
0026         interhash = "67ad1818fa8dd30668085b8325c87a18",
0027         intrahash = "ec240ce81d095bc052ea751d502e87c5",
0028         isbn = "1-58113-840-7",
0029         keywords = Scheduling # "Online Algorithm; Competitive Analysis",
0030         month = jun,
0031         pages = "151–159",
0032         publisher = "ACM",
0033         title = "{Scheduling against an adversarial network}",
0034         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",
0035         year = 2004
0036 }
0037 
0038 @inproceedings{DGNR09_online_story_scheduling_in_web_advertising,
0039         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.",
0040         added-at = "2009-01-24T00:00:00.000+0100",
0041         address = "Philadelphia, PA, USA",
0042         author = "Dasgupta, Anirban and Ghosh, Arpita and Nazerzadeh, Hamid and Raghavan, Prabhakar",
0043         booktitle = "{Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms}",
0044         crossref = "conf/soda/2009",
0045         date = "2009-01-24",
0046         description = "dblp",
0047         editor = "Mathieu, Claire",
0048         interhash = "490caba3eaab01862d082cde767d83f1",
0049         intrahash = "08ee0846d5114cf38c925410c15d1303",
0050         keywords = "dblp",
0051         location = "New York, New York",
0052         pages = "1275–1284",
0053         publisher = "Society for Industrial and Applied Mathematics (SIAM)",
0054         series = "{SODA '09}",
0055         title = "{Online story scheduling in web advertising}",
0056         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",
0057         year = 2009
0058 }
0059 
0060 @inproceedings{AB09_coresets-and-approximate-clustering-for-bregman-divergences,
0061         added-at = "2009-01-24T00:00:00.000+0100",
0062         author = "Ackermann, Marcel R. and Blömer, Johannes",
0063         booktitle = "{SODA}",
0064         crossref = "conf/soda/2009",
0065         date = "2009-01-24",
0066         description = "dblp",
0067         editor = "Mathieu, Claire",
0068         interhash = "6b56c21640088899e3b246fa7fd9a23a",
0069         intrahash = "ca82e3e3ba36f49e3d651e9839e4a470",
0070         keywords = "dblp",
0071         localfile = "archive/AB09_coresets-and-approximate-clustering-for-bregman-divergences.pdf",
0072         pages = "1088–1097",
0073         publisher = "SIAM",
0074         title = "{Coresets and approximate clustering for Bregman divergences.}",
0075         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",
0076         year = 2009
0077 }
0078 
0079 @inproceedings{YG01_comparing_hybrid_p2p_systems,
0080         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.},
0081         added-at = "2002-01-03T00:00:00.000+0100",
0082         author = "Yang, Beverly and Garcia-Molina, Hector",
0083         booktitle = "{VLDB}",
0084         crossref = "conf/vldb/2001",
0085         date = "2002-01-03",
0086         description = "dblp",
0087         editor = "Apers, Peter M. G. and Atzeni, Paolo and Ceri, Stefano and Paraboschi, Stefano and Ramamohanarao, Kotagiri and Snodgrass, Richard T.",
0088         interhash = "12560ac0ed3053a9b50c851f02419244",
0089         intrahash = "364cc66f5b65bfc7fa41a3e885cde33c",
0090         isbn = "1-55860-804-4",
0091         keywords = "dblp",
0092         note = "Evaluation",
0093         pages = "561––570",
0094         publisher = "Morgan Kaufmann",
0095         title = "{Comparing Hybrid Peer-to-Peer Systems.}",
0096         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",
0097         year = 2001
0098 }
0099 
0100 @inproceedings{conf/icalp/ChaintreauFL08,
0101         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.",
0102         added-at = "2008-07-08T00:00:00.000+0200",
0103         address = "Berlin, Heidelberg",
0104         author = "Chaintreau, Augustin and Fraigniaud, Pierre and Lebhar, Emmanuelle",
0105         booktitle = "{Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I}",
0106         crossref = "conf/icalp/2008-1",
0107         date = "2008-07-08",
0108         description = "dblp",
0109         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",
0110         interhash = "a4081126ff934cce0ed38ddf8db6af2a",
0111         intrahash = "40906a7e2ffb9fd967400d38b8bdd1c6",
0112         isbn = "978-3-540-70574-1",
0113         keywords = "Small world phenomenon; dynamic process; random walks; resource location; routing; spatial gossip",
0114         localfile = "archive/CFL08_networks_become_navigable_as_nodes_move_and_forget.pdf",
0115         location = "Reykjavik, Iceland",
0116         pages = "133–144",
0117         publisher = "Springer-Verlag",
0118         series = "{Lecture Notes in Computer Science}",
0119         title = "{Networks Become Navigable as Nodes Move and Forget}",
0120         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",
0121         volume = 5125,
0122         year = 2008
0123 }
0124 
0125 @inproceedings{GJRSST10_distr-graph-linearization,
0126         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.",
0127         added-at = "2010-07-21T16:01:11.000+0200",
0128         author = "Gall, Dominik and Jacob, Riko and Richa, Andréa W. and Scheideler, Christian and Schmid, Stefan and Täubig, Hanjo",
0129         booktitle = "{LATIN 2010: Theoretical Informatics}",
0130         crossref = "conf/latin/2010",
0131         date = "2010-04-27",
0132         editor = "López-Ortiz, Alejandro",
0133         interhash = "485f14443b751421dc44d051dfe304b7",
0134         intrahash = "d004e207935c5358f56f76b8ffebe657",
0135         isbn = "978-3-642-12199-9",
0136         keywords = "graph linearization",
0137         localfile = "archive/GJRSST10_distr-graph-linearization.pdf",
0138         pages = "294–305",
0139         publisher = "Springer Berlin / Heidelberg",
0140         series = "{Lecture Notes in Computer Science}",
0141         title = "{Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization.}",
0142         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",
0143         volume = 6034,
0144         year = 2010
0145 }
0146 
0147 @article{J01_factor-2-approx-GSNP,
0148         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. ",
0149         affiliation = "College of Computing, Georgia Institute of Technology; USA; E-mail: kjain@cc.gatech.edu US",
0150         author = "Jain, Kamal",
0151         issn = "0209-9683",
0152         issue = "1",
0153         journal = "Combinatorica",
0154         keyword = "Mathematics and Statistics",
0155         keywords = "Steiner tree; approximation algorithm",
0156         localfile = "archive/J01_factor-2-approx-GSNP.pdf",
0157         note = "10.1007/s004930170004",
0158         pages = "39–60",
0159         publisher = "Springer Berlin / Heidelberg",
0160         title = "{A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem}",
0161         url = "http://dx.doi.org/10.1007/s004930170004",
0162         volume = "21",
0163         year = "2001"
0164 }
0165 
0166 @article{agrawal1995trees,
0167         author = "Agrawal, A. and Klein, PN and Ravi, R.",
0168         journal = "Comput",
0169         keywords = "GNWS - Generalized Node-Weighted Steiner Tree Problem",
0170         pages = "440–456",
0171         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}",
0172         volume = "24",
0173         x-fetchedfrom = "Google Scholar",
0174         year = "1995"
0175 }
0176 
0177 @article{JRSS09_selfstabilizing_delaunay-graphs,
0178         author = "Jacob, Riko and Ritscher, Stephan and Scheideler, Christian and Schmid, Stefan",
0179         booktitle = "{Algorithms and Computation}",
0180         pages = "771–780",
0181         publisher = "Springer-Verlag",
0182         series = "{Lecture Notes in Computer Science}",
0183         title = "{A Self-stabilizing and Local Delaunay Graph Construction}",
0184         url = "http://dx.doi.org/10.1007/978-3-642-10631-6_78",
0185         volume = "5878",
0186         year = "2009"
0187 }
0188 
0189 @incollection{AEMN06_constant_factor_dom_sets_udg,
0190         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.",
0191         affiliation = "Department of Computer Science, University of Liverpool",
0192         author = "Ambühl, Christoph and Erlebach, Thomas and Mihalák, Matúš and Nunkesser, Marc",
0193         booktitle = "{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques}",
0194         doi = "10.1007/11830924_3; 10.1007/11830924_3",
0195         editor = "Díaz, Josep and Jansen, Klaus and Rolim, José and Zwick, Uri",
0196         file = "Full Paper Springer:/home/phoenixx/Studium/MasterThesis/mastercola/papers/AEMN06\_constant\_factor\_dom\_sets\_udg.pdf:PDF",
0197         owner = "phoenixx",
0198         pages = "3–14",
0199         publisher = "Springer Berlin / Heidelberg",
0200         series = "{Lecture Notes in Computer Science}",
0201         timestamp = "2010.09.03",
0202         title = "{Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs}",
0203         url = "http://www.springerlink.com/content/h68246294j8pr8p3",
0204         volume = "4110",
0205         year = "2006"
0206 }
0207 
0208 @inproceedings{ASY05_formation_problems,
0209         author = "Ando, H. and Suzuki, Ichiro and Yamashita, Masafumi",
0210         doi = "10.1109/ISIC.1995.525098",
0211         journal = "Intelligent Control, 1995., Proceedings of the 1995 IEEE International Symposium on",
0212         keywords = "agreement problems; correctness proofs; formation problems; limited visibility; mobile processor; synchronous mobile robots; distributed control; graph theory; mobile robots; path planning",
0213         month = "August",
0214         owner = "phoenixx",
0215         pages = "453–460",
0216         timestamp = "2010.10.09",
0217         title = "{Formation and agreement problems for synchronous mobile robots with limited visibility}",
0218         year = "1995"
0219 }
0220 
0221 @article{BMP05_performance_compare_protocols_for_clustering_and_backbone_ad_hoc_nets,
0222         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.},
0223         author = "Basagni, S. and Mastrogiovanni, M. and Panconesi, A. and Petrioli, C.",
0224         doi = "10.1109/TPDS.2006.52",
0225         file = "Full Article (IEEE):/home/phoenixx/Studium/MasterThesis/mastercola/papers/BMP06\_performance\_compare\_protocols\_for\_clustering\_and\_backbone\_ad\_hoc\_nets.pdf:PDF",
0226         issn = "1045-9219",
0227         journal = "Parallel and Distributed Systems, IEEE Transactions on",
0228         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",
0229         month = "April",
0230         number = "4",
0231         owner = "phoenixx",
0232         pages = "292–306",
0233         timestamp = "2010.10.11",
0234         title = "{Localized protocols for ad hoc clustering and backbone formation: a performance comparison}",
0235         volume = "17",
0236         year = "2006"
0237 }
0238 
0239 @inproceedings{BEKLPR09_SINR_diagrams,
0240         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.",
0241         author = "Ben, Chen Avin and Emek, Yuval and Kantor, Erez and Lotker, Zvi and Peleg, David and Roditty, Liam",
0242         booktitle = "{Annual ACM Symposium on Principles of Distributed Computing Proceedings of the 28th ACM symposium on Principles of distributed computing}",
0243         doi = "10.1145/1582716.1582750",
0244         file = "Full Paper:/home/phoenixx/Studium/MasterThesis/mastercola/papers/p200-avin.pdf:PDF",
0245         owner = "phoenixx",
0246         pages = "200–209",
0247         publisher = "ACM New York, NY, USA",
0248         review = "Bastian meinte, dass ich mir hier die Modellierungen für unebene Gelände anschauen sollte.",
0249         timestamp = "2010.04.19",
0250         title = "{SINR diagrams: towards algorithmically usable SINR models of wireless networks}",
0251         year = "2009"
0252 }
0253 
0254 @inproceedings{BBKS00_mobility_facility_location,
0255         address = "New York, NY, USA",
0256         author = "Bespamyatnikh, S. and Bhattacharya, B. and Kirkpatrick, D. and Segal, M.",
0257         booktitle = "{DIALM '00: Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications}",
0258         doi = "10.1145/345848.345858",
0259         file = "Full Article (ACM Portal):/home/phoenixx/Studium/MasterThesis/mastercola/papers/BBKM00\_mobilr\_facility\_location.pdf:PDF",
0260         isbn = "1-58113-301-4",
0261         location = "Boston, Massachusetts, United States",
0262         owner = "phoenixx",
0263         pages = "46–53",
0264         publisher = "ACM",
0265         timestamp = "2010.10.05",
0266         title = "{Mobile facility location (extended abstract)}",
0267         year = "2000"
0268 }
0269 
0270 @inproceedings{BT10_parallel_approx_algos_for_flp,
0271         __markedentry = "[phoenixx]",
0272         address = "New York, NY, USA",
0273         author = "Blelloch, Guy E. and Tangwongsan, Kanat",
0274         booktitle = "{SPAA '10: Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures}",
0275         doi = "10.1145/1810479.1810535",
0276         isbn = "978-1-4503-0079-7",
0277         localfile = "archive/BT10_parallel_approx_algos_for_flp.pdf",
0278         location = "Thira, Santorini, Greece",
0279         owner = "phoenixx",
0280         pages = "315–324",
0281         publisher = "ACM",
0282         timestamp = "2010.10.13",
0283         title = "{Parallel approximation algorithms for facility-location problems}",
0284         year = "2010"
0285 }
0286 
0287 @incollection{BCIS05_facility_location_sublinear_time,
0288         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.",
0289         author = "Bădoiu, Mihai and Czumaj, Artur and Indyk, Piotr and Sohler, Christian",
0290         booktitle = "{Automata, Languages and Programming}",
0291         doi = "10.1007/11523468",
0292         editor = "et al., L. Caires",
0293         file = "Full Chapter:/home/phoenixx/Studium/MasterThesis/mastercola/papers/BCIS05\_facility\_location\_sublinear\_time.pdf:PDF",
0294         note = "ISSN 0302-9743 (Print) 1611-3349 (Online) ISBN 978-3-540-27580-0",
0295         owner = "phoenixx",
0296         pages = "866–877",
0297         publisher = "Springer Berlin / Heidelberg",
0298         series = "{Lecture Notes in Computer Science}",
0299         timestamp = "2010.03.06",
0300         title = "{Facility Location in Sublinear Time}",
0301         url = "http://www.springerlink.com/content/22qfq41ftupd0wd6",
0302         volume = "3580/2005",
0303         year = "2005"
0304 }
0305 
0306 @incollection{C98_improved_approximation_algorithms_for_uncap_flp,
0307         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.",
0308         affiliation = "Cornell University School of Operations Research \& Industrial Engineering Ithaca NY 14853 USA",
0309         author = "Chudak, Fabián",
0310         booktitle = "{Integer Programming and Combinatorial Optimization}",
0311         editor = "Bixby, Robert and Boyd, E. and Ríos-Mercado, Roger",
0312         owner = "phoenixx",
0313         pages = "180–194",
0314         publisher = "Springer Berlin / Heidelberg",
0315         series = "{Lecture Notes in Computer Science}",
0316         timestamp = "2010.10.12",
0317         title = "{Improved Approximation Algorithms for Uncapacitated Facility Location}",
0318         url = "http://dx.doi.org/10.1007/3-540-69346-7_14",
0319         volume = "1412",
0320         year = "1998"
0321 }
0322 
0323 @incollection{CS99_improved_approximation_algorithms_for_cap_flp,
0324         address = "Baltimore, Md.",
0325         affiliation = "Cornell University School of Operations Research \& Industrial Engineering Ithaca NY 14853 USA",
0326         author = "Chudak, Fabián and Shmoys, David B.",
0327         booktitle = "{Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms}",
0328         month = "Jan. 17–19",
0329         owner = "phoenixx",
0330         pages = "875–876",
0331         publisher = "ACM New York, NY, USA",
0332         timestamp = "2010.10.12",
0333         title = "{Improved Approximation Algorithms for the Capacitated Facility Location}",
0334         year = "1999"
0335 }
0336 
0337 @incollection{CFPS03_solving_robots_gathering_problem,
0338         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.",
0339         affiliation = "ETH Zurich Zurich",
0340         author = "Cieliebak, Mark and Flocchini, Paola and Prencipe, Giuseppe and Santoro, Nicola",
0341         booktitle = "{Automata, Languages and Programming}",
0342         editor = "Baeten, Jos and Lenstra, Jan and Parrow, Joachim and Woeginger, Gerhard",
0343         file = "Springer Article:/home/phoenixx/Studium/MasterThesis/mastercola/papers/CFPS03\_solving\_robots\_gathering\_problem.pdf:PDF",
0344         owner = "phoenixx",
0345         pages = "1181–1196",
0346         publisher = "Springer Berlin / Heidelberg",
0347         series = "{Lecture Notes in Computer Science}",
0348         timestamp = "2010.08.22",
0349         title = "{Solving the Robots Gathering Problem}",
0350         url = "http://dx.doi.org/10.1007/3-540-45061-0_90",
0351         volume = "2719",
0352         year = "2003"
0353 }
0354 
0355 @article{CCJ90_udg,
0356         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.",
0357         author = "Clark, Brent N. and Colbourn, Charles J. and Johnson, David S.",
0358         doi = "10.1016/0012-365X(90)90358-O",
0359         file = "/home/phoenixx/Studium/MasterThesis/mastercola/papers/CCJ90\_udg.pdf",
0360         issn = "0012-365X",
0361         journal = "Discrete Mathematics",
0362         localfile = "/home/phoenixx/Studium/MasterThesis/mastercola/papers/CCJ90_udg.pdf",
0363         number = "1–3",
0364         owner = "phoenixx",
0365         pages = "165–177",
0366         timestamp = "2010.09.04",
0367         title = "{Unit disk graphs}",
0368         url = "http://www.sciencedirect.com/science/article/B6V00-45GN4W9-K/2/1ac54dd6410c091d3594a2282aa4c7d3",
0369         volume = "86",
0370         year = "1990"
0371 }
0372 
0373 @article{COG05_journal,
0374         author = "Cohen, Reuven and Peleg, David",
0375         doi = "10.1137/S0097539704446475",
0376         journal = "SIAM Journal on Computing",
0377         keywords = "robot swarms; autonomous mobile robots; convergence",
0378         number = "6",
0379         owner = "phoenixx",
0380         pages = "1516–1528",
0381         publisher = "SIAM",
0382         review = "Cohen/Peleg Journal Version, beides, zudem asynchrones UMmin (Konvergenz + Konvergenzgeschwindigkeit)",
0383         timestamp = "2010.08.22",
0384         title = "{Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems}",
0385         url = "http://link.aip.org/link/?SMJ/34/1516/1",
0386         volume = "34",
0387         year = "2005"
0388 }
0389 
0390 @incollection{CGP06_gathering_few_fat_robots,
0391         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.",
0392         affiliation = "Département d’informatique, Université du Québec en Outaouais, Gatineau, Québec J8X 3X7 Canada Canada",
0393         author = "Czyzowicz, Jurek and Gasieniec, Leszek and Pelc, Andrzej",
0394         booktitle = "{Principles of Distributed Systems}",
0395         editor = "Shvartsman, Alexander",
0396         owner = "phoenixx",
0397         pages = "350–364",
0398         publisher = "Springer Berlin / Heidelberg",
0399         series = "{Lecture Notes in Computer Science}",
0400         timestamp = "2010.10.08",
0401         title = "{Gathering Few Fat Mobile Robots in the Plane}",
0402         url = "http://dx.doi.org/10.1007/11945529_25",
0403         volume = "4305",
0404         year = "2006"
0405 }
0406 
0407 @article{DGL10_Kinetic-Facility-Location,
0408         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.",
0409         address = "Secaucus, NJ, USA",
0410         author = "Degener, Bastian and Gehweiler, Joachim and Lammersen, Christiane",
0411         doi = "10.1007/s00453-008-9250-7",
0412         file = "Journal Article:/home/phoenixx/Studium/MasterThesis/DGL08\_Kinetic-Facility-Location.pdf:PDF",
0413         journal = "Algorithmica",
0414         keywords = "facility location; kinetic data structure; approximation algorithm; deterministic algorithm",
0415         month = "July",
0416         number = "3",
0417         owner = "phoenixx",
0418         pages = "562–584",
0419         publisher = "Springer-Verlag New York, Inc.",
0420         timestamp = "2010.03.02",
0421         title = "{Kinetic Facility Location}",
0422         url = "http://www.springerlink.com/content/341q657424x70uq2",
0423         volume = "57",
0424         year = "2010"
0425 }
0426 
0427 @inproceedings{DGL08_Kinetic-Facility-Location,
0428         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.",
0429         address = "Berlin, Heidelberg",
0430         author = "Degener, Bastian and Gehweiler, Joachim and Lammersen, Christiane",
0431         booktitle = "{SWAT '08: Proceedings of the 11th Scandinavian workshop on Algorithm Theory}",
0432         doi = "10.1007/978-3-540-69903-3_34",
0433         file = "Journal Article:/home/phoenixx/Studium/MasterThesis/DGL08\_Kinetic-Facility-Location.pdf:PDF",
0434         journal = "Algorithmica",
0435         keywords = "facility location; kinetic data structure; Approximation algorithm; Deterministic algorithm",
0436         owner = "phoenixx",
0437         pages = "378–389",
0438         publisher = "Springer-Verlag",
0439         timestamp = "2010.03.02",
0440         title = "{The Kinetic Facility Location}",
0441         year = "2008"
0442 }
0443 
0444 @inproceedings{DKM10_local_o2_gathering,
0445         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.",
0446         address = "New York, NY, USA",
0447         author = "Degener, Bastian and Kempkes, Barbara and {Meyer auf der Heide}, Friedhelm",
0448         booktitle = "{SPAA '10: Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures}",
0449         doi = "10.1145/1810479.1810523",
0450         file = "Full Article ACM Portal:/home/phoenixx/Studium/MasterThesis/mastercola/papers/DKM10_local_n2_gathering_algo.pdf:PDF",
0451         isbn = "978-1-4503-0079-7",
0452         location = "Thira, Santorini, Greece",
0453         pages = "217–223",
0454         publisher = "ACM",
0455         review = "Round model is same as DKP10",
0456         title = "{A local O($n^2$) gathering algorithm}",
0457         url = "http://portal.acm.org/citation.cfm?id=1810479.1810523",
0458         year = "2010"
0459 }
0460 
0461 @inproceedings{FR07_distr_flp_for_flex_wlansensors,
0462         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.",
0463         address = "Berlin, Heidelberg",
0464         author = "Frank, Christian and Römer, Kay",
0465         booktitle = "{DCOSS'07: Proceedings of the 3rd IEEE international conference on Distributed computing in sensor systems}",
0466         file = "Full Paper ACM Portal:/home/phoenixx/Studium/MasterThesis/mastercola/papers/FR07_distr_flp_for_flex_wlansensors.pdf:PDF",
0467         isbn = "978-3-540-73089-7",
0468         location = "Santa Fe, NM, USA",
0469         owner = "phoenixx",
0470         pages = "124–141",
0471         publisher = "Springer-Verlag",
0472         timestamp = "2010.09.02",
0473         title = "{Distributed facility location algorithms for flexible configuration of wireless sensor networks}",
0474         url = "http://portal.acm.org/citation.cfm?id=1769096",
0475         year = "2007"
0476 }
0477 
0478 @inproceedings{GLS06-distr-approx-uniform-location,
0479         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.",
0480         address = "New York, NY, USA",
0481         author = "Gehweiler, Joachim and Lammersen, Christiane and Sohler, Christian",
0482         booktitle = "{SPAA '06: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures}",
0483         doi = "10.1145/1148109.1148152",
0484         file = "Conference Paper:/home/phoenixx/Studium/MasterThesis/GLS06\_distributed_algo_facility_location_problem.pdf:PDF",
0485         journal = "Electronic Notes in Discrete Matehamatics",
0486         keywords = "facility location; distribued approximation; randomized algorithm",
0487         owner = "phoenixx",
0488         pages = "237–243",
0489         publisher = "ACM",
0490         review = "* Bounded message size to log(n) * 3 communication rounds * only uniform facility location problem * also for powers of metrics",
0491         timestamp = "2010.02.28",
0492         title = "{A distributed O(1)-approximation algorithm for the uniform facility location problem}",
0493         url = "http://portal.acm.org/citation.cfm?id=1148109.1148152",
0494         volume = "25",
0495         year = "2006"
0496 }
0497 
0498 @inproceedings{GK98_greedy_strikes_back,
0499         address = "Philadelphia, PA, USA",
0500         author = "Guha, Sudipto and Khuller, Samir",
0501         booktitle = "{SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms}",
0502         file = "Full Text:/home/phoenixx/Studium/MasterThesis/mastercola/papers/p649-guha\_greedy_strikes_back.pdf:PDF",
0503         owner = "phoenixx",
0504         pages = "649–657",
0505         publisher = "Society for Industrial and Applied Mathematics",
0506         timestamp = "2010.04.28",
0507         title = "{Greedy strikes back: improved facility location algorithms}",
0508         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",
0509         year = "1998"
0510 }
0511 
0512 @article{HBF08_kinetic_mobility_mgmt_ad_hoc_nets,
0513         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.",
0514         author = "Härri, Jérôme and Bonnet, Christian and Filali, Fethi",
0515         doi = "10.1016/j.comcom.2008.01.060",
0516         file = "Full Paper:/home/phoenixx/Studium/MasterThesis/mastercola/papers/HBF08\_kinetic_mobility_management_on_ad_hoc_nets.pdf:PDF",
0517         issn = "0140-3664",
0518         journal = "Computer Communications",
0519         keywords = "Reactive mobility management",
0520         note = "Mobility Protocols for ITS/VANET",
0521         number = "12",
0522         pages = "2907–2924",
0523         title = "{Kinetic mobility management applied to vehicular ad hoc network protocols}",
0524         url = "http://www.sciencedirect.com/science/article/B6TYP-4RSYC9K-1/2/6184d66ad7a0e5537a92b86973455d55",
0525         volume = "31",
0526         year = "2008"
0527 }
0528 
0529 @article{03jmmav_greedy_flp_using_duals,
0530         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.",
0531         author = "Jain, Kamal and Mahdian, Mohammad and Markakis, Evangelos and Saberi, Amin and Vazirani, Vijay V.",
0532         doi = "10.1145/950620.950621",
0533         file = "Full Article:/home/phoenixx/Studium/MasterThesis/mastercola/papers/03jmms_greedy_p795-jain.pdf:PDF",
0534         journal = "Journal of the ACM (JACM)",
0535         month = "November",
0536         note = "ISSN:0004-5411",
0537         number = "6",
0538         owner = "phoenixx",
0539         pages = "795–824",
0540         timestamp = "2010.07.21",
0541         title = "{Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP}",
0542         url = "http://portal.acm.org/citation.cfm?id=950621",
0543         volume = "50",
0544         year = "2003"
0545 }
0546 
0547 @article{JMMSV03_greedy_flp_using_dual_fitting_with_factor-revealing_lp,
0548         address = "New York, NY, USA",
0549         author = "Jain, Kamal and Mahdian, Mohammad and Markakis, Evangelos and Saberi, Amin and Vazirani, Vijay V.",
0550         doi = "10.1145/950620.950621",
0551         file = "Full Article (Portal ACM):/home/phoenixx/Studium/MasterThesis/mastercola/papers/JMMSV03_greedy_flp_using_dual_fitting_with_factor-revealing_lp.pdf:PDF",
0552         issn = "0004-5411",
0553         journal = "Journal of the ACM (JACM)",
0554         number = "6",
0555         owner = "phoenixx",
0556         pages = "795–824",
0557         publisher = "ACM",
0558         timestamp = "2010.10.13",
0559         title = "{Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP}",
0560         volume = "50",
0561         year = "2003"
0562 }
0563 
0564 @article{JV01_primal_dual_metric_flp,
0565         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.",
0566         author = "Jain, Kamal and Vazirani, Vijay V.",
0567         comment = "ISSN:0004-5411",
0568         doi = "10.1145/375827.375845",
0569         file = "Journal Version of Jain and Vazirani Paper:/home/phoenixx/Studium/MasterThesis/mastercola/papers/JV01\_journal.pdf:PDF",
0570         journal = "Journal of the ACM (JACM)",
0571         owner = "phoenixx",
0572         pages = "274–296",
0573         timestamp = "2010.07.10",
0574         title = "{Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation}",
0575         url = "http://portal.acm.org/citation.cfm?id=375827.375845",
0576         volume = "48",
0577         year = "2001"
0578 }
0579 
0580 @book{KW05_sensor_networks,
0581         author = "Karl, Holger and Willig, Andreas",
0582         owner = "phoenixx",
0583         publisher = "Wiley",
0584         timestamp = "2010.10.11",
0585         title = "{Protocols and Architectures for Wireless Sensor Networks}",
0586         year = "2007"
0587 }
0588 
0589 @article{KPR98_microeconomic_view_of_datamining,
0590         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.",
0591         author = "Kleinberg, Jon and Papadimitriou, Christos and Raghavan, Prabhakar",
0592         issn = "1384-5810",
0593         journal = "Data Mining and Knowledge Discovery",
0594         keyword = "Computer Science",
0595         note = "10.1023/A:1009726428407",
0596         number = "4",
0597         owner = "phoenixx",
0598         pages = "311–324",
0599         publisher = "Springer Netherlands",
0600         timestamp = "2010.10.04",
0601         title = "{A Microeconomic View of Data Mining}",
0602         url = "http://dx.doi.org/10.1023/A:1009726428407",
0603         volume = "2",
0604         year = "1998"
0605 }
0606 
0607 @article{KH63_heuristic_program_for_locating_warehouses,
0608         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.",
0609         author = "Kuehn, Alfred A. and Hamburger, Michael J.",
0610         copyright = "Copyright © 1963 INFORMS",
0611         issn = "00251909",
0612         journal = "Management Science",
0613         jstor_articletype = "research-article",
0614         jstor_formatteddate = "Jul., 1963",
0615         language = "English",
0616         number = "4",
0617         owner = "phoenixx",
0618         pages = "643–666",
0619         publisher = "INFORMS",
0620         timestamp = "2010.10.12",
0621         title = "{A Heuristic Program for Locating Warehouses}",
0622         url = "http://www.jstor.org/stable/2627368",
0623         volume = "9",
0624         year = "1963"
0625 }
0626 
0627 @inproceedings{KWZ03_ad-hoc_networks_beyond_unit-disk-graphs,
0628         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.",
0629         address = "New York, NY, USA",
0630         author = "Kuhn, Fabian and Wattenhofer, Roger and Zollinger, Aaron",
0631         booktitle = "{DIALM-POMC '03: Proceedings of the 2003 joint workshop on Foundations of mobile computing}",
0632         doi = "10.1145/941079.941089",
0633         isbn = "1-58113-765-6",
0634         location = "San Diego, CA, USA",
0635         pages = "69–78",
0636         publisher = "ACM",
0637         review = "This is the initial work on quasi-UDGs.",
0638         title = "{Ad-hoc networks beyond unit disk graphs}",
0639         url = "http://portal.acm.org/citation.cfm?id=941089&dl=GUIDE,&coll=GUIDE&CFID=100300923&CFTOKEN=55730014",
0640         year = "2003"
0641 }
0642 
0643 @article{MFHH02_tiny_aggregation_service_for_ad-hoc_nets,
0644         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.",
0645         address = "New York, NY, USA",
0646         author = "Madden, Samuel and Franklin, Michael J. and Hellerstein, Joseph M. and Hong, Wei",
0647         doi = "10.1145/844128.844142",
0648         issn = "0163-5980",
0649         journal = "SIGOPS Oper. Syst. Rev.",
0650         number = "SI",
0651         owner = "phoenixx",
0652         pages = "131–146",
0653         publisher = "ACM",
0654         timestamp = "2010.10.11",
0655         title = "{TAG: a Tiny AGgregation service for ad-hoc sensor networks}",
0656         volume = "36",
0657         year = "2002"
0658 }
0659 
0660 @inproceedings{MP00_online_median_problem,
0661         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.",
0662         address = "Washington, DC, USA",
0663         author = "Mettu, Ramgopal R. and Plaxton, C. Greg",
0664         booktitle = "{Proceedings of the 41st Annual Symposium on Foundations of Computer Science}",
0665         citeseerurl = "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.128.4386",
0666         comment = "ISBN: 0-7695-0850-2",
0667         doi = "10.1109/SFCS.2000.892122",
0668         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",
0669         month = "November",
0670         organization = "FOCS",
0671         owner = "phoenixx",
0672         pages = "pp. 339",
0673         publisher = "IEEE Computer Society",
0674         timestamp = "2010.03.08",
0675         title = "{The Online Median Problem}",
0676         url = "http://www.computer.org/portal/web/csdl/abs/proceedings/focs/2000/0850/00/08500339abs.htm",
0677         year = "2000"
0678 }
0679 
0680 @inproceedings{PP09_finding_facilities_fast,
0681         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.",
0682         address = "Berlin, Heidelberg",
0683         author = "Pandit, Saurav and Pemmaraju, Sriram V.",
0684         booktitle = "{ICDCN '09: Proceedings of the 10th International Conference on Distributed Computing and Networking}",
0685         doi = "10.1007/978-3-540-92295-7_5",
0686         isbn = "978-3-540-92294-0",
0687         location = "Hyderabad, India",
0688         pages = "11–24",
0689         publisher = "Springer-Verlag",
0690         series = "{Lecture Notes in Computer Science}",
0691         title = "{Finding Facilities Fast}",
0692         url = "http://www.springerlink.com/content/c2237kh3v339g77w",
0693         volume = "5408",
0694         year = "2009"
0695 }
0696 
0697 @book{P00_book_distributed_computing,
0698         address = "Philadelphia",
0699         author = "Peleg, David",
0700         editor = "Hammer, Peter L.",
0701         owner = "phoenixx",
0702         publisher = "Society for Industrial and Applied Mathematics (SIAM)",
0703         series = "{SIAM Monographs on Discrete Mathematics and Applications}",
0704         timestamp = "2010.10.13",
0705         title = "{Distributed Computing: A Locality-Sensitive Approach}",
0706         year = "2000"
0707 }
0708 
0709 @inproceedings{STA97_approx_algorithms_for_flp,
0710         address = "New York, NY, USA",
0711         author = "Shmoys, David B. and Tardos, Éva and Aardal, Karen",
0712         booktitle = "{STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing}",
0713         doi = "10.1145/258533.258600",
0714         isbn = "0-89791-888-6",
0715         location = "El Paso, Texas, United States",
0716         owner = "phoenixx",
0717         pages = "265–274",
0718         publisher = "ACM",
0719         timestamp = "2010.10.12",
0720         title = "{Approximation algorithms for facility location problems (extended abstract)}",
0721         year = "1997"
0722 }
0723 
0724 @article{S63_working_model_for_plant_numbers_and_locations,
0725         author = "Stollsteimer, John F.",
0726         copyright = "Copyright © 1963 Agricultural \& Applied Economics Association",
0727         issn = "10711031",
0728         journal = "Journal of Farm Economics",
0729         jstor_articletype = "research-article",
0730         jstor_formatteddate = "Aug., 1963",
0731         language = "English",
0732         number = "3",
0733         owner = "phoenixx",
0734         pages = "631–645",
0735         publisher = "Blackwell Publishing on behalf of the Agricultural \& Applied Economics Association",
0736         timestamp = "2010.10.12",
0737         title = "{A Working Model for Plant Numbers and Locations}",
0738         url = "http://www.jstor.org/stable/1235442",
0739         volume = "45",
0740         year = "1963"
0741 }
0742 
0743 @article{SY99_distr_robots_geometric_patterns,
0744         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.",
0745         author = "Suzuki, Ichiro and Yamashita, Masafumi",
0746         doi = "10.1137/S009753979628292X",
0747         journal = "SIAM Journal on Computing",
0748         keywords = "distributed algorithms; anonymous robots; mobile robots; multiagent systems; formation of geometric patterns",
0749         number = "4",
0750         owner = "phoenixx",
0751         pages = "1347–1363",
0752         publisher = "SIAM",
0753         review = "This is probably the first definition of the FSYNC time model",
0754         timestamp = "2010.08.22",
0755         title = "{Distributed Anonymous Mobile Robots: Formation of Geometric Patterns}",
0756         url = "http://link.aip.org/link/?SMJ/28/1347/1",
0757         volume = "28",
0758         year = "1999"
0759 }
0760 
0761 @inproceedings{SY96_distr_formation_and_agreement_problem,
0762         address = "Waterloo, ON, Canada",
0763         author = "Suzuki, Ichiro and Yamashita, Masafumi",
0764         booktitle = "{Proceedings of the 3rd Annual Colloquium on Structural Information and Communication Complexity (SIROCCO '96)}",
0765         citeseerurl = "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.3191",
0766         organization = "Carleton Scientific",
0767         pages = "313–330",
0768         review = "Probably first annoucement of SSYNC model!",
0769         title = "{Distributed Anonymous Mobile Robots – Formation and Agreement Problems}",
0770         year = "1996"
0771 }
0772 
0773 @inproceedings{Y00_kmedians_flp_chernoff-wald_bound,
0774         address = "Philadelphia, PA, USA",
0775         author = "Young, Neal E.",
0776         booktitle = "{SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms}",
0777         file = "Full Text:/home/phoenixx/Studium/MasterThesis/mastercola/papers/p86-young.pdf:PDF",
0778         owner = "phoenixx",
0779         pages = "86–95",
0780         publisher = "Society for Industrial and Applied Mathematics",
0781         timestamp = "2010.04.28",
0782         title = "{K-medians, facility location, and the Chernoff-Wald bound}",
0783         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",
0784         year = "2000"
0785 }
0786 
0787 @article{Gon01_JXTA_network_programming_framework,
0788         added-at = "2010-04-06T16:41:10.000+0200",
0789         address = "Piscataway, NJ, USA",
0790         author = "Gong, Li",
0791         doi = "10.1109/4236.935182",
0792         interhash = "4fe36a0a4c007a8356fb9107dd5bc7e4",
0793         intrahash = "28e9d43bf0a7e7bae63091ea60cbaf64",
0794         issn = "1089-7801",
0795         journal = "IEEE Internet Computing",
0796         keywords = "imported",
0797         number = 3,
0798         pages = "88–95",
0799         publisher = "IEEE Educational Activities Department",
0800         title = "{JXTA: A Network Programming Environment}",
0801         url = "http://www.bibsonomy.org/bibtex/228e9d43bf0a7e7bae63091ea60cbaf64/chesteve",
0802         volume = 5,
0803         year = 2001
0804 }
0805 
0806 @inproceedings{EFKR09_online_computation_with_advance,
0807         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 .",
0808         author = "Emek, Yuval and Fraigniaud, Pierre and Korman, Amos and Rosén, Adi",
0809         booktitle = "{Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP)}",
0810         doi = "10.1007/978-3-642-02927-1_36",
0811         issn = "0304-3975",
0812         journal = "Theoretical Computer Science",
0813         keywords = "Online; Competitive Analysis; k-Server Problem; Metrical Task System",
0814         number = "5555",
0815         pages = "427–438",
0816         publisher = "Springer",
0817         series = "{Lecture Notes in Computer Science}",
0818         title = "{Online computation with advice}",
0819         year = "2009"
0820 }
0821 
0822 @incollection{Sch07_principles_of_stochastic_local_search,
0823         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.",
0824         author = "Schöning, Uwe",
0825         booktitle = "{Unconventional Computation}",
0826         doi = "10.1007/978-3-540-73554-0_17",
0827         editor = "Akl, Selim and Calude, Cristian and Dinneen, Michael and Rozenberg, Grzegorz and Wareham, H.",
0828         institution = "Institute of Theoretical Computer Science, Ulm University, 89069 Ulm Germany",
0829         keywords = "local search; stochastic local search; heuristic information; restart; meta-algorithms",
0830         pages = "178–187",
0831         publisher = "Springer Berlin / Heidelberg",
0832         series = "{Lecture Notes in Computer Science}",
0833         title = "{Principles of Stochastic Local Search}",
0834         volume = "4618",
0835         year = "2007"
0836 }
0837 
0838 @article{Jain:1999:DCR:331499.331504,
0839         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.",
0840         acmid = "331504",
0841         address = "New York, NY, USA",
0842         author = "Jain, A. K. and Murty, M. N. and Flynn, P. J.",
0843         doi = "10.1145/331499.331504",
0844         issn = "0360-0300",
0845         issue_date = "Sept. 1999",
0846         journal = "ACM Comput. Surv.",
0847         keywords = "cluster analysis; clustering applications; exploratory data analysis; incremental clustering; similarity indices; unsupervised learning",
0848         month = "September",
0849         number = "3",
0850         numpages = "60",
0851         pages = "264–323",
0852         publisher = "ACM",
0853         title = "{Data clustering: a review}",
0854         url = "http://doi.acm.org/10.1145/331499.331504",
0855         volume = "31",
0856         year = "1999"
0857 }
0858 
0859 @inproceedings{YG98_efficient_search_in_p2p_nets,
0860         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.",
0861         added-at = "2005-12-21T09:35:26.000+0100",
0862         author = "Yang, Beverly and Garcia-Molina, Hector",
0863         booktitle = "{Proc.\ 22nd International Conference on Distributed Computing Systems, 2 - 5 July, 2002, Vienna, Austria}",
0864         interhash = "ab216e9f213b3a0d9499dc77f5188e16",
0865         intrahash = "04fa8a681cbfef5d56a4c9e35ae48745",
0866         keywords = "superpeer p2p Peer-to-peer; distributed data; search, performance modeling; evaluation",
0867         misc = "comment = {Lokal vorhanden}",
0868         organization = "IEEE Computer Society",
0869         title = "{Efficient Search in Peer-to-Peer Networks}",
0870         url = "http://www.bibsonomy.org/bibtex/204fa8a681cbfef5d56a4c9e35ae48745/schmitz",
0871         year = 1998
0872 }
0873 
0874 @article{FBD09_nonneg_matrix_factorization_with_itakura-saito_and_music_application,
0875         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",
0876         author = "Févotte, Cédric and Bertin, Nancy and Durrieu, Jean-Louis",
0877         issn = "08997667",
0878         journal = "Neural Computation",
0879         keywords = "FACTORIZATION method (Quantum theory); GAUSSIAN processes; STATISTICS; ESTIMATION theory; BAYESIAN statistical decision theory; MUSICAL analysis",
0880         localfile = "archive/FBD09_nonneg_matrix_factorization_with_itakura-saito_and_music_application.pdf",
0881         number = "3",
0882         pages = "793–830",
0883         title = "{Nonnegative Matrix Factorization with the Itakura-Saito Divergence: With Application to Music Analysis}",
0884         url = "http://search.ebscohost.com/login.aspx?direct=true&db=pbh&AN=36785201&site=ehost-live",
0885         volume = "21",
0886         year = "2009"
0887 }
0888 
0889 @article{Bregman1967200,
0890         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.",
0891         author = "Bregman, L. M.",
0892         doi = "10.1016/0041-5553(67)90040-7",
0893         issn = "0041-5553",
0894         journal = "USSR Computational Mathematics and Mathematical Physics",
0895         number = "3",
0896         pages = "200–217",
0897         title = "{The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming}",
0898         url = "http://www.sciencedirect.com/science/article/B75BX-49090J9-7T/2/2c1500ce39d60cfcf0d0962cc7df1d19",
0899         volume = "7",
0900         year = "1967"
0901 }
0902 
0903 @book{CZ97_book_parallel-optimization,
0904         author = "Censor, Y. and Zenios, S. A.",
0905         location = "New York",
0906         publisher = "Oxford University Press",
0907         series = "{Numerical Mathematics and Scientific Computation}",
0908         title = "{Parallel Optimization: Theory, Algorithms, and Applications}",
0909         year = "1997"
0910 }
0911 
0912 @article{DBLP:journals/corr/abs-0803-0248,
0913         author = "Chaintreau, Augustin and Fraigniaud, Pierre and Lebhar, Emmanuelle",
0914         bibsource = "DBLP, http://dblp.uni-trier.de",
0915         journal = "CoRR",
0916         localfile = "archive/CFL08_networks_become_navigable_as_nodes_move_and_forget_EXTENDED_ARCHIVE.pdf",
0917         title = "{Networks become navigable as nodes move and forget}",
0918         type = "preprint server version with extended proofs",
0919         url = "http://arxiv.org/abs/0803.0248",
0920         volume = "abs/0803.0248",
0921         year = "2008"
0922 }
0923 
0924 @article{T85_amortized_computational_analysis,
0925         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.},
0926         acknowledgement = ack-nhfb,
0927         author = "Tarjan, Robert Endre",
0928         bibdate = "Sat Apr 11 10:02:33 MDT 1998",
0929         coden = "SJAMDU",
0930         fjournal = "SIAM Journal on Algebraic and Discrete Methods",
0931         issn = "0196-5212",
0932         keywords = "competitive analysis",
0933         localfile = "archive/T85_amortized_computational_complexity.pdf",
0934         mrclass = "68Q15 (68P05)",
0935         mrnumber = "86i:68046",
0936         number = "2",
0937         pages = "306–318",
0938         title = "{Amortized computational complexity}",
0939         volume = "6",
0940         year = "1985"
0941 }
0942 
0943 @article{journals/jacm/Vocking03,
0944         added-at = "2003-11-20T00:00:00.000+0100",
0945         author = "Vöcking, Berthold",
0946         date = "2003-11-20",
0947         description = "dblp",
0948         interhash = "e12acde6641fbd29a2be6282564d7b51",
0949         intrahash = "b4520cb029cfbb218e876fb8014b34cf",
0950         journal = "Journal of the ACM",
0951         keywords = "randomized algorithm; probabilistic analysis; balls and bins process",
0952         localfile = "archive/V03_HowAsymmetryHelpsLoadBalancing.pdf",
0953         number = 4,
0954         pages = "568–589",
0955         title = "{How asymmetry helps load balancing}",
0956         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",
0957         volume = 50,
0958         year = 2003
0959 }
0960 
0961 @inproceedings{KFT10_optimal_gradient_clock_sync,
0962         address = "New York, NY, USA",
0963         author = "Kuhn, Fabian and Lenzen, Christoph and Locher, Tthomas and Oshman, Rotem",
0964         booktitle = "{Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing}",
0965         keywords = "clock synchronization; dynamic networks",
0966         localfile = "archive/KFT10_OptimalGradientClockSynchronizationinDynamicNetworks2010.pdf",
0967         location = "Zurich, Switzerland",
0968         organization = "ACM",
0969         pages = "430–439",
0970         publisher = "ACM",
0971         series = "{PODC '10}",
0972         title = "{Optimal Gradient Clock Synchronization in Dynamic Networks}",
0973         url = "http://dx.doi.org/10.1145/1835698.1835799; http://doi.acm.org/10.1145/1835698.1835799",
0974         year = "2010"
0975 }
0976 
0977 @inproceedings{ORS07_linearization_locally_self_stab_sorting_in_graphs,
0978         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.",
0979         author = "Onus, Melih and Richa, Andrea and Scheideler, Christian",
0980         booktitle = "{Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics}",
0981         editor = "Applegate, David and Brodal, Gerth Stølting and Panario, Daniel and Sedgewic, Robert",
0982         keywords = "Self-Stabilization; Linearization",
0983         localfile = "archive/ORS07_linearization_locally_self_stab_sorting_in_graphs.pdf",
0984         location = "New Orleans, LA",
0985         organization = "SIAM",
0986         series = "{Proceedings in Applied Mathematics}",
0987         title = "{Linearization: Locally self-stabilizing sorting in graphs}",
0988         url = "http://www.siam.org/proceedings/alenex/2007/alenex07.php",
0989         volume = "126",
0990         year = "2007"
0991 }
0992 
0993 @article{IMP11_tutorial_to_local_amortized_onlinescheduling,
0994         address = "New York, NY, USA",
0995         author = "Im, Sungjin and Moseley, Benjamin and Pruhs, Kirk",
0996         doi = "10.1145/1998037.1998058",
0997         issn = "0163-5700",
0998         journal = "SIGACT News",
0999         localfile = "archive/IMP11_tutorial_to_local_amortized_onlinescheduling.pdf",
1000         month = "June",
1001         number = "2",
1002         pages = "83–97",
1003         publisher = "ACM",
1004         title = "{A tutorial on amortized local competitiveness in online scheduling}",
1005         volume = "42",
1006         year = "2011"
1007 }
1008 
1009 @techreport{DBLP:journals/corr/abs-1012-0009,
1010         author = "Casteigts, Arnaud and Flocchini, Paola and Quattrociocchi, Walter and Santoro, Nicola",
1011         localfile = "archive/CFQS11_time-varying-graphs-and-dynamic-networks_TR.pdf",
1012         title = "{Time-Varying Graphs and Dynamic Networks}",
1013         url = "http://arxiv.org/abs/1012.0009v2"
1014 }
1015 
1016 @article{Aldous1991185,
1017         author = "Aldous, David J.",
1018         doi = "10.1016/0304-4149(91)90090-Y",
1019         issn = "0304-4149",
1020         journal = "Stochastic Processes and their Applications",
1021         localfile = "archive/CFL08_networks_become_navigable_as_nodes_move_and_forget.pdf",
1022         number = "2",
1023         pages = "185–193",
1024         title = "{Meeting times for independent Markov chains}",
1025         url = "http://www.sciencedirect.com/science/article/pii/030441499190090Y",
1026         volume = "38",
1027         x-fetchedfrom = "ScienceDirect",
1028         year = "1991"
1029 }
1030 
1031 @article{Bshouty1999259,
1032         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).",
1033         author = "Bshouty, Nader H. and Higham, Lisa and Warpechowska-Gruca, Jolanta",
1034         doi = "10.1016/S0020-0190(99)00017-4",
1035         issn = "0020-0190",
1036         journal = "Information Processing Letters",
1037         keywords = "distributed computing; analysis of algorithms; random walks; meeting time; hitting time",
1038         localfile = "archive/BHW99_meeting-times-of-random-walks-on-graphs.pdf",
1039         number = "5",
1040         pages = "259–265",
1041         title = "{Meeting times of random walks on graphs}",
1042         url = "http://www.sciencedirect.com/science/article/pii/S0020019099000174",
1043         volume = "69",
1044         year = "1999"
1045 }
1046 
1047 @article{cooper2009multiple,
1048         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.",
1049         author = "Cooper, Colin and Frieze, Alan and Radzik, Tomasz",
1050         booktitle = "{SIAM Journal on Discrete Mathematics }",
1051         issn = "08954801",
1052         journal = "Preprint",
1053         keywords = "multiple walks; random regular graphs; random walks; cover time",
1054         localfile = "archive/CFR09_multiple-random-walks-in-random-regular-graphs.pdf",
1055         number = "4",
1056         pages = "1738–1761",
1057         publisher = "SIAM",
1058         title = "{Multiple random walks in random regular graphs}",
1059         url = "http://dx.doi.org/10.1137/080729542",
1060         volume = "23",
1061         x-fetchedfrom = "Google Scholar",
1062         year = "2009"
1063 }
1064 
1065 @article{lovász1993random,
1066         author = "Lovász, Láslo",
1067         journal = "Combinatorics, Paul Erdos is Eighty",
1068         localfile = "archive/L93_random-walks-a-survey.pdf",
1069         number = "1",
1070         pages = "1–46",
1071         publisher = "János Bolyai Mathematical Society",
1072         title = "{Random walks on graphs: A survey}",
1073         volume = "2",
1074         x-fetchedfrom = "Google Scholar",
1075         year = "1993"
1076 }
1077 
1078 @inproceedings{Pettie:2010:AFM:1873601.1873719,
1079         acmid = "1873719",
1080         address = "Philadelphia, PA, USA",
1081         author = "Pettie, Seth",
1082         booktitle = "{Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms}",
1083         isbn = "978-0-898716-98-6",
1084         localfile = "archive/P10_applications-of-forbidden-01-matrices-to-search-tree-and-path-compression-based-data-structures.pdf",
1085         location = "Austin, Texas",
1086         numpages = "11",
1087         pages = "1457–1467",
1088         publisher = "Society for Industrial and Applied Mathematics",
1089         series = "{SODA '10}",
1090         title = "{Applications of forbidden 0-1 matrices to search tree and path compression-based data structures}",
1091         url = "http://portal.acm.org/citation.cfm?id=1873601.1873719",
1092         year = "2010"
1093 }
1094 
1095 @article{coppersmith1993collisions,
1096         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.},
1097         author = "Coppersmith, Don and Tetali, Prasad and Winkler, Peter",
1098         booktitle = "{SIAM Journal on Discrete Mathematics }",
1099         journal = "SIAM Journal on Discrete Mathematics",
1100         keywords = "random walks; graph; Markov chain; collision; token management",
1101         localfile = "archive/CTW93_collisions-among-random-walks-on-a-graph.pdf",
1102         month = "August",
1103         number = "3",
1104         pages = "363–374",
1105         publisher = "Society for Industrial and Applied Mathematics",
1106         title = "{Collisions among random walks on a graph}",
1107         url = "http://dx.doi.org/10.1137/0406029",
1108         volume = "6",
1109         x-fetchedfrom = "Google Scholar",
1110         year = "1993"
1111 }
1112 
1113 @inproceedings{ADHL10_basic-netwok-creation-games,
1114         acmid = "1810502",
1115         address = "New York, NY, USA",
1116         author = "Alon, Noga and Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Leighton, Tom",
1117         booktitle = "{Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures}",
1118         doi = "10.1145/1810479.1810502",
1119         isbn = "978-1-4503-0079-7",
1120         keywords = "nash equilibrium; network design; price of anarchy; routing",
1121         localfile = "archive/ADHL10_basic-network-creation-games.pdf",
1122         location = "Thira, Santorini, Greece",
1123         numpages = "8",
1124         pages = "106–113",
1125         publisher = "ACM",
1126         series = "{SPAA '10}",
1127         title = "{Basic network creation games}",
1128         url = "http://doi.acm.org/10.1145/1810479.1810502",
1129         x-fetchedfrom = "ACM Digital Library",
1130         year = "2010"
1131 }
1132 
1133 @inproceedings{FLMPS03_on-a-network-creation-game,
1134         acmid = "872088",
1135         address = "New York, NY, USA",
1136         author = "Fabrikant, Alex and Luthra, Ankur and Maneva, Elitza and Papadimitriou, Christos H. and Shenker, Scott",
1137         booktitle = "{Proceedings of the twenty-second annual symposium on Principles of distributed computing}",
1138         doi = "10.1145/872035.872088",
1139         isbn = "1-58113-708-7",
1140         keywords = "nash equilibrium; distributed network design; game-theoretic models; price of anarchy",
1141         localfile = "archive/FLMPS03_on-a-network-creation-game.pdf",
1142         location = "Boston, Massachusetts",
1143         numpages = "5",
1144         pages = "347–351",
1145         publisher = "ACM",
1146         series = "{PODC '03}",
1147         title = "{On a network creation game}",
1148         url = "http://doi.acm.org/10.1145/872035.872088",
1149         x-fetchedfrom = "ACM Digital Library",
1150         year = "2003"
1151 }
1152 
1153 @inproceedings{Mehler:2009:POF:1583991.1584072,
1154         acmid = "1584072",
1155         address = "New York, NY, USA",
1156         author = "Mehler, Jan and auf der Heide, Friedhelm Meyer",
1157         booktitle = "{Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures}",
1158         doi = "10.1145/1583991.1584072",
1159         isbn = "978-1-60558-606-9",
1160         keywords = "amortized analysis; file allocation; mobile ad hoc networks; online algorithms",
1161         localfile = "archive/MMadH09_power-aware-online-file-allocation-in-mobile-adhoc.pdf",
1162         location = "Calgary, AB, Canada",
1163         numpages = "10",
1164         pages = "347–356",
1165         publisher = "ACM",
1166         series = "{SPAA '09}",
1167         title = "{Power-aware online file allocation in mobile ad hoc networks}",
1168         url = "http://doi.acm.org/10.1145/1583991.1584072",
1169         year = "2009"
1170 }
1171 
1172 @article{Bienkowski2009545,
1173         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.",
1174         author = "Bienkowski, Marcin and Byrka, Jaroslaw and Korzeniowski, Miroslaw and auf der Heide, Friedhelm Meyer",
1175         doi = "10.1016/j.jda.2008.07.006",
1176         issn = "1570-8667",
1177         journal = "Journal of Discrete Algorithms",
1178         keywords = "online algorithms; randomized algorithm; page migration; data management; dynamic networks",
1179         localfile = "archive/BBKMadH09_optimal-algorithms-for-page-migration-in-dynamic-networks.pdf",
1180         number = "4",
1181         pages = "545–569",
1182         title = "{Optimal algorithms for page migration in dynamic networks}",
1183         url = "http://www.sciencedirect.com/science/article/pii/S1570866708000518",
1184         volume = "7",
1185         year = "2009"
1186 }
1187 
1188 @incollection{springerlink:10.1007/978-3-642-22012-8_7,
1189         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.",
1190         affiliation = "Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel",
1191         author = "Chechik, Shiri",
1192         booktitle = "{Automata, Languages and Programming}",
1193         editor = "Aceto, Luca and Henzinger, Monika and Sgall, Jirí",
1194         keywords = "routing scheme; fault tolerant; tree cover",
1195         localfile = "archive/C11_fault-tolerant-routing-schemes-for-general-graphs.pdf",
1196         note = "10.1007/978-3-642-22012-8\_7",
1197         pages = "101–112",
1198         publisher = "Springer Berlin / Heidelberg",
1199         series = "{Lecture Notes in Computer Science}",
1200         title = "{Fault-Tolerant Compact Routing Schemes for General Graphs}",
1201         url = "http://dx.doi.org/10.1007/978-3-642-22012-8_7",
1202         volume = "6756",
1203         year = "2011"
1204 }
1205 
1206 @inproceedings{ieee1357018,
1207         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.",
1208         arnumber = "1357018",
1209         author = "Chun, Byung-Gon and Fonseca, R. and Stoica, I. and Kubiatowicz, J.",
1210         booktitle = "{INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies}",
1211         doi = "10.1109/INFCOM.2004.1357018",
1212         issn = "0743-166X",
1213         keywords = "Nash equilibrium graph; network construction game; overlay routing network; graph theory; telecommunication links; telecommunication network routing; telecommunication network topology",
1214         localfile = "archive/CFSK04_characterizing-selfishly-constructed-overlay-routing-networks.pdf",
1215         month = "march",
1216         pages = "1329–1339 vol.2",
1217         title = "{Characterizing selfishly constructed overlay routing networks}",
1218         volume = "2",
1219         x-fetchedfrom = "IEEEXplore",
1220         year = "2004"
1221 }
1222 
1223 @inproceedings{Moscibroda:2006:TFS:1146381.1146403,
1224         acmid = "1146403",
1225         address = "New York, NY, USA",
1226         author = "Moscibroda, Thomas and Schmid, Stefan and Wattenhofer, Roger",
1227         booktitle = "{Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing}",
1228         doi = "10.1145/1146381.1146403",
1229         isbn = "1-59593-384-0",
1230         keywords = "NP-hardness; game theory; network creation",
1231         localfile = "archive/MSW06_on-the-topologies-formed-by-selfish-peers.pdf",
1232         location = "Denver, Colorado, USA",
1233         numpages = "10",
1234         pages = "133–142",
1235         publisher = "ACM",
1236         series = "{PODC '06}",
1237         title = "{On the Topologies Formed by Selfish Peers}",
1238         url = "http://doi.acm.org/10.1145/1146381.1146403",
1239         x-fetchedfrom = "ACM Digital Library",
1240         year = "2006"
1241 }
1242 
1243 @incollection{CLDF11_a-new-approach-for-analyzing-convergence-problems,
1244         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.",
1245         affiliation = "Heinz Nixdorf Institute \& Department of Computer Science, University of Paderborn, Germany",
1246         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",
1247         booktitle = "{Automata, Languages and Programming}",
1248         editor = "Aceto, Luca and Henzinger, Monika and Sgall, Jirí",
1249         localfile = "archive/CLDF11_a-new-approach-for-analyzing-convergence-problems.pdf",
1250         note = "10.1007/978-3-642-22012-8\_52",
1251         pages = "650–661",
1252         publisher = "Springer Berlin / Heidelberg",
1253         series = "{Lecture Notes in Computer Science}",
1254         title = "{A New Approach for Analyzing Convergence Algorithms for Mobile Robots}",
1255         url = "http://dx.doi.org/10.1007/978-3-642-22012-8_52",
1256         volume = "6756",
1257         year = "2011"
1258 }
1259 
1260 @incollection{springerlink:10.1007/978-3-642-18381-2_15,
1261         affiliation = "Heinz Nixdorf Institute, Computer Science Department, University of Paderborn",
1262         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",
1263         booktitle = "{SOFSEM 2011: Theory and Practice of Computer Science}",
1264         doi = "10.1007/978-3-642-18381-2_15",
1265         editor = "Cerná, Ivana and Gyimóthy, Tibor and Hromkovic, Juraj and Jefferey, Keith and Královic, Rastislav and Vukolic, Marko and Wolf, Stefan",
1266         isbn = "",
1267         pages = "178–189",
1268         publisher = "Springer Berlin / Heidelberg",
1269         series = "{Lecture Notes in Computer Science}",
1270         title = "{Collisionless Gathering of Robots with an Extent}",
1271         url = "http://dx.doi.org/10.1007/978-3-642-18381-2_15",
1272         volume = "6543",
1273         x-fetchedfrom = "SpringerLink",
1274         year = "2011"
1275 }
1276 
1277 @inproceedings{ACLD11_local-approximation-algorithms-for-uncap-metric-flp-power-aware,
1278         author = "Abshoff, Sebastian and Cord-Landwehr, Andreas and Degener, Bastian and Kempkes, Barbara and Pietrzyk, Peter",
1279         booktitle = "{Proceedings of 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities}",
1280         note = "(to be published)",
1281         publisher = "Springer-Verlag",
1282         series = "{LNCS}",
1283         title = "{Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks}",
1284         year = "2011"
1285 }
1286 
1287 @inproceedings{Garey:1976:NGP:800113.803626,
1288         acmid = "803626",
1289         address = "New York, NY, USA",
1290         author = "Garey, M. R. and Graham, R. L. and Johnson, D. S.",
1291         booktitle = "{Proceedings of the eighth annual ACM symposium on Theory of computing}",
1292         doi = "10.1145/800113.803626",
1293         localfile = "archive/G76_some-np-complete-geometric-problems.pdf",
1294         location = "Hershey, Pennsylvania, United States",
1295         numpages = "13",
1296         pages = "10–22",
1297         publisher = "ACM",
1298         series = "{STOC '76}",
1299         title = "{Some NP-complete geometric problems}",
1300         url = "http://doi.acm.org/10.1145/800113.803626",
1301         year = "1976"
1302 }
1303 
1304 @inproceedings{CMTV07_constructing-scalable-overlays-for-pub-sub-with-many-topics,
1305         acmid = "1281118",
1306         address = "New York, NY, USA",
1307         author = "Chockler, Gregory and Melamed, Roie and Tock, Yoav and Vitenberg, Roman",
1308         booktitle = "{Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing}",
1309         doi = "10.1145/1281100.1281118",
1310         isbn = "978-1-59593-616-5",
1311         keywords = "application-level multicast; optimization problems; overlay networks; peer-to-peer; pub/sub",
1312         localfile = "archive/CMTV07_constructing-scalable-overlays-for-pub-sub-with-many-topics.pdf",
1313         location = "Portland, Oregon, USA",
1314         numpages = "10",
1315         pages = "109–118",
1316         publisher = "ACM",
1317         series = "{PODC '07}",
1318         title = "{Constructing scalable overlays for pub-sub with many topics}",
1319         url = "http://doi.acm.org/10.1145/1281100.1281118",
1320         year = "2007"
1321 }
1322 
1323 @inproceedings{springerlink:10.1007/978-3-642-22012-8_8,
1324         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.",
1325         affiliation = "Dept. of Computer Science, RWTH Aachen University, Germany",
1326         author = "Hoefer, Martin",
1327         booktitle = "{Automata, Languages and Programming}",
1328         doi = "10.1007/978-3-642-22012-8_8",
1329         editor = "Aceto, Luca and Henzinger, Monika and Sgall, Jirí",
1330         isbn = "978-3-642-22011-1",
1331         keyword = "Computer Science",
1332         localfile = "archive/H11_local-matching-dynamics-in-social-networks_EXTENDED.pdf; archive/H11_local-matching-dynamics-in-social-networks.pdf",
1333         pages = "113–124",
1334         publisher = "Springer Berlin / Heidelberg",
1335         series = "{Lecture Notes in Computer Science}",
1336         title = "{Local Matching Dynamics in Social Networks}",
1337         url = "http://dx.doi.org/10.1007/978-3-642-22012-8_8",
1338         volume = "6756",
1339         x-fetchedfrom = "SpringerLink",
1340         year = "2011"
1341 }
1342 
1343 @incollection{AH_contribution-games-in-social-networks,
1344         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.",
1345         affiliation = "Dept. of Computer Science, Rensselaer Polytechnic Institute, Troy, NY",
1346         author = "Anshelevich, Elliot and Hoefer, Martin",
1347         booktitle = "{Algorithms – ESA 2010}",
1348         editor = "de Berg, Mark and Meyer, Ulrich",
1349         isbn = "978-3-642-15774-5",
1350         keyword = "Computer Science",
1351         localfile = "archive/AH10_contribution-games-in-social-networks.pdf; archive/AH10_contribution-games-in-social-networks_FULLPAPER.pdf",
1352         note = "10.1007/978-3-642-15775-2\_14",
1353         pages = "158–169",
1354         publisher = "Springer Berlin / Heidelberg",
1355         series = "{Lecture Notes in Computer Science}",
1356         title = "{Contribution Games in Social Networks}",
1357         url = "http://dx.doi.org/10.1007/978-3-642-15775-2_14",
1358         volume = "6346",
1359         year = "2010"
1360 }
1361 
1362 @article{AAABN06_general-approach-to-online-network-opt-problems,
1363         acmid = "1198522",
1364         address = "New York, NY, USA",
1365         author = "Alon, Noga and Awerbuch, Baruch and Azar, Yossi and Buchbinder, Niv and Naor, Joseph (Seffi)",
1366         doi = "10.1145/1198513.1198522",
1367         issn = "1549-6325",
1368         journal = "ACM Trans. Algorithms",
1369         keywords = "Online network optimization; competitive analysis; facility location; group Steiner; multi-cuts; randomized rounding",
1370         localfile = "archive/AAZBN06_general-approach-to-online-network-opt-problems.pdf",
1371         month = "October",
1372         number = "4",
1373         numpages = "21",
1374         pages = "640–660",
1375         publisher = "ACM",
1376         title = "{A general approach to online network optimization problems}",
1377         url = "http://doi.acm.org/10.1145/1198513.1198522",
1378         volume = "2",
1379         x-fetchedfrom = "ACM Digital Library",
1380         year = "2006"
1381 }
1382 
1383 @inproceedings{AKR91_when-trees-collide,
1384         author = "Agrawal, A. and Klein, P. and Ravi, R.",
1385         booktitle = "{Proceedings of the twenty-third annual ACM symposium on Theory of computing}",
1386         keywords = "GNWS - Generalized Node-Weighted Steiner Tree Problem; NWS - Network-Weighted Steiner Tree Problem; network design",
1387         localfile = "archive/AKR91_when-trees-collide.pdf",
1388         organization = "ACM",
1389         pages = "134–144",
1390         title = "{When trees collide: An approximation algorithm for the generalized Steiner problem on networks}",
1391         x-fetchedfrom = "Google Scholar",
1392         year = "1991"
1393 }
1394 
1395 @article{A06_node-weighted-steiner-problem-in-graphs,
1396         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.",
1397         author = "Angelopoulos, Spyros",
1398         booktitle = "{Algorithm Theory – SWAT 2006}",
1399         editor = "Arge, Lars and Freivalds, Rusins",
1400         isbn = "978-3-540-35753-7",
1401         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",
1402         localfile = "archive/A06_node-weighted-steiner-problem-in-graphs.pdf",
1403         note = "10.1007/11785293\_21",
1404         pages = "208–219",
1405         publisher = "Springer Berlin / Heidelberg",
1406         series = "{Lecture Notes in Computer Science}",
1407         title = "{The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights}",
1408         url = "http://dx.doi.org/10.1007/11785293_21",
1409         volume = "4059",
1410         x-fetchedfrom = "Google Scholar",
1411         year = "2006"
1412 }
1413 
1414 @inproceedings{GHR06_oblivious-network-design,
1415         acmid = "1109665",
1416         address = "New York, NY, USA",
1417         author = "Gupta, Anupam and Hajiaghayi, Mohammad T. and Räcke, Harald",
1418         booktitle = "{Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm}",
1419         doi = "10.1145/1109557.1109665",
1420         isbn = "0-89871-605-5",
1421         localfile = "archive/GHR06_oblivious-network-design.pdf",
1422         location = "Miami, Florida",
1423         numpages = "10",
1424         pages = "970–979",
1425         publisher = "ACM",
1426         series = "{SODA '06}",
1427         title = "{Oblivious network design}",
1428         url = "http://doi.acm.org/10.1145/1109557.1109665",
1429         year = "2006"
1430 }
1431 
1432 @techreport{HKKN11_cobminatorial-algorithms-for-cap-network-design,
1433         author = "Hajiaghayi, Mohammad Taghi and Khandekar, Rohit and Kortsarz, Guy and Nutov, Zeev",
1434         bibsource = "DBLP, http://dblp.uni-trier.de",
1435         journal = "CoRR",
1436         keywords = "SNDP; CAP-SNDP; group steiner tree; tree cover",
1437         localfile = "archive/HKKN11_cobminatorial-algorithms-for-cap-network-design.pdf",
1438         title = "{Combinatorial Algorithms for Capacitated Network Design}",
1439         url = "http://arxiv.org/abs/1108.1176",
1440         volume = "abs/1108.1176",
1441         year = "2011"
1442 }
1443 
1444 @inproceedings{HK03_polylogarithmic-inapproximability,
1445         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.",
1446         acmid = "780628",
1447         address = "New York, NY, USA",
1448         author = "Halperin, Eran and Krauthgamer, Robert",
1449         booktitle = "{Proceedings of the thirty-fifth annual ACM symposium on Theory of computing}",
1450         doi = "10.1145/780542.780628",
1451         isbn = "1-58113-674-9",
1452         keywords = "Steiner tree; approximation algorithms; hardness of approximation; integrality ratio; polylogarithmic approximation",
1453         localfile = "archive/HK03_polylogarithmic-inapproximability.pdf",
1454         location = "San Diego, CA, USA",
1455         numpages = "10",
1456         pages = "585–594",
1457         publisher = "ACM",
1458         series = "{STOC '03}",
1459         title = "{Polylogarithmic inapproximability}",
1460         url = "http://doi.acm.org/10.1145/780542.780628",
1461         year = "2003"
1462 }
1463 
1464 @inproceedings{GW92_general-approx-technique-for-constrained-forest-problems,
1465         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].",
1466         acmid = "139468",
1467         address = "Philadelphia, PA, USA",
1468         author = "Goemans, Michel X. and Williamson, David P.",
1469         booktitle = "{Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms}",
1470         isbn = "0-89791-466-X",
1471         localfile = "archive/GW92_general-approx-technique-for-constrained-forest-problems.pdf",
1472         location = "Orlando, Florida, United States",
1473         numpages = "10",
1474         pages = "307–316",
1475         publisher = "Society for Industrial and Applied Mathematics",
1476         series = "{SODA '92}",
1477         title = "{A general approximation technique for constrained forest problems}",
1478         url = "http://dl.acm.org/citation.cfm?id=139404.139468",
1479         year = "1992"
1480 }
1481