SwePub
Sök i SwePub databas

  Utökad sökning

Träfflista för sökning "AMNE:(NATURVETENSKAP Matematik Diskret matematik) ;pers:(Larsson Joel 1987)"

Sökning: AMNE:(NATURVETENSKAP Matematik Diskret matematik) > Larsson Joel 1987

  • Resultat 1-7 av 7
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
1.
  • Falgas-Ravry, Victor, et al. (författare)
  • Speed and concentration of the covering time for structured coupon collectors
  • 2020
  • Ingår i: Advances in Applied Probability. - : Cambridge University Press. - 0001-8678 .- 1475-6064. ; 52:2, s. 433-462
  • Tidskriftsartikel (refereegranskat)abstract
    • Let V be an n-set, and let X be a random variable taking values in the powerset of V. Suppose we are given a sequence of random coupons X1,X2,…, where the Xi are independent random variables with distribution given by X. The covering time T is the smallest integer t≥0 such that ⋃ti=1Xi=V. The distribution of T is important in many applications in combinatorial probability, and has been extensively studied. However the literature has focussed almost exclusively on the case where X is assumed to be symmetric and/or uniform in some way.In this paper we study the covering time for much more general random variables X; we give general criteria for T being sharply concentrated around its mean, precise tools to estimate that mean, as well as examples where T fails to be concentrated and when structural properties in the distribution of X allow for a very different behaviour of T relative to the symmetric/uniform case.
  •  
2.
  • Larsson, Joel, 1987-, et al. (författare)
  • Biased random k-SAT
  • Annan publikation (övrigt vetenskapligt/konstnärligt)
  •  
3.
  • Larsson, Joel, 1987-, et al. (författare)
  • Biased random k-SAT
  • 2021
  • Ingår i: Random structures & algorithms (Print). - : John Wiley & Sons. - 1042-9832 .- 1098-2418. ; 59:2, s. 238-266
  • Tidskriftsartikel (refereegranskat)abstract
    • The basic random k‐SAT problem is: given a set of n Boolean variables, and m clauses of size k picked uniformly at random from the set of all such clauses on our variables, is the conjunction of these clauses satisfiable? Here we consider a variation of this problem where there is a bias towards variables occurring positive—that is, variables occur negated w.p. 0<p<½  and positive otherwise—and study how the satisfiability threshold depends on p. For p<½ this model breaks many of the symmetries of the original random k‐SAT problem, for example, the distribution of satisfying assignments in the Boolean cube is no longer uniform. For any fixed k, we find the asymptotics of the threshold as p approaches 0 or ½ . The former confirms earlier predictions based on numerical studies and heuristic methods from statistical physics.
  •  
4.
  • Larsson, Joel, 1987- (författare)
  • On random cover and matching problems
  • 2016
  • Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
    • This thesis consists of the following papers.I  J. Larsson, The Minimum Matching in Pseudo-dimension 0 < q < 1, submittedII  V. Falgas-Ravry, J. Larsson, K. Markström, Speed and concentration of the covering time for structured coupon collectors, submittedIII  J. Larsson, K. Markström, Biased random k-SAT problems, manuscriptThese papers can all be seen as variations on the same question: Given a large set V and a family F of subsets of V, each assigned a (random) weight, we assign each subfamily G ⊆ F a cost based on the weights of sets that occur in it. What will the minimal cost of a subfamiliy G that covers V be?In the first paper, we search for a disjoint cover of the ground set V = {u_1,u_2,...u_n,v_1,v_2,...v_n}, using random 2-sets of the form {u_i, v_j}. In other words, we search for matchings in a bipartite graph. Each edge receives a random weight distributed uniformly in [0, 1], and the cost of a perfect matching using edges with weights l_1,l_2,...l_n is Σ_{i=1}^n l_i^{1/q} for some q > 0.The second paper lives in a more general setting. There we search for any cover of the ground set V, for general families F. Each set f ∈ F receives weight w(f) uniformly at random from [0,1]. The cost of a cover f_1,f_2,...f_m is then taken to be max_i w(f_i). This is equivalent (after a rescaling) to drawing sets from F at Poisson times, and the cost of a cover is the first time V is covered. This problem is known under a number of names, perhaps most famously the coupon collector problem. In the classical formulation, single elements of V are drawn, not sets. The classical coupon collector thus corresponds to the family F consisting of singleton sets, and we call the version allowing larger sets structured coupon collector problems. The main concern of this paper is to identify relevant properties of F that affect the covering time (i.e. minimal cost of a cover), and to provide (easily checkable) sufficient conditions for concentration of the covering time.For the third paper we narrow the scopes once more, and study the biased random k-SAT problem. The random k-SAT problem can be seen as a special case of the structured coupon collector, but a special case that has far richer structure than the generic case. The ground set is the hypercube Σ_n = {0, 1}^n, and the coupons are all the k-codimensional subcubes of Σ_n. We study a slight variation on this problem: subcubes are drawn with a constant bias towards 0, so that vertices in Σ_n with fewer 1's and more 0's are easier to cover.
  •  
5.
  • Larsson, Joel, 1987- (författare)
  • On random satisfiability and optimization problems
  • 2018
  • Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
    • In Paper I, we study the following optimization problem: in the complete bipartite graph where edges are given i.i.d. weights of pseudo-dimension q>0, find a perfect matching with minimal total weight. The generalized Mézard-Parisi conjecture states that the limit of this minimum exists and is given by the solution to a certain functional equation. This conjecture has been confirmed for q=1 and for q>1. We prove it for the last remaining case 0<q<1.In Paper II, we study generalizations of the coupon collector problem. Versions of this problem shows up naturally in various context and has been studied since the 18th century. Our focus is on using existing methods in greater generality in a unified way, so that others can avoid ad-hoc solutions.Papers III & IV concerns the satisfiability of random Boolean formulas. The classic model is to pick a k-CNF with m clauses on n variables uniformly at random from all such formulas. As the ratio m/n increases, the formulas undergo a sharp transition from satisfiable (w.h.p.) to unsatisfiable (w.h.p.). The critical ratio for which this occurs is called the satisfiability threshold.We study two variations where the signs of variables in clauses are not chosen uniformly. In paper III, variables are biased towards occuring pure rather than negated. In paper IV, there are two types of clauses, with variables in them biased in opposite directions. We relate the thresholds of these models to the threshold of the classical model.
  •  
6.
  • Larsson, Joel, 1987-, et al. (författare)
  • Polarized random k-SAT
  • Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
    • We introduce a variation of the random k-SAT problem, which we call polarized random k-SAT. In polarized random k-SAT we have a polarization parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p = 1/2 we get the classical random k-SAT model.Of particular interest is the fully polarized model where p = 0. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated.We show that the threshold of satisfiability does not decrease as p moves away from 1. Thus the satisfiability threshold for polarized random k-SAT is an upper bound on the threshold for the classical random k-SAT. We also conjecture that the two thresholds coincide.
  •  
7.
  • Larsson, Joel, 1987- (författare)
  • The Minimum Perfect Matching in Pseudo-dimension 0<q<1
  • Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
    • It is known that for Kn,n equipped with i.i.d. exp(1) edge costs, the minimum total cost of a perfect matching converges to π2/6 in probability. Similar convergence has been established for all edge cost distributions of pseudo-dimension q≥1, such as Weibull(1,q) costs. In this paper we extend those results all q>0, confirming the Mézard-Parisi conjecture in the last remaining applicable case.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-7 av 7

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy