检索结果-内蒙古大学图书馆

symposium on discrete algorithms

作者： Artur Czumaj Christiane Lammersen Morteza Monemizadeh Christian Sohler Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP) University of Warwick School of Computing Science Simon Fraser University Institute for Computer Science University of Frankfurt Department of Computer Science Technische Universit?t Dortmund

ISBN: (纸本)9781627484855

We consider the Euclidean facility location problem with uniform opening cost. In this problem, we are given a set of n points P ? ?~2 and an opening cost f ∈ ?~+ and we want to find a set of facilities F ? ?~2 that minimizes where d(p, q) is the Euclidean distance between p and q. We obtain two main results: ? A (1 + ε)-approximation algorithm with running time 0(nlog n(log n log log n + (log log n)~8 2~(O(log (1/ε)/ε)))),which is O(n log~2 n log log n) for any constant ε. ? the first (1 + ε)-approximation algorithm for the cost of the facility location problem for dynamic geometric data streams, i.e., when the stream consists of insert and delete operations of points from a discrete space {1,..., Δ}~2. the streaming algorithm uses (log △/?)~(o(1)) space. Our PTAS is significantly faster than any previously known (1 + ε)-approximation algorithm for the problem, and is also relatively simple. Our algorithm for dynamic geometric data streams is the first (1 + ε)-approximation algorithm for the cost of the facility location problem with polylogarithmic space, and it resolves an open problem in the streaming area. Both algorithms are based on a novel and simple decomposition of an input point set Ρ into small subsets Pi, such that: ? the cost of solving the facility location problem for each Pi is small (which means that for each Pi one needs to open only a small, polylogarithmic number of facilities), ? Σ_(i) OPT(P_(i)) ≤ (1+ε) ? OPT(P), where for a point set P, OPT(P) denotes the cost of an optimal solution for P. the decomposition can be used directly to obtain the PTAS by splitting the point set in the subsets and efficiently solve the problem for each subset independently. By combining our partitioning with techniques to process dynamic data streams of sampling from the cells of the partition and estimating the cost from the sample, we obtain our data streaming algorithm.

关键词： (1 + ε)-Approximation Location in Data Streams process dynamic facility location data flow Approximation algorithms location problem streams logs logarithm (log) Set of points partitions rivers Euclidean distance algorithms

来源：评论

学校读者我要写书评

暂无评论

Anonymous Meeting in Networks 13

Anonymous Meeting in Networks

引用

symposium on discrete algorithms

作者： Yoann Dieudonné Andrzej Pelc MIS Université de Picardie Jules Verne Amiens France. Département d'informatique Université du Québec en Outaouais Gatineau Québec J8X 3X7 Canada.

ISBN: (纸本)9781627484855

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node. Agents are anonymous (identical), execute the same deterministic algorithm and move in synchronous rounds along links of the network. An. initial configuration of agents is called gatherable if there exists a deterministic algorithm (even dedicated to this particular configuration) that achieves meeting of all agents in one node. Which configurations are gatherable and how to gather all of them deterministically by the same algorithm? We give a complete solution of this gathering problem in arbitrary networks. We characterize all gatherable configurations and give two universal deterministic gathering algorithms, i.e., algorithms that gather all gatherable configurations. the first algorithm works under the assumption that an upper bound n on the size of the network is known. In this case our algorithm guarantees gathering with detection, i.e., the existence of a round for any gatherable configuration, such that all agents are at the same node and all declare that gathering is accomplished. If no upper bound on the size of the network is known, we show that a universal algorithm for gathering with detection does not exist. Hence, for this harder scenario, we construct a second universal gathering algorithm, which guarantees that, for any gatherable configuration all agents eventually get to one node and stop, although they cannot tell if gathering is over. the time of the first algorithm is polynomial in the upper bound n on the size of the network, and the time of the second algorithm is polynomial in the (unknown) size itself. Our results have an important consequence for the leader election problem for anonymous agents in arbitrary graphs. Leader election is a fundamental symmetry breaking problem in distributed computing. Its goal is to assign, in some common round, value 1(leader) to one of the

关键词： Anonymous Meeting mobile agents leader election problem harvesting Mobile agents Agents collection Network Polynomial configurations generalized algorithm

来源：评论

学校读者我要写书评

暂无评论

Packing anchored rectangles

Packing anchored rectangles

引用

23rd annual acm-siam symposium on discrete algorithms, SODA 2012

作者： Dumitrescu, Adrian Tóth, Csaba D. Department of Computer Science University of Wisconsin-Milwaukee Milwaukee WI United States Department of Mathematics and Statistics University of Calgary Canada

ISBN: (纸本)9781611972108

