*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 satisﬁed 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 inﬁnitely 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. Speciﬁcally, we present algorithms for converging the robots to a single point and moving the robots to a single point in ﬁnite steps. We also characterize the class of geometric patterns that the robots can form in terms of their initial conﬁguration. 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