搜索结果：Minimum

In this paper, we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global minimum cut problem is asymptotically better than the fastest sequential deterministic global minimum cut algorithm (Henzinger, Li, Rao, Wang; SODA 2024). Furthermore, we implement our algorithm in sequential, streaming, PRAM, and cut-query models, where no efficient deterministic global minimum cut algorithms are known.

A longest path in a graph is called a detour. Denote by $a(k,n)$ the minimum number of detours in a connected graph with minimum degree $k$ and order $n,$ and denote by $b(k,n)$ the minimum odd number of detours in such a graph. X. Zhan has posed the problem of determining $a(k,n)$ and $b(k,n).$ It is known that $a(2,n)=4$ for $n\ge 4$ and $b(2,n)=9$ for $n\ge 9.$ In this paper we prove that $a(3,n)=36$ for $n\ge 18,$ $a(k,n)\le (k!)^2$ for $n\ge k^2+2k+3$ and $b(3,n)\le 225$ for $n\ge 11.$ We also pose several related unsolved problems.

We introduce two quantitative measures of the strength of causal relations in quantum theory and more general physical theories. These two measures, called the maximum and minimum causal effect, quantify the maximum and minimum changes in the output of a quantum process induced by changes in its input. The maximum and minimum causal effects possess useful properties, such as continuity and data-processing inequality. In quantum theory, they have close connections with quantum information tasks. The maximum quantum causal effect can be used to detect quantum channels with nonzero capacity for transmitting classical information. The minimum causal effect can be used to guarantee the recoverability of quantum information: every quantum process with a high value of the minimum quantum causal effect can be approximately inverted. Moreover, we show that the quantum causal effects satisfy a duality relation: if the minimum causal effect of a quantum system $A$ on another quantum system $B$ is high, then $A$ must have a low value of the maximum causal effect on any other quantum system $B'$ that is spacelike separated with $B$. This duality implies a monogamy relation for quantum causal ef

Online planning and execution of minimum-time maneuvers on three-dimensional (3D) circuits is an open challenge in autonomous vehicle racing. In this paper, we present an artificial race driver (ARD) to learn the vehicle dynamics, plan and execute minimum-time maneuvers on a 3D track. ARD integrates a novel kineto-dynamical (KD) vehicle model for trajectory planning with economic nonlinear model predictive control (E-NMPC). We use a high-fidelity vehicle simulator (VS) to compare the closed-loop ARD results with a minimum-lap-time optimal control problem (MLT-VS), solved offline with the same VS. Our ARD sets lap times close to the MLT-VS, and the new KD model outperforms a literature benchmark. Finally, we study the vehicle trajectories, to assess the re-planning capabilities of ARD under execution errors. A video with the main results is available as supplementary material.

In serial batch (s-batch) scheduling, jobs are grouped in batches and processed sequentially within their batch. This paper considers multiple parallel machines, nonidentical job weights and release times, and sequence-dependent setup times between batches of different families. Although s-batch has been widely studied in the literature, very few papers have taken into account a minimum batch size, typical in practical settings such as semiconductor manufacturing and the metal industry. The problem with this minimum batch size requirement has been mostly tackled with dynamic programming and meta-heuristics, and no article has ever used constraint programming (CP) to do so. This paper fills this gap by proposing, three CP models for s-batching with minimum batch size: (i) an \textit{Interval Assignment} model that computes and bounds the size of the batches using the presence literals of interval variables of the jobs. (ii) A \textit{Global} model that exclusively uses global constraints that track the size of the batches over time. (iii) And a \textit{Hybrid} model that combines the benefits of the extra global constraints with the efficiency of the sum-of-presences constraints to