Let S be a set of n points in the unit square [0,1]2, one of which is the origin. We construct n pairwise interior-disjoint axis-aligned empty rectangles such that the lower left corner of each rectangle is a point in S, and the rectangles jointly cover at least a positive constant area (about 0.09). this is a first step towards the solution of a longstanding conjecture that the rectangles in such a packing can jointly cover an area of at least 1/2. Copyright © siam.

关键词：

来源：评论

学校读者我要写书评

暂无评论

the condensation transition in random hypergraph 2-coloring

The condensation transition in random hypergraph 2-coloring

引用

23rd annual acm-siam symposium on discrete algorithms, SODA 2012

作者： Coja-Oghlan, Amin Zdeborová, Lenka University of Warwick Mathematics and Computer Science Zeeman Building Coventry CV4 7AL United Kingdom Institut de Physique Théorique IPhT CNRS 91191 Gif-sur-Yvette France

ISBN: (纸本)9781611972108

For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence of solutions are based on the first and the second moment method. However, in most cases these techniques do not yield matching upper and lower bounds. Sophisticated but non-rigorous arguments from statistical mechanics have ascribed this discrepancy to the existence of a phase transition called condensation that occurs shortly before the actual threshold for the existence of solutions and that affects the combinatorial nature of the problem (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborová: PNAS 2007). In this paper we prove for the first time that a condensation transition exists in a natural random CSP, namely in random hypergraph 2-coloring. Perhaps surprisingly, we find that the second moment method applied to the number of 2-colorings breaks down strictly before the condensation transition. Our proof also yields slightly improved bounds on the threshold for random hypergraph 2-colorability. Copyright © siam.

关键词： Statistical mechanics

来源：评论

学校读者我要写书评

暂无评论

Simultaneous approximations for adversarial and stochastic online budgeted allocation

Simultaneous approximations for adversarial and stochastic o...

引用

23rd annual acm-siam symposium on discrete algorithms, SODA 2012

作者： Mirrokni, Vahab S. Gharan, Shayan Oveis Zadimoghaddam, Morteza Google Research 76 9th Ave. New York NY 10011 United States Department of Management Science and Engineering Stanford University United States MIT Computer Science and Artificial Intelligence Laboratory Cambridge MA 02139 United States

ISBN: (纸本)9781611972108

Motivated by online ad allocation, we study the problem of simultaneous approximations for the adversarial and stochastic online budgeted allocation problem. this problem consists of a bipartite graph G = (X, Y, E), where the nodes of Y along with their corresponding capacities are known beforehand to the algorithm, and the nodes of X arrive online. When a node of X arrives, its incident edges, and their respective weights are revealed, and the algorithm can match it to a neighbor in Y. the objective is to maximize the weight of the final matching, while respecting the capacities. When nodes arrive in an adversarial order, the best competitive ratio is known to be 1 - 1/e, and it can be achieved by the Ranking [18], and its generalizations (Balance [16, 21]). On the other hand, if the nodes arrive through a random permutation, it is possible to achieve a competitive ratio of 1 - Ε [9]. In this paper we design algorithms that achieve a competitive ratio better than 1 - 1/e on average, while preserving a nearly optimal worst case competitive ratio. Ideally, we want to achieve the best of both worlds, i.e, to design an algorithm with the optimal competitive ratio in both the adversarial and random arrival models. We achieve this for unweighted graphs, but show that it is not possible for weighted graphs. In particular, for unweighted graphs, under some mild assumptions, we show that Balance achieves a competitive ratio of 1 - Ε in a random permutation model. For weighted graphs, however, we prove this is not possible;we prove that no online algorithm that achieves an approximation factor of 1 - 1/e for the worst-case inputs may achieve an average approximation factor better than 97.6% for random inputs. In light of this hardness result, we aim to design algorithms with improved approximation ratios in the random arrival model while preserving the competitive ratio of 1 - 1/e in the worst case. To this end, we show the algorithm proposed by [21] achieves a competitive r

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Gathering despite mischief

Gathering despite mischief

引用

23rd annual acm-siam symposium on discrete algorithms, SODA 2012

作者： Dieudonné, Yoann Pelc, Andrzej Peleg, David MIS Université de Picardie Jules Verne Amiens France Département d'Informatique Université du Québec en Outaouais Gatineau QC J8X 3X7 Canada Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot 76100 Israel

ISBN: (纸本)9781611972108

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents, and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents we show that any number of good agents permit to solve the problem for networks of known size. If the size is unknown, then this minimum number is f + 2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f + 2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f + 1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents we give a lower bound of f + 1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side we give deterministic gathering algorithms for at least 2f + 1 good agents when the size of the network is known, and for at least 4f + 2 good agents when it is unknown. Copyright © siam.

