the proceedings contain 23 papers. the special focus in this conference is on approximation and onlinealgorithms. the topics include: approximationalgorithms for domination search;lower bounds for Smith’s rule in s...
ISBN:
(纸本)9783642183171
the proceedings contain 23 papers. the special focus in this conference is on approximation and onlinealgorithms. the topics include: approximationalgorithms for domination search;lower bounds for Smith’s rule in stochastic machine scheduling;approximating survivable networks with minimum number of Steiner points;a 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks;online tracking of the dominance relationship of distributed multi-dimensional data;how to play unique games on expanders;online ranking for tournament graphs;throughput maximization for periodic packet routing on trees and grids;approximating directed buy-at-bulk network design;k-edge-connectivity: approximation and LP relaxation;minimizing maximum flowtime of jobs with arbitrary parallelizability;an improved algorithm for online rectangle filling;approximate counting for complex-weighted boolean constraint satisfaction problems;new lower bounds for certain classes of bin packing algorithms;on the approximation complexity hierarchy;the power of uncertainty: Bundle-pricing for unit-demand customers;tradeoff between energy and throughput for online deadline scheduling;new models and algorithms for throughput maximization in broadcast scheduling;densest k-subgraph approximation on intersection graphs;the train delivery problem - vehicle routing meets bin packing.
the proceedings contain 23 papers. the topics discussed include: strategic multiway cut and multicut games;new lower bounds for certain classes of bin packing algorithms;the power of uncertainty: bundle-pricing for un...
ISBN:
(纸本)9783642183171
the proceedings contain 23 papers. the topics discussed include: strategic multiway cut and multicut games;new lower bounds for certain classes of bin packing algorithms;the power of uncertainty: bundle-pricing for unit-demand customers;tradeoff between energy and throughput for online deadline scheduling;new models and algorithms for throughput maximization in broadcast scheduling;densest k-subgraph approximation on intersection graphs;the train delivery problem - vehicle routing meets bin packing;list factoring and relative worst order analysis;approximationalgorithms for domination search;approximating survivable networks with minimum number of Steiner points;online tracking of the dominance relationship of distributed multi-dimensional data;throughput maximization for periodic packet routing on trees and grids;and minimizing maximum flowtime of jobs with arbitrary parallelizability.
this article explores the current state and practical solutions for addressing the readiness of primary school students and teachers to utilise cloud services for creating augmented reality (AR) enhanced comics. the d...
详细信息
the proceedings contain 41 papers from the approximation, Randomization and Combinatorial Optimization - algorithms and Techniques: 8th International workshop on approximationalgorithms for Combinatorial Optimization...
详细信息
the proceedings contain 41 papers from the approximation, Randomization and Combinatorial Optimization - algorithms and Techniques: 8th International workshop on approximationalgorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th International workshop on Randomization and Computation, RANDOM 2005, Proceedings. the topics discussed include: a rounding algorithm for approximating minimum Manhattan networks;packing element-disjoint steiner trees;finding graph matchings in data streams;efficient approximation of convex recolorings;sampling bounds for stochastic optimization;the online clique avoidance game on random graphs;mixing points on a circle;and reconstructive dispensers and hitting set generators.
In this paper we introduce a new technique for approximation schemes for geometrical optimization problems. As an example problem, we consider the following variant of the geometric Steiner tree problem. Every point u...
详细信息
In this paper we introduce a new technique for approximation schemes for geometrical optimization problems. As an example problem, we consider the following variant of the geometric Steiner tree problem. Every point u which is not included in the tree costs a penalty of pi(u) units. Furthermore, every Steiner point that we use costs c(S) units. the goal is to minimize the total length of the tree plus the penalties. Our technique yields a polynomial time approximation scheme for the problem, if the points lie in the plane.
We study the problem of producing a global ranking of items given pairwise ranking information, when the items to be ranked arrive in an online fashion. We study boththe maximization and the minimization versions of ...
详细信息
ISBN:
(纸本)9783642183171
We study the problem of producing a global ranking of items given pairwise ranking information, when the items to be ranked arrive in an online fashion. We study boththe maximization and the minimization versions of the problem on tournaments (max acyclic subgraph, feedback arc set). We also study the case when the items arrive in random order.
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...
详细信息
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.
We present a new approximation algorithm for rate-monotonic multiprocessor scheduling of periodic tasks with implicit deadlines. We prove that for an arbitrary parameter k is an element of N it yields solutions with a...
详细信息
ISBN:
(纸本)9783642183171
We present a new approximation algorithm for rate-monotonic multiprocessor scheduling of periodic tasks with implicit deadlines. We prove that for an arbitrary parameter k is an element of N it yields solutions with at most (3/2 + 1/k)OPT + 9k many processors, thus it gives an asymptotic 3/2-approximation algorithm. this improves over the previously best known ratio of 7/4. Our algorithm can be implemented to run in time O(n(2)), where n is the number of tasks. It is based on custom-tailored weights for the tasks such that a greedy maximal matching and subsequent partitioning by a first-fit strategy yields the result.
In this paper we investigate the computational complexity of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows: We abstract a combinatorial v...
详细信息
In this paper we investigate the computational complexity of a combinatorial problem that arises in the reverse engineering of protein and gene networks. Our contributions are as follows: We abstract a combinatorial version of the problem and observe that this is "equivalent" to the set multicover problem when the "coverage" factor k is a function of the number of elements it of the universe. An important special case for our application is the case in which k = n - 1. We observe that the standard greedy algorithm produces an approximation ratio of Omega(log n) even if k is "large" i.e k = n - c for some constant c > 0. Let 1 < a < n denote the maximum number of elements in any given set in our set multicover problem. then, we show that a non-trivial analysis of a simple randomized polynomial-time approximation algorithm for this problem yields an expected approximation ratio E vertical bar r(a, k)vertical bar that is an increasing function of a/k. the behavior of E vertical bar r(a, k)vertical bar is roughly as follows: it is about In(a/k) when a/k is at least about e(2) approximate to 7.39, and for smaller values of a/k it decreases towards 1 as a linear function of root a/k with lim(a/k -> 0) E vertical bar r(a, k)vertical bar = 1. Our randomized algorithm is a cascade of a deterministic and a randomized rounding step parameterized by a quantity beta followed by a greedy solution for the remaining problem. We also comment about the impossibility of a significantly faster convergence of E vertical bar r(a, k)vertical bar towards 1 for any polynomial-time approximation algorithm. (c) 2006 Elsevier B.V. All rights reserved.
We consider the online problem for a root (or a coordinator) to maintain a set of filters for the purpose of keeping track of the dominance relationship of some distributed multi-dimensional data. Such data keep chang...
详细信息
ISBN:
(纸本)9783642183171
We consider the online problem for a root (or a coordinator) to maintain a set of filters for the purpose of keeping track of the dominance relationship of some distributed multi-dimensional data. Such data keep changing from time to time. the objective is to minimize the communication between the root and the distributed data sources. Assume that data are chosen from the d-dimensional grid {1, 2, ..., U}(d), we give an O(d log U)-competitive algorithm for this online problem. the competitive ratio is asymptotically tight as it is relatively easy to show an Omega(d log U) lower bound.
暂无评论