122,242 research outputs found
A Faster Implementation of the Goemans-Williamson Clustering Algorithm
No full textWe give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting Travelling Salesman, 2-Edge Connected Subgraph etc. On a graph with n nodes and m edges, our implementation gives time approximation algorithms for all these problems at the expense of a 1 slight additive degradation of in the approximation factor, for any constant k
A faster implementation of the Goemans-Williamson clustering algorithm
No full textWe give an implementation of the Goemans-Williamson clustering procedure which is at the core of several approximation algorithms including those for Generalized Steiner Trees, Prize Collecting Travelling Salesman, 2-Edge Connected Subgraph etc. On a graph with n nodes and m edge, our implementation gives Ο (k(n + m) log2 n) time approximation algorithms for all these problems at the expense of a slight additive degradation of 1/nk in the approximation factor, for any constant k
Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints
No full textSemidefinite programs are optimization methods with a wide array of
applications, such as approximating difficult combinatorial problems. One such
semidefinite program is the Goemans-Williamson algorithm, a popular integer
relaxation technique. We introduce a variational quantum algorithm for the
Goemans-Williamson algorithm that uses only qubits, a constant number
of circuit preparations, and expectation values in order to
approximately solve semidefinite programs with up to variables and constraints. Efficient optimization is achieved by encoding the
objective matrix as a properly parameterized unitary conditioned on an auxilary
qubit, a technique known as the Hadamard Test. The Hadamard Test enables us to
optimize the objective function by estimating only a single expectation value
of the ancilla qubit, rather than separately estimating exponentially many
expectation values. Similarly, we illustrate that the semidefinite programming
constraints can be effectively enforced by implementing a second Hadamard Test,
as well as imposing a polynomial number of Pauli string amplitude constraints.
We demonstrate the effectiveness of our protocol by devising an efficient
quantum implementation of the Goemans-Williamson algorithm for various NP-hard
problems, including MaxCut. Our method exceeds the performance of analogous
classical methods on a diverse subset of well-studied MaxCut problems from the
GSet library.Comment: 21 pages, 6 figures. Updated files to the version of manuscript
accepted by Quantu
Smallest Compact Formulation for the Permutahedron
No full textIn this note, we consider the permutahedron, the convex hull of all permutations of {1,2…,n} . We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal Ajtai–Komlós–Szemerédi sorting network, this extended formulation has Θ(nlogn) variables and inequalities. Furthermore, from basic polyhedral arguments, we show that this is best possible (up to a multiplicative constant) since any extended formulation has at least Ω(nlogn) inequalities. The results easily extend to the generalized permutahedron.National Science Foundation (U.S.) (Contract CCF-0829878)National Science Foundation (U.S.) (Contract CCF-1115849)United States. Office of Naval Research (Grant 0014-05-1-0148
Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations
No full textWe present an efficient algorithm to find nonempty minimizers of a symmetric submodular function f over any family of sets I closed under inclusion. Our algorithm makes O(n[superscript 3]) oracle calls to f and I, where n is the cardinality of the ground set. In contrast, the problem of minimizing a general submodular function under a cardinality constraint is known to be inapproximable within o(√n/log n) [Z. Svitkina and L. Fleischer, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, 2008, pp. 697--706]. We also present two extensions of the above algorithm. The first extension reports all nontrivial inclusionwise minimal minimizers of f over I using O(n[superscript 3]) oracle calls, and the second reports all extreme subsets of f using O(n[superscript 4]) oracle calls. Our algorithms are similar to a procedure by Nagamochi and Ibaraki [Inform. Process. Lett., 67 (1998), pp. 239--244] that finds all nontrivial inclusionwise minimal minimizers of a symmetric submodular function over a set of size n using O(n[superscript 3]) oracle calls. Their procedure in turn is based on Queyranne's algorithm [M. Queyranne, Math. Program., 82 (1998), pp. 3--12] to minimize a symmetric submodular function by finding pendent pairs. Our results extend to any class of functions for which we can find a pendent pair whose head is not a given element.National Science Foundation (U.S.) (Contract CCF-0829878)National Science Foundation (U.S.) (Contrac tCCF-1115849)United States. Office of Naval Research (Grant N00014-11-1-0053
Tight Approximation Algorithms for Maximum Separable Assignment Problems
No full textA separable assignment problem (SAP) is defined by a set of bins and a set of items to pack in each bin; a value, f[subscript ij], for assigning item j to bin i; and a separate packing constraint for each bin—i.e., for each bin, a family of subsets of items that fit in to that bin. The goal is to pack items into bins to maximize the aggregate value. This class of problems includes the maximum generalized assignment problem (GAP)[superscript 1] and a distributed caching problem (DCP) described in this paper.
Given a β-approximation algorithm for finding the highest value packing of a single bin, we give
i. A polynomial-time LP-rounding based ((1 − 1/e)β)-approximation algorithm.
ii. A simple polynomial-time local search (β/(β + 1) − ε)-approximation algorithm, for any ε > 0.
Therefore, for all examples of SAP that admit an approximation scheme for the single-bin problem, we obtain an LP-based algorithm with (1 − 1/e − ε)-approximation and a local search algorithm with (½ - ε)-approximation guarantee. Furthermore, for cases in which the subproblem admits a fully polynomial approximation scheme (such as for GAP), the LP-based algorithm analysis can be strengthened to give a guarantee of 1 − 1/e. The best previously known approximation algorithm for GAP is a ½-approximation by Shmoys and Tardos and Chekuri and Khanna. Our LP algorithm is based on rounding a new linear programming relaxation, with a provably better integrality gap.
To complement these results, we show that SAP and DCP cannot be approximated within a factor better than 1 − 1/e unless NP ⊆ DTIME(n[superscript O(log log n)]), even if there exists a polynomial-time exact algorithm for the single-bin problem.
We extend the (1 − 1/e)-approximation algorithm to a constant-factor approximation algorithms for a nonseparable assignment problem with applications in maximizing revenue for budget-constrained combinatorial auctions and the AdWords assignment problem. We generalize the local search algorithm to yield a ½ - ε approximation algorithm for the maximum k-median problem with hard capacities.National Science Foundation (U.S.) (Contract CCF-0728869)National Science Foundation (U.S.) (Contract CCF-0829878)United States. Office of Naval Research (Grant N00014-11-1-0053
A Multi-Language Comparison of Influences on Author Verification using Character N-Grams
No full textWe create a new multi-language corpus for author verification based on Wikipedia talkpages, and evaluate the influence that differences in topic and time have on character n-gram author profiles. Topic alignment between two texts is found to increase author verification precision, and an authors writing style is found to change over time, but not more significantly after 3 years than after 1 year.Information ArchitectureWISElectrical Engineering, Mathematics and Computer Scienc
Approximating Submodular Functions Everywhere
No full textURL to paper from conference siteSubmodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by
a (value) oracle. Many interesting problems involving
submodular functions can be solved using only polynomially many queries to the oracle, e.g., exact minimization or approximate maximization. In this paper, we consider the problem of approximating a non-negative, monotone, submodular function
f on a ground set of size n everywhere, after only poly(n)
oracle queries. Our main result is a deterministic algorithm that makes poly(n) oracle queries and derives a function ^ f such that, for every set S, ^ f(S) approximates f(S) within a factor alpha(n), where alpha(n) = [sqrt]n + 1
for rank functions of matroids and alpha(n) = O( [sqrt]n log n)
for general monotone submodular functions. Our result
is based on approximately finding a maximum volume
inscribed ellipsoid in a symmetrized polymatroid, and
the analysis involves various properties of submodular
functions and polymatroids. Our algorithm is tight up to logarithmic factors.
Indeed, we show that no algorithm can achieve a factor
better than Omega([sqrt]n= log n), even for rank functions of a
matroid.National Science Foundation (U.S.) (CCF-0515221)National Science Foundation (U.S.) (CCF-0829878)United States. Office of Naval Research (N00014-05-1-0148
Appropriate Similarity Measures for Author Cocitation Analysis
No full textWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
The vanishing author in computer-generated works: a critical analysis of recent Australian case law
No full textAbstract
The use of software is ubiquitous in the creation of many copyright works, yet the requirement in copyright law that every work have a human author who engages in independent intellectual effort means that its use may prevent copyright subsistence. Several recent Australian cases have refocused attention on authorship as an essential criterion of copyright subsistence, and these cases suggest that much computer-produced output may be authorless and thus lack copyright protection. This article, the first in a two-part series, analyses how each case deals with the question of authorship of computer-produced works and why the use of software diminishes copyright protection for a significant number of computer-generated works. The article critiques the application of conventional notions of human authorship developed in the pre-computer age to modern productions and suggests alternative approaches to authorship that satisfy both the major objectives of copyright policy and the need to adapt to the computer age. The article argues that, without a broader judicial approach to authorship of computer-generated works, Parliament must remedy the lacuna in protection for these ‘authorless’ works. Possible solutions for reform are suggested. In a forthcoming article, the author comprehensively examines those reform proposals
- …
