## New answers tagged algorithms

2

You have an interesting kind of partitioning problem here. (Maybe that's why you are using lattices.)
One thing that should be noted. If d is a join b for some given a and b which are incomparable, then d is NOT a meet c for any c in the lattice. So when you focus on the first coordinate a, you immediately divide X minus a into three sets: those above a, ...

0

Assuming you can easily compute the infimum and supremum of the density function $f$ on a given square with axis-aligned sides, you can use a quadtree to perform an approximate sampling. Let's assume that $f$ is bounded.
Work in 2D Cartesian coordinates and write $S_{l, b, \delta}$ for the axis-aligned square containing all points $(x,y)$ with $l \leq x < ...

3

I'm not sure if this is exactly what you're looking for, but my go-to volume for these kinds of question is Symbolic Integration I by Manuel Bronstein. Risch's original treatment is sketchy in many places, and Bronstein did a lot of work to flesh out the details and actually implement Risch's methods. From the Foreword by B. F. Caviness:
With the advent ...

1

J. H. Davenport, On the integration of algebraic functions. Lecture Notes in Computer Science, 102. Springer-Verlag, Berlin-New York, 1981.
J. H. Davenport, Integration in closed form. Computers in mathematical research (Cardiff, 1986), 119–134, Inst. Math. Appl. Conf. Ser. New Ser., 14, Oxford Sci. Publ., Oxford Univ. Press, New York, 1988.

answered Jun 24 at 12:54

Alexandre Eremenko

63.1k66 gold badges174174 silver badges297297 bronze badges

1

Let
$$M = \begin{pmatrix} | & | & \cdots & | \\ v_1 & v_2 & \cdots & v_d \\ | & | & \cdots & | \end{pmatrix}$$
and let $e_1, \ldots, e_N$ be the standard unit vectors. Then consider the linear programs indexed by $i = 1, \ldots, N$:
$$\begin{aligned}
&\text{maximize }\langle e_i,Mx\rangle \\
&\text{subject to }\...

0

Yup, NP-hard.
Consider the case where edges only have two weights. Then we have a hypergraph of light edges, and the problem is to pick a matching using as many light edges as possible. This is NP-hard, and in fact I believe it was one of Karp’s original 21 NP-complete problems.
https://en.m.wikipedia.org/wiki/3-dimensional_matching
That said, you might ...

Top 50 recent answers are included

#### Related Tags

algorithms × 1203graph-theory × 249

co.combinatorics × 232

computational-complexity × 174

nt.number-theory × 154

linear-algebra × 101

computer-science × 79

reference-request × 64

gr.group-theory × 64

mg.metric-geometry × 60

computational-geometry × 54

pr.probability × 52

ag.algebraic-geometry × 46

na.numerical-analysis × 42

computational-number-theory × 40

polynomials × 39

approximation-algorithms × 39

discrete-geometry × 37

matrices × 35

linear-programming × 31

combinatorial-optimization × 31

oc.optimization-and-control × 30

ac.commutative-algebra × 29

prime-numbers × 28

permutations × 25