Grzegorz Świrszcz
Grzegorz Świrszcz has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Tomasz Nowicki
IBM Thomas J. Watson Research Center, Yorktown Heights, USA
4 shared publications - R. L. Adler
IBM, TJ Watson Research Center, Yorktown Heights, NY 10598-0218, USA
2 shared publications - Tomasz Maszczyk2 shared publications
Charles Tresser
IBM T. J. Watson Research Center 33-210
1 shared publication- Charles Tresser
IBM, TJ Watson Research Center, Yorktown Heights, NY 10598-0218, USA
1 shared publication - Claudia Perlich
IBM T.J. Watson Research Center
1 shared publication
Latest Publications
- 11 July 2017
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 221 (1) , 445-469
Error diffusion on acute simplices: invariant tiles
- 11 July 2017
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 221 (1) , 445-469
Error diffusion on acute simplices: invariant tiles
- 28 March 2013
- Published by Springer Nature in Mathematical Programming
- Vol. 145 (1-2) , 483-508
Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
- 28 March 2013
- Published by Springer Nature in Mathematical Programming
- Vol. 145 (1-2) , 483-508
Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
- 23 December 2009
- Published by Springer Nature in Data Mining and Knowledge Discovery
- Vol. 20 (3) , 439-468
Medical data mining: insights from winning two competitions
- 23 December 2009
- Published by Springer Nature in Data Mining and Knowledge Discovery
- Vol. 20 (3) , 439-468
Medical data mining: insights from winning two competitions
- 30 September 2009
- Published by Cambridge University Press (CUP) in Ergodic Theory and Dynamical Systems
- Vol. 30 (4) , 957-972
Convex dynamics with constant input
In Adler et al [Convex dynamics and applications. Ergod. Th. & Dynam. Sys.25 (2005), 321–352] certain piecewise linear maps were defined in terms of a convex polytope. When the convex polytope is a simplex, the resulting map has a dual nature. On one hand it is defined on ℝN and acts as a piecewise translation. On the other it can be viewed as a translation on the N-torus. What relates its two roles? A natural answer would be that there exists an invariant fundamental set into which all orbits under piecewise translation eventually enter. We prove this for N=1 and for acute and right triangles—i.e. non-obtuse triangles. We leave open the case of obtuse triangles and higher-dimensional simplices. Another question not treated is the connectivity of the invariant fundamental sets which arise.
- 30 September 2009
- Published by Cambridge University Press (CUP) in Ergodic Theory and Dynamical Systems
- Vol. 30 (4) , 957-972
Convex dynamics with constant input
In Adler et al [Convex dynamics and applications. Ergod. Th. & Dynam. Sys.25 (2005), 321–352] certain piecewise linear maps were defined in terms of a convex polytope. When the convex polytope is a simplex, the resulting map has a dual nature. On one hand it is defined on ℝN and acts as a piecewise translation. On the other it can be viewed as a translation on the N-torus. What relates its two roles? A natural answer would be that there exists an invariant fundamental set into which all orbits under piecewise translation eventually enter. We prove this for N=1 and for acute and right triangles—i.e. non-obtuse triangles. We leave open the case of obtuse triangles and higher-dimensional simplices. Another question not treated is the connectivity of the invariant fundamental sets which arise.
- 1 October 2008
- Published by Cambridge University Press (CUP) in Ergodic Theory and Dynamical Systems
- Vol. 28 (5) , 1479-1495
Invariant probability measures and dynamics of exponential linear type maps
We consider the problem of the asymptotic size of the random maximum-weight matching of a sparse random graph, which we translate into dynamics of the operator in the space of distribution functions. A tight condition for the uniqueness of the globally attracting fixed point is provided, which extends the result of Karp and Sipser [Maximum matchings in sparse random graphs. 22nd Ann. Symp. on Foundations of Computer Science (Nashville, TN, 28–30 October, 1981). IEEE, New York, 1981, pp. 364–375] from deterministic weight distributions (Dirac measures μ) to general ones. Given a probability measure μ which corresponds to the weight distribution of a link of a random graph, we form a positive linear operator Φμ (convolution) on distribution functions and then analyze a family of its exponents, with parameter λ, which corresponds to the connectivity of a sparse random graph. The operator 𝕋 relates the distribution F on the subtrees to the distribution 𝕋F on the node of the tree by 𝕋F=exp (−λΦμF). We prove that for every probability measure μ and every λ<e, there exists a unique globally attracting fixed point of the operator; the probability measure corresponding to this fixed point can then be used to compute the expected maximum-weight matching on a sparse random graph. This result is called the e-cutoff phenomenon. For deterministic distributions and λ>e, there is no fixed point attractor. We further establish that the uniqueness of the invariant measure of the underlying operator is not a monotone property of the average connectivity; this parallels similar non-monotonicity results in the statistical physics context.
- 1 October 2008
- Published by Cambridge University Press (CUP) in Ergodic Theory and Dynamical Systems
- Vol. 28 (5) , 1479-1495
Invariant probability measures and dynamics of exponential linear type maps
We consider the problem of the asymptotic size of the random maximum-weight matching of a sparse random graph, which we translate into dynamics of the operator in the space of distribution functions. A tight condition for the uniqueness of the globally attracting fixed point is provided, which extends the result of Karp and Sipser [Maximum matchings in sparse random graphs. 22nd Ann. Symp. on Foundations of Computer Science (Nashville, TN, 28–30 October, 1981). IEEE, New York, 1981, pp. 364–375] from deterministic weight distributions (Dirac measures μ) to general ones. Given a probability measure μ which corresponds to the weight distribution of a link of a random graph, we form a positive linear operator Φμ (convolution) on distribution functions and then analyze a family of its exponents, with parameter λ, which corresponds to the connectivity of a sparse random graph. The operator 𝕋 relates the distribution F on the subtrees to the distribution 𝕋F on the node of the tree by 𝕋F=exp (−λΦμF). We prove that for every probability measure μ and every λ<e, there exists a unique globally attracting fixed point of the operator; the probability measure corresponding to this fixed point can then be used to compute the expected maximum-weight matching on a sparse random graph. This result is called the e-cutoff phenomenon. For deterministic distributions and λ>e, there is no fixed point attractor. We further establish that the uniqueness of the invariant measure of the underlying operator is not a monotone property of the average connectivity; this parallels similar non-monotonicity results in the statistical physics context.
- Open Access
- 1 April 2008
- Published by Walter de Gruyter GmbH in Demonstratio Mathematica
- Vol. 41 (2) , 473-480
SOME REMARKS ON ORIGAMI AND ITS LIMITATIONS
- 1 April 2008
- Published by Walter de Gruyter GmbH in Demonstratio Mathematica
- Vol. 41 (2) , 473-480
Open AccessSOME REMARKS ON ORIGAMI AND ITS LIMITATIONS
- Open Access
- 1 January 2008
- Published by Walter de Gruyter GmbH in Demonstratio Mathematica
- Vol. 41 (2) , 473-481
Some remarks on Origami and its limitations
From a mathematical point of view the Japanese art of Origami is an art of finding isometric injections of subsets of ℝ
- 1 January 2008
- Published by Walter de Gruyter GmbH in Demonstratio Mathematica
- Vol. 41 (2) , 473-481
Open AccessSome remarks on Origami and its limitations
From a mathematical point of view the Japanese art of Origami is an art of finding isometric injections of subsets of ℝ
- 15 October 2006
- Published by Elsevier in Journal of Differential Equations
- Vol. 229 (2) , 529-537
Relationships between limit cycles and algebraic invariant curves for quadratic systems
- 15 October 2006
- Published by Elsevier in Journal of Differential Equations
- Vol. 229 (2) , 529-537
Relationships between limit cycles and algebraic invariant curves for quadratic systems
- 24 May 2005
- Published by Wiley in Random Structures & Algorithms
- Vol. 28 (1) , 76-106
Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
LetG(n,c/n) andGr(n) be ann‐node sparse random graph and a sparse randomr‐regular graph, respectively, and letI(n,r) andI(n,c) be the sizes of the largest independent set inG(n,c/n) andGr(n). The asymptotic value ofI(n,c)/nasn→ ∞, can be computed using the Karp‐Sipser algorithm whenc≤e. For random cubic graphs,r= 3, it is only known that .432 ≤ lim infnI(n,3)/n≤ lim supnI(n,3)/n≤ .4591 with high probability (w.h.p.) asn→ ∞, as shown in Frieze and Suen [Random Structures Algorithms 5 (1994), 649–664] and Bollabas [European J Combin 1 (1980), 311–316], respectively. In this paper we assume in addition that the nodes of the graph are equipped with nonnegative weights, independently generated according to some common distribution, and we consider instead the maximum weight of an independent set. Surprisingly, we discover that for certain weight distributions, the limit limnI(n,c)/ncan be computed exactly even whenc>e, and limnI(n,r)/ncan be computed exactly for somer≥ 1. For example, when the weights are exponentially distributed with parameter 1, limnI(n,2e)/n≈ .5517, and limnI(n,3)/n≈ .6077. Our results are established using the recently developedlocal weak convergencemethod further reduced to a certainlocal optimalityproperty exhibited by the models we consider. We extend our results to maximum weight matchings inG(n,c/n) andGr(n). For the case of exponential distributions, we compute the corresponding limits for everyc> 0 and everyr≥ 2. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006
- 24 May 2005
- Published by Wiley in Random Structures & Algorithms
- Vol. 28 (1) , 76-106
Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
LetG(n,c/n) andGr(n) be ann‐node sparse random graph and a sparse randomr‐regular graph, respectively, and letI(n,r) andI(n,c) be the sizes of the largest independent set inG(n,c/n) andGr(n). The asymptotic value ofI(n,c)/nasn→ ∞, can be computed using the Karp‐Sipser algorithm whenc≤e. For random cubic graphs,r= 3, it is only known that .432 ≤ lim infnI(n,3)/n≤ lim supnI(n,3)/n≤ .4591 with high probability (w.h.p.) asn→ ∞, as shown in Frieze and Suen [Random Structures Algorithms 5 (1994), 649–664] and Bollabas [European J Combin 1 (1980), 311–316], respectively. In this paper we assume in addition that the nodes of the graph are equipped with nonnegative weights, independently generated according to some common distribution, and we consider instead the maximum weight of an independent set. Surprisingly, we discover that for certain weight distributions, the limit limnI(n,c)/ncan be computed exactly even whenc>e, and limnI(n,r)/ncan be computed exactly for somer≥ 1. For example, when the weights are exponentially distributed with parameter 1, limnI(n,2e)/n≈ .5517, and limnI(n,3)/n≈ .6077. Our results are established using the recently developedlocal weak convergencemethod further reduced to a certainlocal optimalityproperty exhibited by the models we consider. We extend our results to maximum weight matchings inG(n,c/n) andGr(n). For the case of exponential distributions, we compute the corresponding limits for everyc> 0 and everyr≥ 2. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006