# Tag Info

## Hot answers tagged approximation-algorithms

13

@user61318 and @JosephORourke, thanks for the advertisement for my book. @chubakueono, as far as I know the answer to your questions are no and no. Pages 148-149 in my book have the state of the art (essentially the formula you wrote, along with some additional background) and the relevant references. However, in a broader sense much more is understood ...

11

Not in general. An explicit and elementary counterexample is the sparse triangular matrix with $1$'s on the diagonal and $-1$'s just above it: the inverse is the triangular matrix with every entry on or above the diagonal equal $1$.

9

The determinant of matrices whose support corresponds to incidence matrices of planar graphs (this includes the Laplacian matrix of a planar graph, or more precisely its cofactors) can be calculated in $O(n^{1.5})$ with the algorithm given in R.J. Lipton, D. Rose, R.E. Tarjan Generalized nested dissection SIAM J. Numer. Anal., 16 (1979), pp. 346-358 ...

8

Before you can formulate your question precisely, you need a better notion of distance between two pictures of a set $S \subset \mathbb{C}$ (where in this case, $S$ is the union of Ford circles). If $\iota_1, \iota_2$ are pictures (bijections from square subsets $A_1, A_2$ of $\mathbb{C}$ to the unit square), then we can define distance as the Hausdorff ...

7

Define the parent of a Ford circle to be the smaller of its two larger neighbors; then this parent relation defines the Stern–Brocot tree on the points of tangency of the circles. The path in this tree to a given real number is closely related to its continued fraction expansion. A path in the tree can be represented combinatorially by a binary sequence that ...

6

This will answer your questions on $\delta$: The case $\delta=1$, sometimes referred to as the ideal or optimal LLL-Algorithm, is the most natural way to define the swap condition between vectors after the length reduction step, as it forces to swap $b_k$ and $b_{k+1}$ if and only if its orthogonal 'emergence', i.e. orthogonal distance of $b_{k+1}$ with ...

6

Below the line I address the question after "Update" about the relationship between volume and the number of lattice points. Since OP asks about conditions under which we can count the number of lattice points in $K$, let me point to a recent chapter by Barvinok, which has a lot of relevant information. Here are three special cases in which a positive result ...

5

