More Like this

1. Breaking the r _max Barrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem

   https://doi.org/10.1287/ijoc.2020.0975  

   Ran, Yingli; Zhang, Zhao; Tang, Shaojie; Du, Ding-Zhu (October 2020, INFORMS Journal on Computing)

   null (Ed.)

   Given an element set E of order n, a collection of subsets [Formula: see text], a cost c S on each set [Formula: see text], a covering requirement r e for each element [Formula: see text], and an integer k, the goal of a minimum partial set multicover problem (MinPSMC) is to find a subcollection [Formula: see text] to fully cover at least k elements such that the cost of [Formula: see text] is as small as possible and element e is fully covered by [Formula: see text] if it belongs to at least r e sets of [Formula: see text]. This problem generalizes the minimum k-union problem (MinkU) and is believed not to admit a subpolynomial approximation ratio. In this paper, we present a [Formula: see text]-approximation algorithm for MinPSMC, in which [Formula: see text] is the maximum size of a set in S. And when [Formula: see text], we present a bicriteria algorithm fully covering at least [Formula: see text] elements with approximation ratio [Formula: see text], where [Formula: see text] is a fixed number. These results are obtained by studying the minimum density subcollection problem with (or without) cardinality constraint, which might be of interest by itself. 

   more » « less
2. THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES

   https://doi.org/10.1017/jsl.2025.11  

   DZHAFAROV, DAMIR D; SOLOMON, REED; VALENTI, MANLIO (February 2025, The Journal of Symbolic Logic)

   Abstract We study versions of the tree pigeonhole principle,$$\mathsf {TT}^1$$, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether$$\mathsf {TT}^1$$is$$\Pi ^1_1$$-conservative over the ordinary pigeonhole principle,$$\mathsf {RT}^1$$. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination with other results, we use this to show that unlike$$\mathsf {RT}^1$$, the problem$$\mathsf {TT}^1$$is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of$$\mathsf {TT}^1$$. 

   more » « less
3. Minimum norm interpolation in the ℓ1(ℕ) space

   https://doi.org/10.1142/S0219530520400059  

   Cheng, Raymond; Xu, Yuesheng (January 2021, Analysis and Applications)

   null (Ed.)

   We consider the minimum norm interpolation problem in the [Formula: see text] space, aiming at constructing a sparse interpolation solution. The original problem is reformulated in the pre-dual space, thereby inducing a norm in a related finite-dimensional Euclidean space. The dual problem is then transformed into a linear programming problem, which can be solved by existing methods. With that done, the original interpolation problem is reduced by solving an elementary finite-dimensional linear algebra equation. A specific example is presented to illustrate the proposed method, in which a sparse solution in the [Formula: see text] space is compared to the dense solution in the [Formula: see text] space. This example shows that a solution of the minimum norm interpolation problem in the [Formula: see text] space is indeed sparse, while that of the minimum norm interpolation problem in the [Formula: see text] space is not. 

   more » « less
4. The structure of the singular set in the thin obstacle problem for degenerate parabolic equations

   https://doi.org/10.1007/s00526-021-01938-2  

   Banerjee, Agnid; Danielli, Donatella; Garofalo, Nicola; Petrosyan, Arshak (April 2021, Calculus of Variations and Partial Differential Equations)

   Abstract We study the singular set in the thin obstacle problem for degenerate parabolic equations with weight$$|y|^a$$ ${\left|y\right|}^a$for$$a \in (-1,1)$$ $a\in (-1,1)$. Such problem arises as the local extension of the obstacle problem for the fractional heat operator$$(\partial _t - \Delta _x)^s$$ ${({\partial }_t-{\Delta }_x)}^s$for$$s \in (0,1)$$ $s\in (0,1)$. Our main result establishes the complete structure and regularity of the singular set of the free boundary. To achieve it, we prove Almgren-Poon, Weiss, and Monneau type monotonicity formulas which generalize those for the case of the heat equation ($$a=0$$ $a=0$). 

   more » « less
5. Solvability of the $$\mathrm{L}^{p}$$ Dirichlet problem for the heat equation is equivalent to parabolic uniform rectifiability in the case of a parabolic Lipschitz graph

   https://doi.org/10.1007/s00222-024-01300-1  

   Bortz, Simon; Hofmann, Steve; Martell, José María; Nyström, Kaj (January 2025, Inventiones mathematicae)

   Abstract We prove that if a parabolic Lipschitz (i.e., Lip(1,1/2)) graph domain has the property that its caloric measure is parabolic$$A_{\infty }$$ $A_{\infty }$with respect to surface measure (which property is in turn equivalent to$$\mathrm{L}^{p}$$ $L^p$solvability of the Dirichlet problem for some finite$$p$$ $p$), then the function defining the graph has a half-order time derivative in the space of (parabolic) bounded mean oscillation. Equivalently, we prove that the$$A_{\infty }$$ $A_{\infty }$property of caloric measure implies, in this case, that the boundary is parabolic uniformly rectifiable. Consequently, by combining our result with the work of Lewis and Murray we resolve a long standing open problem in the field by characterizing those parabolic Lipschitz graph domains for which one has$$\mathrm{L}^{p}$$ $L^p$solvability (for some$$p <\infty $$ $p<\infty$) of the Dirichlet problem for the heat equation. The key idea of our proof is to view the level sets of the Green function as extensions of the original boundary graph for which we can prove (local) square function estimates of Littlewood-Paley type. 

   more » « less