2,698 research outputs found
LP-Relaxations for Tree Augmentation
No full textIn the Tree Augmentation Problem (TAP) the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T+F is 2-edge-connected. The best approximation ratio known for TAP is 1.5. In the more general Weighted TAP problem, F should be of minimum weight. Weighted TAP admits several 2-approximation algorithms w.r.t. the standard cut-LP relaxation. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than 2 is not known. Improving this "natural" ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is an old open problem even for TAP. In this paper we introduce two different LP-relaxations, and for each of them give a simple algorithm that computes a feasible solution for TAP of size at most 7/4 times the optimal LP value. This gives some hope to break the ratio 2 for the weighted case
On the Concavity of Delivery Games
No full textDelivery games, introduced by Hamers, Borm, van de Leensel and Tijs (1994), are combinatorial optimization games that arise from delivery problems closely related to the Chinese postman problem (CPP). They showed that delivery games are not necessarily balanced. For delivery problems corresponding to the class of bridge-connected Euler graphs they showed that the related games are balanced. This paper focuses on the concavity property for delivery games. A delivery game arising from a delivery model corresponding to a bridge-connected Euler graph needs not to be concave. The main result will be that for delivery problems corresponding to the class of bridge-connected cyclic graphs, which is a subclass of the class of bridge-connected Euler graphs, the related delivery games are concave.
LP Decoding Excess over Symmetric Channels
No full textWe consider the problem of Linear Programming (LP) decoding of binary linear codes. The LP excess lemma was introduced by the first author, B. Ghazi, and R. Urbanke (IEEE Trans. Inf. Th., 2014) as a technique to trade crossover probability for 'LP excess' over the Binary Symmetric Channel. We generalize the LP excess lemma to discrete, binary-input, Memoryless, Symmetric and LLR-Bounded (MSB) channels. As an application, we extend a result by the first author and H. Audah (IEEE Trans. Inf. Th., 2015) on the impact of redundant checks on LP decoding to discrete MSB channels. © 2015 IEEE
A Sobolev estimate for radial lp-multipliers on a class of semi-simple lie groups
No full textLet G be a semi-simple Lie group in the Harish-Chandra class with maximal compact subgroup K. Let ΩK be minus the radial Casimir operator. Let 1 4 dim(G/K) < SG < 1 2 dim(G/K), s ∈ (0, SG] and p ∈ (1,∞) be such that(1 p - 1 2 )< s 2SG . Then, there exists a constant CG,s,p > 0 such that for every m ∈ L∞(G) ∩ L2(G) bi-K-invariant with m ∈ Dom(Ωs K) and Ωs K(m) ∈ L2SG/s(G) we have, (0.1) ∥Tm : Lp(G) → Lp( G)∥ ≤ CG,s,p∥Ωs K(m)∥ L2SG/s(G), where Tm is the Fourier multiplier with symbol m acting on the noncommutative Lp-space of the group von Neumann algebra of G. This gives new examples of Lp-Fourier multipliers with decay rates becoming slower when p approximates 2.Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Analysi
Stability properties of stochastic maximal Lp-regularity
No full textIn this paper we consider Lp-regularity estimates for solutions to stochastic evolution equations, which is called stochastic maximal Lp-regularity. Our aim is to find a theory which is analogously to Dore’s theory for deterministic evolution equations. He has shown that maximal Lp-regularity is independent of the length of the time interval, implies analyticity and exponential stability of the semigroup, is stable under perturbation and many more properties. We show that the stochastic versions of these results hold
A 1.75 LP approximation for the Tree Augmentation Problem
No full textIn the Tree Augmentation Problem (TAP) the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T ∪F is 2-edge-connected. The best approximation ratio known for TAP is 1.5. In the more general Weighted TAP problem, F should be of minimum weight. Weighted TAP admits several 2-approximation algorithms w.r.t. to the standard cut LP-relaxation, but for all of them the performance ratio of 2 is tight even for TAP. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than 2 is not known. Improving this “natural” ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is a long time open problem even for TAP, studied by various researchers. In this paper we introduce such an LP-relaxation and give an algorithm that computes a feasible solution for TAP of size at most 1.75 times the optimal LP value. This gives some hope to break the ratio 2 for the weighted case. Our algorithm computes some initial edge set by solving a partial system of constraints that form the integral edge-cover polytope, and then applies local search on 3-leaf subtrees to exchange some of the edges and to add additional edges. Thus we do not need to solve the LP, and the algorithm runs roughly in time required to find a minimum edge-cover in a general graph
PROPAGATION OF LP//0//1 AND LP//1//1 MODES IN COUPLED OPTICAL FIBERS.
No full textThe author studied the propagation of the fundamental mode, called the LP//0//1 mode, of a single-mode optical fiber and the LP//1//1 mode, the next higher-order mode, in two long lengths of fiber coupled together. This was done by launching light having a wavelength below the cut-off wavelength of the fiber. The effect of lateral misalignment at the coupled junctions was investigated. The results are explained in terms of excitation of the modes at this junction
Life of a Yellow Kid: an audiovisual electro-pop LP
No full textThe basis of this project is to compose, record, produce and mix an eleven song album (LP) with a visualizer, logo and design for each track. The author designed all of the artworks for the songs and LP and produced videos and content for said LP. Also, the author combined all of his influences from electronic music and other genres to create something new to expand the limits of electronic music. This album was influenced by works of artists like Madeon, Porter Robinson, Louis The Child, Urboi, Medasin, Fred Again.. and The Weeknd. Song-writing, recording, sound design, creative production techniques, mixing, graphic design and audiovisual production were the skills and tools necessary for the completion of this LP. The main focus of the LP was to combine different genres of music, like Electro-pop, UK Garage, Pop, House and Drum and Bass. Also this album is about personal experiences of the author and it covers different feelings throughout the LP, creating a sunset literally and figuratively within the album.
This paper was written without any assistance from generative artificial intelligence.https://remix.berklee.edu/graduate-studies-production-technology/1378/thumbnail.jp
Tеорема Литтлвуда - Пелі про простори Lp(t)(ℝⁿ)
No full textWe point out that if the Hardy–Littlewood maximal operator is bounded on the space Lp(t)(ℝ), 1 1 , the Littlewood–Paley operator is bounded on Lp(t) (ℝⁿ), 1 1, оператор Літтлвуда - Пелі обмежений на Lp(t)(Rⁿ),1 < a ≤ p(t) ≤ b<∞,t ∈ R, тоді і тільки тоді, коли p(t)= const.The author was supported by grant GNSF / STO 7 / 3-171
Tеорема Литтлвуда - Пелі про простори Lp(t)(ℝⁿ)
No full textWe point out that if the Hardy–Littlewood maximal operator is bounded on the space Lp(t)(ℝ), 1 1 , the Littlewood–Paley operator is bounded on Lp(t) (ℝⁿ), 1 1, оператор Літтлвуда - Пелі обмежений на Lp(t)(Rⁿ),1 < a ≤ p(t) ≤ b<∞,t ∈ R, тоді і тільки тоді, коли p(t)= const.The author was supported by grant GNSF / STO 7 / 3-171
- …