This question is closely related to the so-called "condition number" of the B-spline basis. Basically, for a spline $f$ of some degree $p$ with a coefficient vector $c=(c_i)$, you generally have for any $q \in [1,\infty]$ that $$A_{p,q} \|c\|_{\ell_q} \le \| f \|_{L_q} \le B_{p,q} \|c\|_{\ell_q},$$ and the smallest possible ratio $\kappa_{p,q} = B_{p,... 5 Polynomials with a multiple root form a Zariski closed set (vanishing of the discriminant, which is a certain polynomial in the coefficients); hence, this set is nowhere dense, whereas its complement is dense. In other words, in any neighborhood of any point, "most" polynomials are nonsingular, and it's very unlikely one can detect the singularity unless the ... 4$\newcommand{\Ag}{\mathcal{A}_\gamma}$Not a full answer, put probably a fruitful pointer: In the discretization of infinite dimensional problems one faces (bi-)infinite matrices. There, the Jaffard algebra$\Ag$of bi-infinte matrices (for some$\gamma>1$) is $$\Ag = \{A \ : \ |a_{k,l}|\lesssim (1+ |k-l|)^\gamma\}.$$ It can be shown that the Jaffard ... 4 That's the Metric$k$-center problem. 4 The question is stated informally, using the terms "queries" and "access". Here is how I formally interpret it: Take any$s$and$t$in$(0,1)$. Let$G_{s,t}$be the set of all continuous strictly increasing functions$g\colon[0,1]\to[0,1]$such that the set $$E:=E_{s,t}(g):=\{x\in[0,1-s]\colon g(x+s)-g(x)<t\}$$ is nonempty. Do there ... 3 If the number and position of the knots are fixed, then the problem is a linear least squares problem for determining the coefficients of linear B-Splines (cf e.g http://en.wikipedia.org/wiki/B-spline); if the knot-positions also have to be determined, then the problem becomes non-linear, but is also studied in approximation theory. This article seems to ... 3 The FFT is an important part of the fast multipole method, which is probably what you would want to use. 3 It depends on the model of computation you're using. If your memory slots can contain arbitrarily large integers (rather than single bits), and you can perform arithmetic operations in constant time, the answer is yes. Basically you use the following algorithm to step through the Farey sequence of the correct order: https://en.wikipedia.org/wiki/... 3 Do you care more about the curve or the surfaces? Replacing the first function in your example by$100(x^2 + y^2 - 16)$or$x^2-z^2+9$gives the same curve but a different error function. Also, consider the intersection of the cylinder$(x-11)^2+(y-11)^2=221$and the plane$x+y-z=1.$It is an ellipse and the portion$\mathit{C}$in the positive octant goes ... 3 There is an easy$2$-approximation algorithm for finding a minimum size maximal matching. Simply find any maximal matching. Note that a maximal matching$M$can be found greedily. Initialize$M=\emptyset$. Add any edge$xy$to$M$, and in$G -x-y$search for another edge to add and recurse. Let$m$be the size of a minimum maximal matching. To show ... 3 You have to find a way to reduce the size of your simplicial complex. Some algorithms based e.g. on discrete Morse theory can do that fairly rapidly, but they don't have guarantees on the amount of size reduction. I don't think there exists faster algorithms for approximate Betti numbers in general, but I believe it can be done if your simplicial complex is "... 3 There is a way to speed-up Bourgain's embedding in case if the original metric space has low "intrinsic dimension". The resulting algorithm will have a theoretical runtime$O(CN\log^2(N))$, where$C$is a constant depending only on "intrinsic dimension". And also will show speedups over the standard Bourgain's embedding varying between one and several orders ... 3 You can solve this problem via integer linear programming. Let binary decision variable$x_i$indicate whether you can open door$i$, and let binary decision variable$y_j$indicate whether you select key$j$. The problem is to maximize$\sum_{i=1}^N x_isubject to \begin{align} \sum_{j=1}^M y_j &= k \\ x_i &\le y_j &&\text{if doori$... 2 I have recently computed a large table of rigorous values of the Stieltjes constants. Thanks to some coding by Jon Bober, the table can be browsed using a web interface on LMFDB.org (the L-functions and modular forms database): http://beta.lmfdb.org/riemann/stieltjes/ For any$n \le 10^5$, the web interface allows printing$\gamma_n$to at least 10000 ... 2 Your reference to eigenvalues suggests that you are minimizing$\sum_i P(x_i, y_i)^2$subject to a constraint like$\sum_{a,b} P_{ab}^2=1$, where$P(x,y) = \sum_{a,b} P_{ab} x^a y^b$. Why not instead minimize$\sum_i P(x_i, y_i)^2$subject to a linear constraint like$P_{00}=1$? This is a standard approach when fitting a conic through a cloud of points (... 2 Since you're using sage, I'd write a quick C or Cython function. Use the Arb library (I think this is already included in the latest release of sage) by computing the function in the naive way using the gamma function. The benefit to doing so, is that the library uses "Ball" arithmetic and automatically finds rigorous error bounds for the computation. ... 2 Here is an idea that may work. Assume we are interested in minimizing the expected value \begin{equation*} f(T) := E_z[F(T,z)], \end{equation*} where$F'(T,z) = x(z)e^{x(z)/T}-C$. If the$z$'s are sampled independently, then$E_z[F'(T,z)]=f'(T)$, and you can run the Robbins-Monro iteration (stochastic gradient) to update \begin{equation*} T_{k+1} = ... 2 The principles behind embedded Runge-Kutta-Methods apply: You compute the integral over a subinterval with two methods of different order. You use the difference between the two results as an estimate for the local quadrature error of the less accurate formula. In order to meet a global tolerance, you sum up these local errors. If the sum is above the ... 2 This is an extended comment. What exactly you are trying to minimize? First version: given an algebraic curve with equation$F(x,y)=0$, and two points on this curve$M,N$, find the polynomials$p,q$of degree at most$d$such that$(p(0),q(0))=M$,$(p(1),q(1))=N$, and $$\max_{t\in[0,1]}|F(p(t),q(t))|$$ is minimal. Some condition about two points is ... 2 Expanding on my comment ... There's some material on bivariate approximation in Carl deBoor's book entitled "A Practical Guide to Splines". Specifically, chapter XVII has results on approximation by tensor products and code to implement this. The code is also available in the matlab spline package. 2 You might find the idea of Companion matrix to be useful. The eigenvalues$\lambda$of the companion matrix$C$are equal to the roots of a polynomial and its eigenvectors$v$are functions of the eigen-values and$v$are linearly independent iff the eigenvalues(ie, roots) are distinct. Now the question becomes that if only have noisy estimates of the ... 2 Since each row$r$has a finite number of non-zero elements, say$N_r \subset \{1, 2, \dots\}$, you could use the Gillespie algorithm to simulate the continuous time Markov chain. A stationary distribution can then be approximated by the normalized occupancy times. If the matrix is irreducible, this will be the stationary distribution. Here is an outline of ... 2 Yes, we do have "approximate complementary slackness" in the following sense. Consider the standard (primal) linear programming problem: max$c^T x$s.t.$A x \le b$,$x \ge 0$If$x^*$and$y^*$are primal and dual feasible solutions, we have $$c^T x^* \le y^* A x^* \le y^* b$$ with equality iff$x^*$and$y^*$are optimal. Now let's say$x^*\$ is ...

Only top voted, non community-wiki answers of a minimum length are eligible