We present a polynomial time approximation algorithm for the asymmetric maximum traveling salesperson problem that achieves performance ratio 8/13(1 - 1/n). the running time of our algorithm is O(n(3)).
ISBN:
(纸本)089871513X
We present a polynomial time approximation algorithm for the asymmetric maximum traveling salesperson problem that achieves performance ratio 8/13(1 - 1/n). the running time of our algorithm is O(n(3)).
the NP-hard discrete version of the Time-Cost Tradeoff Problem is considered. the first polynomial-time approximation algorithms for the problem are presented. Specifically, the problem of finding an optimal schedule ...
详细信息
the NP-hard discrete version of the Time-Cost Tradeoff Problem is considered. the first polynomial-time approximation algorithms for the problem are presented. Specifically, the problem of finding an optimal schedule for a project with a given budget that must not be overspent is considered. A polynomial time approximation algorithm is given with a performance ratio of 3/2 for projects with alternatives 0/1 or 0/2 for the duration of each activity. this algorithm is shown to be the best approximation that can be found, unless P = NP. the results are generalized to arbitrary projects by giving an approximation algorithm with a performance guarantee of (3/2)log2l+(7/2), where l is the ratio of the maximum duration to the minimum duration.
We show that normalizers and permutational isomorphisms of permutation groups given by generating sets can be computed in time simply exponential in the degree of the groups. the result is obtained by exploiting canon...
详细信息
ISBN:
(纸本)9781611975994
We show that normalizers and permutational isomorphisms of permutation groups given by generating sets can be computed in time simply exponential in the degree of the groups. the result is obtained by exploiting canonical forms for permutation groups (up to permutational isomorphism).
the efficiency of many discretealgorithms crucially depends on quantifying properties of large structured combinatorial configurations. We survey methods of analytic combinatorics that are simply based on the idea of...
详细信息
ISBN:
(纸本)9780898716245
the efficiency of many discretealgorithms crucially depends on quantifying properties of large structured combinatorial configurations. We survey methods of analytic combinatorics that are simply based on the idea of associating numbers to atomic elements that compose combinatorial structures, then examining the geometry of the resulting functions. In this way, an operational calculus of discrete structures emerges. Applications to basic algorithms, data structures, and the theory of random discrete structures are outlined.
We show tight bounds for online Hamming distance computation in the cell-probe model with word size w. the task is to output the Hamming distance between a fixed string of length n and the last n symbols of a stream. ...
详细信息
ISBN:
(纸本)9781611973105;9781611972511
We show tight bounds for online Hamming distance computation in the cell-probe model with word size w. the task is to output the Hamming distance between a fixed string of length n and the last n symbols of a stream. We give a lower bound of Omega (delta/w log n) time on average per output, where ffi is the number of bits needed to represent an input symbol. We argue that this bound is tight within the model. the lower bound holds under randomisation and amortisation.
this paper answers the following mathematical question: Can multiset permutations be ordered so that each permutation is a prefix shift of the previous permutation? Previously, the answer was known for the permutation...
ISBN:
(纸本)9780898716801
this paper answers the following mathematical question: Can multiset permutations be ordered so that each permutation is a prefix shift of the previous permutation? Previously, the answer was known for the permutations of any set, and the permutations of any multiset whose corresponding set contains only two elements. this paper also answers the following algorithmic question: Can multiset permutations be generated by a loopless algorithm that uses sublinear additional storage? Previously, the best loopless algorithm used a linear amount of additional storage. the answers to these questions are both yes.
We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well-studied fairness notions (envy-freeness, proportionality, and approximations thereof) an...
详细信息
ISBN:
(纸本)9781611975482
We initiate the study of the communication complexity of fair division with indivisible goods. We focus on some of the most well-studied fairness notions (envy-freeness, proportionality, and approximations thereof) and valuation classes (submodular, subadditive and unrestricted). Within these parameters, our results completely resolve whether the communication complexity of computing a fair allocation (or determining that none exist) is polynomial or exponential (in the number of goods), for every combination of fairness notion, valuation class, and number of players, for both deterministic and randomized protocols.
Let A be a 0/1 matrix of size m x n, and let p be the density of A (i.e., the number of ones divided by m . n). We show that A can be approximated in the cut norm within epsilon . mnp by a sum of cut matrices (of rank...
详细信息
ISBN:
(纸本)9780898716801
Let A be a 0/1 matrix of size m x n, and let p be the density of A (i.e., the number of ones divided by m . n). We show that A can be approximated in the cut norm within epsilon . mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size m . n of A, provided that A satisfies a certain boundedness condition. the decomposition can be computed in polynomial time. this result extends the work of Frieze and Kannan (Combinatorica 1999) to sparse matrices. As an application, we obtain efficient 1 - epsilon approximation algorithms for "bounded" instances of MAX CSP problems.
A polycube is a face-connected set of cubical cells on Z(3). To-date, no formulae enumerating polycubes by volume (number of cubes) or perimeter (number of empty cubes neighboring the polycube) are known. We present a...
详细信息
ISBN:
(纸本)9781611975031
A polycube is a face-connected set of cubical cells on Z(3). To-date, no formulae enumerating polycubes by volume (number of cubes) or perimeter (number of empty cubes neighboring the polycube) are known. We present a few formulae enumerating polycubes with a fixed deviation from the maximum possible perimeter.
We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. this improves over the best known approximation factor for that problem. As a di...
详细信息
ISBN:
(纸本)9780898716054
We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. this improves over the best known approximation factor for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem, similarly improving upon the best known approximation factor for that problem. the result depends on a new method of consecutive path cover improvements and on a new analysis of certain related color alternating paths. this method could be of independent interest.
暂无评论