关键词： Mobile agents

来源：评论

学校读者我要写书评

暂无评论

Computational Aesthetics 2012 - International symposium on Computational Aesthetics in Graphics, Visualization, and Imaging

Computational Aesthetics 2012 - International Symposium on C...

引用

8th annual symposium on Computational Aesthetics in Graphics, Visualization, and Imaging, CAe 2012

ISBN: (纸本)9783905674439

the proceedings contain 14 papers. the topics discussed include: SAMBA: steadied choreographies;integrarte: DigitalArt using body interaction;sketches by Paul the robot;feedback-guided stroke placement for a painting machine;the aMotion toolkit: painting with affective motion textures;a technique for art direction of physically based fire simulation;evaluating visual aesthetics in photographic portraiture;determining an aesthetic inscribed curve;developing a system of screen-less animation for experiments in perception of movement;random discrete colour sampling;exploring the effect of color palette in painterly rendered character sequences;duotone surfaces;surface covering curves;and accurate and discernible photocollages.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Random discrete colour sampling

Random discrete colour sampling

引用

8th annual symposium on Computational Aesthetics in Graphics, Visualization, and Imaging, CAe 2012

作者： Lieng, Henrik Richardt, Christian Dodgson, Neil A. University of Cambridge United Kingdom

ISBN: (纸本)9783905674439

Apparently-random distributions of colours in a discrete setting have been used by many artists and craftsmen in the past century. Manual colourisation is a tedious and difficult process. Automatic colourisation, on the other hand, tends not to not look'random'to a human, as randomly-generated clusters and patterns stimulate human perception and break the appearance of randomness. We propose an algorithm that minimises these apparent patterns, making the distribution of colours look as if they have been distributed randomly by a human. We show that our approach is superior to current solutions, especially for small numbers of colours. Our algorithm is easily extendible to non-regular patterns in any coordinate system. © the Eurographics Association 2012.

关键词： Color

来源：评论

学校读者我要写书评

暂无评论

Prize-collecting Steiner problems on planar graphs

Prize-collecting Steiner problems on planar graphs

引用

作者： Bateni, M. Chekuri, C. Ene, A. Hajiaghayi, M.T. Korula, N. Marx, D. Department of Computer Science Center for Computational Intractability Princeton University Princeton NJ 08540 United States Department of Computer Science University of Illinois Urbana IL 61801 United States Department of Computer Science University of Maryland 115 A.V. Williams Building College Park MD 20742 United States Google Research 76 9th Ave New York NY 10011 United States Humboldt-Universität zu Berlin Germany

ISBN: (纸本)9780898719932

In this paper, we reduce Prize-Collecting Steiner TSP (PCTSP), Prize-Collecting Stroll (PCS), Prize-Collecting Steiner Tree (PCST), Prize-Collecting Steiner Forest (PCSF), and more generally Submodular Prize-Collecting Steiner Forest (SPCSF), on planar graphs (and also on bounded-genus graphs) to the corresponding problem on graphs of bounded treewidth. More precisely, for each of the mentioned problems, an a-approximation algorithm for the problem on graphs of bounded treewidth implies an (α + Ε)- approximation algorithm for the problem on planar graphs (and also bounded-genus graphs), for any constant Ε > 0. PCS, PCTSP. and PCST can be solved exactly on graphs of bounded treewidth and hence we obtain a PTAS for these problems on planar graphs and bounded-genus graphs. In contrast, we show that PCSF is APX-hard to approximate on series-parallel graphs, which are planar graphs of treewidth at most 2. Apart from ruling out a PTAS for PCSF on planar graphs and bounded treewidth graphs, this result is also interesting since it gives the first provable hardness separation between the approxiinability of a problem and its prize-collecting version. We also show that PCSF is APX-hard on Euclidean instances.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Lower-Bounded Facility Location

引用

acm TRANSACTIONS ON algorithms 2010年第4期6卷 1–16页

作者： Svitkina, Zoya Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

We study the lower-bounded facility location problem which generalizes the classical uncapacitated facility location problem in that it comes with lower bound constraints for the number of clients assigned to a facility in the case that this facility is opened. this problem was introduced independently in the papers by Karger and Minkoff [2000] and by Guha et al. [2000], both of which give bicriteria approximation algorithms for it. these bicriteria algorithms come within a constant factor of the optimal solution cost, but they also violate the lower bound constraints by a constant factor. Our result in this article is the first true approximation algorithm for the lower-bounded facility location problem which respects the lower bound constraints and achieves a constant approximation ratio for the objective function. the main technical idea for the design of the algorithm is a reduction to the capacitated facility location problem, which has known constant-factor approximation algorithms.

关键词： Approximation algorithm facility location

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：