The minimum-norm interpolator (MNI) framework has recently attracted considerable attention as a tool for understanding generalization in overparameterized models, such as neural networks. In this work, we study the MNI under a $2$-uniform convexity assumption, which is weaker than requiring the norm to be induced by an inner product, and it typically does not admit a closed-form solution. At a high level, we show that this condition yields an upper bound on the MNI bias in both linear and nonlinear models. We further show that this bound is sharp for overparameterized linear regression when the unit ball of the norm is in isotropic (or John's) position, and the covariates are isotropic, symmetric, i.i.d. sub-Gaussian, such as vectors with i.i.d. Bernoulli entries. Finally, under the same assumption on the covariates, we prove sharp generalization bounds for the $\ell_p$-MNI when $p \in \bigl(1 + C/\log d, 2\bigr]$. To the best of our knowledge, this is the first work to establish sharp bounds for non-Gaussian covariates in linear models when the norm is not induced by an inner product. This work is deeply inspired by classical works on $K$-convexity, and more modern work on the ge

In this paper we introduce a new parameter for a graph called the {\it minimum universal rank}. This parameter is similar to the minimum rank of a graph. For a graph $G$ the minimum universal rank of $G$ is the minimum rank over all matrices of the form \[ U(α, β, γ, δ) = αA + βI + γJ + δD \] where $A$ is the adjacency matrix of $G$, $J$ is the all ones matrix and $D$ is the matrix with the degrees of the vertices in the main diagonal, and $α eq 0, β, γ, δ$ are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of $A$. The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. Finally we characterize all graphs with minimum universal rank equal to 0 and to 1.

This paper analyzes whether a minimum wage should be used for redistribution on top of taxes and transfers. I characterize optimal redistribution for a government with three policy instruments -- labor income taxes and transfers, corporate income taxes, and a minimum wage -- using an empirically grounded model of the labor market with positive firm profits. A minimum wage can increase social welfare when it increases the average post-tax wages of low-skill labor market participants and when corporate profit incidence is large. When chosen together with taxes, the minimum wage can help the government redistribute efficiently to low-skill workers by preventing firms from capturing low-wage income subsidies such as the EITC and from enjoying high profits that cannot be redistributed via corporate taxes due to capital mobility in unaffected industries. Event studies show that the average US state-level minimum wage reform over the last two decades increased average post-tax wages of low-skilled labor market participants and reduced corporate profits in affected industries, namely low-skill labor-intensive services. A sufficient statistics analysis implies that US minimum wages typicall

A graph is chordal if it does not contain an induced cycle of length greater than three. We determine the minimum size of a chordal graph with given order and minimum degree. In doing so, we have discovered interesting properties of chordal graphs.

Minimum cost homomorphism problems can be viewed as a generalization of list homomorphism problems. They also extend two well-known graph colouring problems: the minimum colour sum problem and the optimum cost chromatic partition problem. In both of these problems, the cost function meets an additional constraint: the cost of using a specific colour is the same for every vertex of the input graph. We study minimum cost homomorphism problems with cost functions constrained to have this property. Clearly, when the standard minimum cost homomorphism problem is polynomial, then the problem with constrained costs is also polynomial. We expect that the same may hold for the cases when the standard minimum cost homomorphism problem is NP-complete. We prove that this is the case for trees $H$: we obtain a dichotomy of minimum constrained cost homomorphism problems which coincides with the dichotomy of standard minimum cost homomorphism problems. For general graphs $H$, we prove a partial dichotomy: the problem is polynomial if $H$ is a proper interval graph and NP-complete when $H$ is not chordal bipartite.

In the minimum sum edge coloring problem, we aim to assign natural numbers to edges of a graph, so that adjacent edges receive different numbers, and the sum of the numbers assigned to the edges is minimum. The {\em chromatic edge strength} of a graph is the minimum number of colors required in a minimum sum edge coloring of this graph. We study the case of multicycles, defined as cycles with parallel edges, and give a closed-form expression for the chromatic edge strength of a multicycle, thereby extending a theorem due to Berge. It is shown that the minimum sum can be achieved with a number of colors equal to the chromatic index. We also propose simple algorithms for finding a minimum sum edge coloring of a multicycle. Finally, these results are generalized to a large family of minimum cost coloring problems.

We give an alternative proof of the formula for the minimum distance of a projective Reed-Muller code of an arbitrary order. It leads to a complete characterization of the minimum weight codewords of a projective Reed-Muller code. This is then used to determine the number of minimum weight codewords of a projective Reed-Muller code. Various formulas for the dimension of a projective Reed-Muller code, and their equivalences are also discussed.

The current cycle minimum appears to be deeper and broader than recent cycle minima, and this minimum appears similar to the minima in the early 1900s. With the best-ever solar irradiance measurements from several different satellite instruments, this minimum offers a unique opportunity to advance our understanding of secular (long-term) changes in the solar irradiance. Comparisons of the 2007-2009 irradiance results to the irradiance levels during the previous minimum in 1996 suggest that the solar irradiance is lower in this current minimum. For example, the total solar irradiance (TSI) indicates lower irradiance in 2008 than in 1996 by about 200 ppm, and the SOHO Solar EUV Monitor (SEM) 26 to 34 nm irradiance is about 15% lower in 2008 than in 1996. However, these irradiance variations have 30-50% uncertainties due to these results depending strongly on instrument degradation trends over 12 years. Supporting evidence for lower irradiance include that the solar magnetic fields are lower and that there are more low-latitude coronal holes during this current minimum.

Robust inference based on the minimization of statistical divergences has proved to be a useful alternative to classical techniques based on maximum likelihood and related methods. Basu et al. (1998) introduced the density power divergence (DPD) family as a measure of discrepancy between two probability density functions and used this family for robust estimation of the parameter for independent and identically distributed data. Ghosh et al. (2017) proposed a more general class of divergence measures, namely the S-divergence family and discussed its usefulness in robust parametric estimation through several asymptotic properties and some numerical illustrations. In this paper, we develop the results concerning the asymptotic breakdown point for the minimum S-divergence estimators (in particular the minimum DPD estimator) under general model setups. The primary result of this paper provides lower bounds to the asymptotic breakdown point of these estimators which are independent of the dimension of the data, in turn corroborating their usefulness in robust inference under high dimensional data.

We show that every $α$-approximate minimum cut in a connected graph is the unique minimum $(S,T)$-terminal cut for some subsets $S$ and $T$ of vertices each of size at most $\lfloor2α\rfloor+1$. This leads to an alternative proof that the number of $α$-approximate minimum cuts in a $n$-vertex connected graph is $n^{O(α)}$ and they can all be enumerated in deterministic polynomial time for constant $α$.

Aims: Although the time of the Maunder minimum (1645--1715) is widely known as a period of extremely low solar activity, claims are still debated that solar activity during that period might still have been moderate, even higher than the current solar cycle #24. We have revisited all the existing pieces of evidence and datasets, both direct and indirect, to assess the level of solar activity during the Maunder minimum. Methods: We discuss the East Asian naked-eye sunspot observations, the telescopic solar observations, the fraction of sunspot active days, the latitudinal extent of sunspot positions, auroral sightings at high latitudes, cosmogenic radionuclide data as well as solar eclipse observations for that period. We also consider peculiar features of the Sun (very strong hemispheric asymmetry of sunspot location, unusual differential rotation and the lack of the K-corona) that imply a special mode of solar activity during the Maunder minimum. Results: The level of solar activity during the Maunder minimum is reassessed on the basis of all available data sets. Conclusions: We conclude that solar activity was indeed at an exceptionally low level during the Maunder minimum. Altho

The minimum rank of a graph G is the minimum rank over all real symmetric matrices whose off-diagonal sparsity pattern is the same as that of the adjacency matrix of G. In this note we present the first exact algorithm for the minimum rank of an arbitrary graph G. In particular, we use the notion of determinantal rank to transform the minimum rank problem into a system of polynomial equations that can be solved by computational tools from algebraic geometry and commutative algebra. We provide computational results, explore possibilities for improvement, and discuss how the algorithm can be extended to other problems such as finding the minimum positive semidefinite rank of a graph.

We study minimum integer representations of weighted games, i.e., representations where the weights are integers and every other integer representation is at least as large in each component. Those minimum integer representations, if the exist at all, are linked with some solution concepts in game theory. Closing existing gaps in the literature, we prove that each weighted game with two types of voters admits a (unique) minimum integer representation, and give new examples for more than two types of voters without a minimum integer representation. We characterize the possible weights in minimum integer representations and give examples for $t\ge 4$ types of voters without a minimum integer representation preserving types, i.e., where we additionally require that the weights are equal within equivalence classes of voters.

A Hausdorff topological group topology on a group $G$ is the minimum (Hausdorff) group topology if it is contained in every Hausdorff group topology on $G$. For every compact metrizable space $X$ containing an open $n$-cell, $n\ge2$, the homeomorphism group $H(X)$ has no minimum Hausdorff group topology. The homeomorphism groups of the Cantor set and the Hilbert cube have no minimum group topology. For every compact metrizable space $X$ containing a dense open one-manifold, $H(X)$ has the minimum group topology. Some, but not all, oligomorphic groups have the minimum group topology.