In the incremental version of the well-known k-median problem, the objective is to compute an incremental sequence of facility sets F-1 subset of F-2 subset of ... subset of F-n, where each F-k contains at most k faci...
详细信息
In the incremental version of the well-known k-median problem, the objective is to compute an incremental sequence of facility sets F-1 subset of F-2 subset of ... subset of F-n, where each F-k contains at most k facilities. We say that this incremental medians sequence is R-competitive if the cost of each F-k is at most R times the optimum cost of k facilities. the smallest such R is called the competitive ratio of the sequence {F-k}. Mettu and Plaxton [Ramgopal R. Mettu, C. Greg Plaxton, the online median problem, in: Proc. 41st Symposium on Foundations of Computer Science, FOCS, IEEE, 2000, pp. 339-348: Ramgopal R. Mettu, C. Greg Plaxton, the online median problem, SIAM journal on Computing 32 (3) (2003) 816-832] presented a polynomial-time algorithm that computes an incremental sequence with competitive ratio approximate to 30. they also showed a lower bound of 2. the upper bound on the ratio was improved to 8 in [Guolong Lin, Chandrashekha Nagarajan, Rajmohan Rajamaran, David P. Williamson, A general approach for incremental approximation and hierarchical clustering, in: Proc. 17th Symposium on Discrete algorithms, SODA, 2006, pp. 1147-1156] and [Marek Chrobak, Claire Kenyon, John Noga, Neal Young, online medians via online bidding, in: Proc. 7th Latin American theoretical Informatics Symposium, LATIN, in: Lecture Notes in Computer Science, vol. 3887, 2006, pp. 311-322]. We improve both bounds in this paper. We first show that no incremental sequence can have competitive ratio better than 2.01 and we give a probabilistic construction of a sequence whose competitive ratio is at most 2 + 4 root 2 approximate to 7.656. We also propose a new approach to the problem that for instances that we refer to as equable achieves an optimal ratio of 2. (C) 2009 Elsevier B.V. All rights reserved.
Utility functions satisfying gross substitutability have been studied extensively in the economics literature [1, 11, 12] and recently, the importance of this property has been recognized in the design of combinatoria...
详细信息
ISBN:
(纸本)3540228942
Utility functions satisfying gross substitutability have been studied extensively in the economics literature [1, 11, 12] and recently, the importance of this property has been recognized in the design of combinatorial polynomial time market equilibrium algorithms [8]. this naturally raises the following question: is it possible to design a combinatorial polynomial time algorithm for this general class of utility functions? We partially answer this question by giving an algorithm for separable, differentiable, concave utility functions satisfying gross substitutes. Our algorithm uses the auction based approach of [10]. We also outline an extension of our method to the Walrasian model.
We propose the MIN-MAX MULTIWAY CUT problem, a variant of the traditional MULTIWAY CUT problem, but withthe goal of minimizing the maximum capacity (rather than the sum or average capacity) leaving a part of the part...
详细信息
ISBN:
(纸本)3540228942
We propose the MIN-MAX MULTIWAY CUT problem, a variant of the traditional MULTIWAY CUT problem, but withthe goal of minimizing the maximum capacity (rather than the sum or average capacity) leaving a part of the partition. the problem is motivated by data partitioning in Peer-to-Peer networks. the min-max objective function forces the solution not to overload any given terminal, and hence may lead to better solution quality. We prove that the MIN-MAX MULTIWAY CUT is NP-hard even on trees, or with only a constant number of terminals. Our main result is an O(log(3) n)-approximation algorithm for general graphs, and an O(log(2) n)approximation for graphs excluding any fixed graph as a minor (e.g., planar graphs). We also give a (2 + epsilon)-approximation algorithm for the special case of graphs with bounded treewidth.
the proceedings contain 30 papers. the topics discussed include: broadcast problem in hypercube of trees;direct and certifying recognition of normal helly circular-arc graphs in linear time;a fixed-parameter approach ...
ISBN:
(纸本)9783319080154
the proceedings contain 30 papers. the topics discussed include: broadcast problem in hypercube of trees;direct and certifying recognition of normal helly circular-arc graphs in linear time;a fixed-parameter approach for privacy-protection with global recoding;engineering algorithms for workflow satisfiability problem with user-independent constraints;the complexity of zero-visibility cops and robber;combining edge weight and vertex weight for minimum vertex cover problem;randomized parameterized algorithms for co-path set problem;monotone grid drawings of planar graphs;space-efficient approximate string matching allowing inversions in fast average time;minimal double dominating sets in trees;approximationalgorithms on consistent dynamic map labeling;and approximationalgorithms for bandwidth consecutive multicolorings.
In this paper we study the approximability of the maximization version of constraint satisfaction problems. We provide two probabilistic approximationalgorithms for MAX kCONJSAT which is the problem to satisfy as man...
详细信息
ISBN:
(纸本)3540228942
In this paper we study the approximability of the maximization version of constraint satisfaction problems. We provide two probabilistic approximationalgorithms for MAX kCONJSAT which is the problem to satisfy as many conjunctions, each of size at most k, as possible. As observed by Trevisan, this leads to approximationalgorithms withthe same approximation ratio for the more general problem MAX kCSP, where instead of conjunctions arbitrary k-ary constraints are imposed. the first algorithm achieves an approximation ratio of 2(1.40-k). the second algorithm achieves a slightly better approximation ratio of 2(1.54-k), but the ratio is shown using computational evidence. these ratios should be compared withthe previous best algorithm, due to Trevisan, that achieves an approximation ratio of 2(1-k). Boththe new algorithms use a combination of random restrictions, a method which have been used in circuit complexity, and traditional semidefinite relaxation methods. A consequence of these algorithms is that some complexity classes described by probabilistical checkable proofs can be characterized as subsets of P. Our result in this paper implies that PCPc,s [log, k] subset of or equal to P for any c/s > 2(k-1.40), and we have computational evidence that if c/s > 2(k-1.54) this inclusion still holds.
We consider the problem of continuum armed bandits where the arms are indexed by a compact subset of . For large d, it is well known that mere smoothness assumptions on the reward functions lead to regret bounds that ...
详细信息
We consider the problem of continuum armed bandits where the arms are indexed by a compact subset of . For large d, it is well known that mere smoothness assumptions on the reward functions lead to regret bounds that suffer from the curse of dimensionality. A typical way to tackle this in the literature has been to make further assumptions on the structure of reward functions. In this work we assume the reward functions to be intrinsically of low dimension k a parts per thousand(a) d and consider two models: (i) the reward functions depend on only an unknown subset of k coordinate variables and, (ii) a generalization of (i) where the reward functions depend on an unknown k dimensional subspace of . By placing suitable assumptions on the smoothness of the rewards we derive randomized algorithms for both problems that achieve nearly optimal regret bounds in terms of the number of rounds n.
We study the PARTIAL VERTEX COVER problem. Given a graph G = (V, E), a weight function w : V -> R+, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. the prob...
详细信息
ISBN:
(纸本)3540282394
We study the PARTIAL VERTEX COVER problem. Given a graph G = (V, E), a weight function w : V -> R+, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. the problem is clearly NP-hard as it generalizes the well-known VERTEX COVER problem. We provide a primal-dual 2-approximation algorithm which runs in O(n log n + m) time. this represents an improvement in running time from the previously known fastest algorithm. Our technique can also be used to get a 2-approximation for a more general version of the problem. In the PARTIAL CAPACITATED VERTEX COVER problem each vertex u comes with a capacity k(u). A solution consists of a function x : V -> N-0 and an orientation of all but s edges, such that the number of edges oriented toward vertex u is at most x(u)k(u). Our objective is to find a cover that minimizes Sigma(v is an element of V) x(v)w(v). this is the first 2-approximation for the problem and also runs in O(n log n + m) time.
In this paper we consider the problem of planning sensor observations for a network of overhead sensors which will resolve ambiguities in the output of a horizontal sensor network. More specifically, we address the pr...
详细信息
In this paper we consider the problem of planning sensor observations for a network of overhead sensors which will resolve ambiguities in the output of a horizontal sensor network. More specifically, we address the problem of counting the number of objects detected by the horizontal sensor network, using the overhead network to aim at specific areas to improve the count. We consider several different overhead sensor models. the main theme of our results is that, even though observation planning is intractable for such a network, a simple, greedy algorithm for controlling the overhead sensors guarantees performance with bounded and reasonable suboptimality. Our results are very general and make few assumptions about the specific sensors used.
this book constitutes the thoroughly refereed workshop post-proceedings of the 19th International workshop on approximation and onlinealgorithms, WAOA 2021, held in September 2021. Due to COVID-19 pandemic the confer...
详细信息
ISBN:
(数字)9783030927028
ISBN:
(纸本)9783030927011
this book constitutes the thoroughly refereed workshop post-proceedings of the 19th International workshop on approximation and onlinealgorithms, WAOA 2021, held in September 2021. Due to COVID-19 pandemic the conference was held virtually.
the proceedings contain 7 papers. the topics discussed include: local search for AI planning;in defense of design patterns for AI planning knowledge models;towards plan recognition in hybrid systems;an asp based solut...
the proceedings contain 7 papers. the topics discussed include: local search for AI planning;in defense of design patterns for AI planning knowledge models;towards plan recognition in hybrid systems;an asp based solution for operating room scheduling with surgical teams in hospital environments;model-based automated flight path planning for an ultralight aircraft;improving the efficiency of euclidean tsp solving in constraint programming by predicting effective nocrossing constraints;and answer set programming in healthcare: extended overview.
暂无评论