X

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Online Resource
    Online Resource
    A spectral algorithm for learning mixture models
    Elsevier BV ; 2004
    In:  Journal of Computer and System Sciences Vol. 68, No. 4 ( 2004-06), p. 841-860
    Details
    In: Journal of Computer and System Sciences, Elsevier BV, Vol. 68, No. 4 ( 2004-06), p. 841-860
    Type of Medium: Online Resource
    ISSN: 0022-0000
    URL: Article
    DOI: 10.1016/j.jcss.2003.11.008
    RVK:
    SA 6200
    Language: English
    Publisher: Elsevier BV
    Publication Date: 2004
    detail.hit.zdb_id: 1469171-1
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Online Resource
    Open Access Request
    Availability (electronic / print)
  • 2
    Online Resource
    Online Resource
    The Cutting Plane Method is Polynomial for Perfect Matchings
    Institute for Operations Research and the Management Sciences (INFORMS) ; 2016
    In:  Mathematics of Operations Research Vol. 41, No. 1 ( 2016-02), p. 23-48
    Details
    In: Mathematics of Operations Research, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 41, No. 1 ( 2016-02), p. 23-48
    Abstract: The cutting plane approach to finding minimum-cost perfect matchings has been discussed by several authors over past decades. Its convergence has been an open question. We develop a cutting plane algorithm that converges in polynomial-time using only Edmonds’ blossom inequalities, and which maintains half-integral intermediate LP solutions supported by a disjoint union of odd cycles and edges. Our main insight is a method to retain only a subset of the previously added cutting planes based on their dual values. This allows us to quickly find violated blossom inequalities and argue convergence by tracking the number of odd cycles in the support of intermediate solutions.
    Type of Medium: Online Resource
    ISSN: 0364-765X , 1526-5471
    URL: Article
    DOI: 10.1287/moor.2015.0714
    Language: English
    Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
    Publication Date: 2016
    detail.hit.zdb_id: 2004273-5
    detail.hit.zdb_id: 195683-8
    SSG: 3,2
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Online Resource
    Open Access Request
    Availability (electronic / print)
  • 3
    Online Resource
    Online Resource
    Algorithmic Prediction of Health-Care Costs
    Institute for Operations Research and the Management Sciences (INFORMS) ; 2008
    In:  Operations Research Vol. 56, No. 6 ( 2008-12), p. 1382-1392
    Details
    In: Operations Research, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 56, No. 6 ( 2008-12), p. 1382-1392
    Abstract: The rising cost of health care is one of the world's most important problems. Accordingly, predicting such costs with accuracy is a significant first step in addressing this problem. Since the 1980s, there has been research on the predictive modeling of medical costs based on (health insurance) claims data using heuristic rules and regression methods. These methods, however, have not been appropriately validated using populations that the methods have not seen. We utilize modern data-mining methods, specifically classification trees and clustering algorithms, along with claims data from over 800,000 insured individuals over three years, to provide rigorously validated predictions of health-care costs in the third year, based on medical and cost data from the first two years. We quantify the accuracy of our predictions using unseen (out-of-sample) data from over 200,000 members. The key findings are: (a) our data-mining methods provide accurate predictions of medical costs and represent a powerful tool for prediction of health-care costs, (b) the pattern of past cost data is a strong predictor of future costs, and (c) medical information only contributes to accurate prediction of medical costs of high-cost members.
    Type of Medium: Online Resource
    ISSN: 0030-364X , 1526-5463
    URL: Article
    DOI: 10.1287/opre.1080.0619
    RVK:
    SA 7410
    Language: English
    Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
    Publication Date: 2008
    detail.hit.zdb_id: 2019440-7
    detail.hit.zdb_id: 123389-0
    SSG: 3,2
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Online Resource
    Open Access Request
    Availability (electronic / print)
  • 4
    Online Resource
    Online Resource
    Query Complexity of Sampling and Small Geometric Partitions
    Cambridge University Press (CUP) ; 2015
    In:  Combinatorics, Probability and Computing Vol. 24, No. 5 ( 2015-09), p. 733-753
    Details
    In: Combinatorics, Probability and Computing, Cambridge University Press (CUP), Vol. 24, No. 5 ( 2015-09), p. 733-753
    Abstract: In this paper we study the following problem. Discrete partitioning problem (DPP) . Let $\mathbb{F}_q$ P n denote the n -dimensional finite projective space over $\mathbb{F}_q$ . For positive integer k ⩽ n , let { A i } i = 1 N be a partition of ( $\mathbb{F}_q$ P n ) k such that: (1) for all i ⩽ N , A i = ∏ j =1 k A j i (partition into product sets), (2) for all i ⩽ N , there is a ( k − 1)-dimensional subspace L i ⊆ $\mathbb{F}_q$ P n such that A i ⊆ ( L i ) k . What is the minimum value of N as a function of q, n, k ? We will be mainly interested in the case k = n . DPP arises in an approach that we propose for proving lower bounds for the query complexity of generating random points from convex bodies. It is also related to other partitioning problems in combinatorics and complexity theory. We conjecture an asymptotically optimal partition for DPP and show that it is optimal in two cases: when the dimension is low ( k = n = 2) and when the factors of the parts are structured, namely factors of a part are close to being a subspace. These structured partitions arise naturally as partitions induced by query algorithms. Our problem does not seem to be directly amenable to previous techniques for partitioning lower bounds such as rank arguments, although rank arguments do lie at the core of our techniques.
    Type of Medium: Online Resource
    ISSN: 0963-5483 , 1469-2163
    URL: Article
    DOI: 10.1017/S0963548314000704
    Language: English
    Publisher: Cambridge University Press (CUP)
    Publication Date: 2015
    detail.hit.zdb_id: 1481145-5
    SSG: 17,1
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Online Resource
    Open Access Request
    Availability (electronic / print)
  • 5
    Online Resource
    Online Resource
    Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
    Association for Computing Machinery (ACM) ; 2017
    In:  Journal of the ACM Vol. 64, No. 2 ( 2017-04-30), p. 1-37
    Details
    In: Journal of the ACM, Association for Computing Machinery (ACM), Vol. 64, No. 2 ( 2017-04-30), p. 1-37
    Abstract: We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, for example, moments-based methods, local search, standard iterative methods for convex optimization, MCMC, and simulated annealing, can be implemented in this framework. Our framework is based on, and generalizes, the statistical query model in learning theory [Kearns 1998]. Our main application is a nearly optimal lower bound on the complexity of any statistical query algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size O ( n 1/2 − δ ) for any constant δ 〉 0. The assumed hardness of variants of these problems has been used to prove hardness of several other problems and as a guarantee for security in cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.
    Type of Medium: Online Resource
    ISSN: 0004-5411 , 1557-735X
    URL: Article
    DOI: 10.1145/3046674
    RVK:
    SA 3010
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2017
    detail.hit.zdb_id: 2006500-0
    detail.hit.zdb_id: 6759-3
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Online Resource
    Open Access Request
    Availability (electronic / print)
  • 6
    Online Resource
    Online Resource
    Usability of Humanly Computable Passwords
    Association for the Advancement of Artificial Intelligence (AAAI) ; 2018
    In:  Proceedings of the AAAI Conference on Human Computation and Crowdsourcing Vol. 6 ( 2018-06-15), p. 174-183
    Details
    In: Proceedings of the AAAI Conference on Human Computation and Crowdsourcing, Association for the Advancement of Artificial Intelligence (AAAI), Vol. 6 ( 2018-06-15), p. 174-183
    Abstract: Reusing passwords across multiple websites is a common practice that compromises security. Recently, Blum and Vempala have proposed password strategies to help people calculate, in their heads, passwords for different sites without dependence on third-party tools or external devices. Thus far, the security and efficiency of these "mental algorithms" has been analyzed only theoretically. But are such methods usable? We present the first usability study of humanly computable password strategies, involving a learning phase (to learn a password strategy), then a rehearsal phase (to login to a few websites), and multiple follow-up tests. In our user study, with training, participants were able to calculate a deterministic eight-character password for an arbitrary new website in under 20 seconds.
    Type of Medium: Online Resource
    ISSN: 2769-1349 , 2769-1330
    URL: Article
    DOI: 10.1609/hcomp.v6i1.13333
    Language: Unknown
    Publisher: Association for the Advancement of Artificial Intelligence (AAAI)
    Publication Date: 2018
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Online Resource
    Open Access Request
    Availability (electronic / print)
  • 7
    Online Resource
    Online Resource
    CHRR: coordinate hit-and-run with rounding for uniform sampling of constraint-based models
    Oxford University Press (OUP) ; 2017
    In:  Bioinformatics Vol. 33, No. 11 ( 2017-06-01), p. 1741-1743
    Details
    In: Bioinformatics, Oxford University Press (OUP), Vol. 33, No. 11 ( 2017-06-01), p. 1741-1743
    Abstract: In constraint-based metabolic modelling, physical and biochemical constraints define a polyhedral convex set of feasible flux vectors. Uniform sampling of this set provides an unbiased characterization of the metabolic capabilities of a biochemical network. However, reliable uniform sampling of genome-scale biochemical networks is challenging due to their high dimensionality and inherent anisotropy. Here, we present an implementation of a new sampling algorithm, coordinate hit-and-run with rounding (CHRR). This algorithm is based on the provably efficient hit-and-run random walk and crucially uses a preprocessing step to round the anisotropic flux set. CHRR provably converges to a uniform stationary sampling distribution. We apply it to metabolic networks of increasing dimensionality. We show that it converges several times faster than a popular artificial centering hit-and-run algorithm, enabling reliable and tractable sampling of genome-scale biochemical networks. Availability and Implementation https://github.com/opencobra/cobratoolbox. Supplementary information Supplementary data are available at Bioinformatics online.
    Type of Medium: Online Resource
    ISSN: 1367-4803 , 1367-4811
    URL: Article
    DOI: 10.1093/bioinformatics/btx052
    Language: English
    Publisher: Oxford University Press (OUP)
    Publication Date: 2017
    detail.hit.zdb_id: 1468345-3
    SSG: 12
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Online Resource
    Open Access Request
    Availability (electronic / print)
  • 8
    Online Resource
    Online Resource
    On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
    Springer Science and Business Media LLC ; 2004
    In:  Mathematical Programming Vol. 100, No. 3 ( 2004-07)
    Details
    In: Mathematical Programming, Springer Science and Business Media LLC, Vol. 100, No. 3 ( 2004-07)
    Type of Medium: Online Resource
    ISSN: 0025-5610 , 1436-4646
    URL: Article
    DOI: 10.1007/s10107-004-0506-y
    RVK:
    SA 6810
    Language: English
    Publisher: Springer Science and Business Media LLC
    Publication Date: 2004
    detail.hit.zdb_id: 1463397-8
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Online Resource
    Open Access Request
    Availability (electronic / print)
  • 9
    Online Resource
    Online Resource
    An Efficient Rescaled Perceptron Algorithm for Conic Systems
    Institute for Operations Research and the Management Sciences (INFORMS) ; 2009
    In:  Mathematics of Operations Research Vol. 34, No. 3 ( 2009-08), p. 621-641
    Details
    In: Mathematics of Operations Research, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 34, No. 3 ( 2009-08), p. 621-641
    Abstract: The classical perceptron algorithm is an elementary row-action/relaxation algorithm for solving a homogeneous linear inequality system Ax 〉 0. A natural condition measure associated with this algorithm is the Euclidean width τ of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/τ 2 [see Rosenblatt, F. 1962. Principles of Neurodynamics. Spartan Books, Washington, DC]. Dunagan and Vempala [Dunagan, J., S. Vempala. 2007. A simple polynomial-time rescaling algorithm for solving linear programs. Math. Programming 114(1) 101–114] have developed a rescaled version of the perceptron algorithm with an improved complexity of O(n ln (1/τ)) iterations (with high probability), which is theoretically efficient in τ and, in particular, is polynomial time in the bit-length model. We explore extensions of the concepts of these perceptron methods to the general homogeneous conic system Ax ∈ int K, where K is a regular convex cone. We provide a conic extension of the rescaled perceptron algorithm based on the notion of a deep-separation oracle of a cone, which essentially computes a certificate of strong separation. We show that the rescaled perceptron algorithm is theoretically efficient if an efficient deep-separation oracle is available for the feasible region. Furthermore, when K is the cross-product of basic cones that are either half-spaces or second-order cones, then a deep-separation oracle is available and, hence, the rescaled perceptron algorithm is theoretically efficient. When the basic cones of K include semidefinite cones, then a probabilistic deep-separation oracle for K can be constructed that also yields a theoretically efficient version of the rescaled perceptron algorithm.
    Type of Medium: Online Resource
    ISSN: 0364-765X , 1526-5471
    URL: Article
    DOI: 10.1287/moor.1090.0388
    Language: English
    Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
    Publication Date: 2009
    detail.hit.zdb_id: 2004273-5
    detail.hit.zdb_id: 195683-8
    SSG: 3,2
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Online Resource
    Open Access Request
    Availability (electronic / print)
  • 10
    Online Resource
    Online Resource
    Stochastic Billiards for Sampling from the Boundary of a Convex Set
    Institute for Operations Research and the Management Sciences (INFORMS) ; 2015
    In:  Mathematics of Operations Research Vol. 40, No. 4 ( 2015-10), p. 888-901
    Details
    In: Mathematics of Operations Research, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 40, No. 4 ( 2015-10), p. 888-901
    Abstract: Stochastic billiards can be used for approximate sampling from the boundary of a bounded convex set through the Markov Chain Monte Carlo paradigm. This paper studies how many steps of the underlying Markov chain are required to get samples (approximately) from the uniform distribution on the boundary of the set, for sets with an upper bound on the curvature of the boundary. Our main theorem implies a polynomial-time algorithm for sampling from the boundary of such sets.
    Type of Medium: Online Resource
    ISSN: 0364-765X , 1526-5471
    URL: Article
    DOI: 10.1287/moor.2014.0701
    Language: English
    Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
    Publication Date: 2015
    detail.hit.zdb_id: 2004273-5
    detail.hit.zdb_id: 195683-8
    SSG: 3,2
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Online Resource
    Open Access Request
    Availability (electronic / print)
Nothing or not found what you are looking for? Please check your search query or use the Interlibrary Loan Search.
Close ⊗
This website uses cookies and the analysis tool Matomo. Further information can be found on the KOBV privacy pages