The GENERALIZED MAXIMUM LINEAR ARRANGEMENT PROBLEM is to compute for a given vector x is an element of IRn and an n x n non-negative symmetric matrix w = (w(i,j)), a permutation pi of {1,...,n} that maximizes Sigma (i...
详细信息
ISBN:
(纸本)3540676902
The GENERALIZED MAXIMUM LINEAR ARRANGEMENT PROBLEM is to compute for a given vector x is an element of IRn and an n x n non-negative symmetric matrix w = (w(i,j)), a permutation pi of {1,...,n} that maximizes Sigma (i,j) w(pii,pij)\x(j) - x(i)\. We present a fast 1/3-approximation algorithm for the problem. We also introduce a a-approximation algorithm for MAX k-CUT WITH GIVEN SIZES. This matches the bound obtained by Ageev and Sviridenko, but without using linear programming.
We study the sample placement and shortest tour problem for robots tasked with mapping environmental phenomena modeled as stationary random fields. The objective is to minimize the resources used (samples or tour leng...
详细信息
ISBN:
(纸本)9798350323658
We study the sample placement and shortest tour problem for robots tasked with mapping environmental phenomena modeled as stationary random fields. The objective is to minimize the resources used (samples or tour length) while guaranteeing estimation accuracy. We give approximation algorithms for both problems in convex environments. These improve previously known results, both in terms of theoretical guarantees and in simulations. In addition, we disprove an existing claim in the literature on a lower bound for a solution to the sample placement problem.
This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP-nets). Its focus is on aggregating p...
详细信息
ISBN:
(纸本)1577358872
This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP-nets). Its focus is on aggregating preferences over so-called swaps, for which optimal solutions in general are already known to be of exponential size. We first analyze a trivial 2-approximation algorithm that simply outputs the best of the given input preferences, and establish a structural condition under which the approximation ratio of this algorithm is improved to 4/3. We then propose a polynomial-time approximation algorithm whose outputs are provably no worse than those of the trivial algorithm, but often substantially better. A family of problem instances is presented for which our improved algorithm produces optimal solutions, while, for any e, the trivial algorithm cannot attain a (2- epsilon)-approximation. These results may lead to the first polynomial-time approximation algorithm that solves the CP-net aggregation problem for swaps with an approximation ratio substantially better than 2.
We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for stor...
详细信息
ISBN:
(数字)9783319774046
ISBN:
(纸本)9783319774046;9783319774039
We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places;at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.
Today's software systems are more frequently composed from preexisting commercial or non-commercial components and connectors. These components provide complex and independent functionality and are engaged in comp...
详细信息
ISBN:
(纸本)9780769530574
Today's software systems are more frequently composed from preexisting commercial or non-commercial components and connectors. These components provide complex and independent functionality and are engaged in complex interactions. Component-Based Software Engineering (CBSE) is concerned with composing, selecting and designing such components. As the popularity of this approach and hence number of commercially available software components grows, selecting a set of components to satisfy a set of requirements while minimizing cost is becoming more difficult. This problem necessitates the design of efficient algorithms to automate component selection for software developing organizations. We address this challenge through analysis of Component Selection, the NP-complete process of selecting a minimal cost set of components to satisfy a set of objectives. Due to the high order of computational complexity of this problem, we examine approximating solutions that make the component selection process practicable. We adapt a greedy approach and a genetic algorithm to approximate this problem. We examined the performance of studied algorithms on a set of selected ActiveX components. Comparing the results of these two algorithms with the choices made by a group of human experts shows that we obtain better results using these approximation algorithms.
We consider two natural generalizations of the Asymmetric Traveling Salesman problem: the k-Stroll and the k-Tour problems. The input to the k-Stroll problem is a directed n-vertex graph with nonnegative edge lengths,...
详细信息
ISBN:
(纸本)9783642153686
We consider two natural generalizations of the Asymmetric Traveling Salesman problem: the k-Stroll and the k-Tour problems. The input to the k-Stroll problem is a directed n-vertex graph with nonnegative edge lengths, an integer k, and two special vertices s and t. The goal is to find a minimum-length s-t, walk, containing at least k distinct vertices. The k-Tour problem can be viewed as a special case of k-Stroll, where S = t. That is, the walk is required to be a tour, containing some pre-specified vertex s. When k = n, the k-Stroll problem becomes equivalent to Asymmetric Traveling Salesman Path, and k-Tour to Asymmetric Traveling Salesman. Our main result is a polylogarithmic approximation algorithm for the k-Stroll problem. Prior to our work, only bicriteria (O(log(2) k), 3)-approximation algorithms have been known, producing walks whose length is bounded by 3OPT, while the number of vertices visited is Omega(k/log(2) k). We also show a simple O(log(2) n/log log n)-approximation algorithm for the k-Tour problem. The best previously known approximation algorithms achieved min (O(log(3) k), O(log(2) *** k/log log n))-approximation in polynomial time, and O(log(2) k)-approximation in quasipolynomial time.
Many known optimal NP-hardness of approximation results are reductions from a problem called LABEL COVER. The input is a bipartite graph G = (L, R, E) and each edge e = (x, y) is an element of E carries a projection p...
详细信息
ISBN:
(纸本)9781611974782
Many known optimal NP-hardness of approximation results are reductions from a problem called LABEL COVER. The input is a bipartite graph G = (L, R, E) and each edge e = (x, y) is an element of E carries a projection pi(e) that maps labels to x to labels to y. The objective is to find a labeling of the vertices that satisfies as many of the projections as possible. It is believed that the best approximation ratio efficiently achievable for LABEL-COVER is of the form N-c where N = nk, n is the number of vertices, k is the number of labels, and 0 < c < 1 is some constant. Inspired by a framework originally developed for DENSEST k-SUBGRAPH, we propose a "log density threshold" for the approximability of Label-Cover. Specifically, we suggest the possibility that the Label-Cover approximation problem undergoes a computational phase transition at the same threshold at which local algorithms for its random counterpart fail. This threshold is N3-2 root 2 approximate to N-0.17 We then design, for any epsilon > 0, a polynomial-time approximation algorithm for semi random LABEL-COVER whose approximation ratio is N3-2 root 2+epsilon. In our semi-random model, the input graph is random (or even just expanding), and the projections on the edges are arbitrary. For worst-case LABEL-COVER we show a polynomial-time algorithm whose approximation ratio is roughly N-0.233. The previous best efficient approximation ratio was N-0.25. We present some evidence towards an N-c threshold by constructing integrality gaps for N-Omega(1) rounds of the Sum-of-squares/Lasserre hierarchy of the natural relaxation of Label Cover. For general 2CSP the "log density threshold" is N-0.25, and we give a polynomial-time algorithm in the semi-random model whose approximation ratio is N-0.25+epsilon for any epsilon > 0.
We present some recent results on the computational complexity of the generic algebraic problems of estimating the number of zeros and nonzeros of multivariate polynomials over finite fields GF[q]. We design the first...
详细信息
This paper considers embeddings f of arbitrary finite metrics into the line metric R so that none of the distances is shrunk by the embedding f;the quantity of interest is the factor by which the average distance in t...
详细信息
ISBN:
(纸本)9783540212362
This paper considers embeddings f of arbitrary finite metrics into the line metric R so that none of the distances is shrunk by the embedding f;the quantity of interest is the factor by which the average distance in the metric is stretched. We call this quantity the average distortion of the non-contracting map f. We prove that finding the best embedding of even a tree metric into a line metric to minimize the average distortion is NP-hard, and hence focus on approximating the average distortion of the best possible embedding for the given input metric. We give a constant-factor approximation for the problem of embedding general metrics into the line metric. For the case of n-point tree metrics, we provide a quasi-polynomial time approximation scheme which outputs an embedding with distortion at most (1 + epsilon) times the optimum in time n(O(logn/epsilon 2)). Finally, when the average distortion is measured only over the endpoints of the edges of an input tree metric, we show how to exploit the structure of tree metrics to give an exact solution in polynomial time.
Unit disk graphs are the intersection graphs of equal sized circles in the plane. In this paper, we consider the maximum independent set problems on unit disk graphs. When the given unit disk graph is defined on a sla...
详细信息
ISBN:
(纸本)3540671811
Unit disk graphs are the intersection graphs of equal sized circles in the plane. In this paper, we consider the maximum independent set problems on unit disk graphs. When the given unit disk graph is defined on a slab whose width is k, we propose an algorithm for finding a maximum independent set in O(n(4(sic)2k/root 3(sic))) time where n denotes the number of vertices. We also propose a (1 - 1/r)-approximation algorithm for the maximum independent set problems on a (general) unit disk graph whose time complexity is bounded by O(rn(4(sic)2(r-1)/root 3(sic))). We also propose an algorithm for fractional coloring problems on unit disk graphs. The fractional coloring problem is a continuous version of the ordinary (vertex) coloring problem. Our approach for the independent set problem implies a strongly polynomial time algorithm for the fractional coloring problem on unit disk graphs defined on a fixed width slab. We also propose a strongly polynomial time a-approximation algorithm for fractional coloring problem on a (general) unit disk graph.
暂无评论