## New answers tagged algorithms

2
votes

Accepted

### Edge-length constraints from greedy matching

Let the weights of the edges in a 6-cycle in $K_6$ be $1,2,5,6,5,2$ (in cyclic order), and let other weights be large. Then the optimal matching will be $2,2,6$, while the greedy one will consist of $...

- 19.8k

1
vote

Accepted

### How to find the maximum of a sum of squares of sums?

You can solve the problem via binary quadratic programming as follows. Let binary decision variable $x_{id}$ indicate whether row $i$ is rotated $d$ places. The problem is to maximize
$$\sum_{j=0}^{...

- 4,073

3
votes

Accepted

### Do all graphs with $n$ vertices and $m$ edges have a special property?

For $n=53$ and $m=113$, you can't even get close in general. Take 7 copies of $K_5$ and 3 copies of $K_6$, all disjoint. Remove any two edges; now you have 53 vertices and 113 edges. No complete ...

- 34.8k

1
vote

### Do all graphs with $n$ vertices and $m$ edges have a special property?

Let $\psi(n)\approx\sqrt{n}$ denote the positive solution to $x^2+2x=n$. Note that if $|V_1||V_2|+|V_1|+|V_2|>n$, then either $|V_1|\geq \psi(n)$ or $|V_2|\geq \psi(n)$. This implies that all ...

- 11

2
votes

Accepted

### Method to solve system of exponential sums of the form $a^x+b^x=c$ given more equations than variables

We can use linear algebra to make this easier.
Consider the space of sequences of the form $A a^n + B b^n$. We can use several dual bases for this space. One is the obvious basis of maps that send $A ...

- 4,706

1
vote

Accepted

### Algorithm for finding a minimum weight circuit in a weighted binary matroid

The problem is NP-hard (even in the unweighted case) via a well-known connection to coding theory. Namely, if $A$ is the parity check matrix of a binary linear code $C$, then the distance of $C$ is ...

- 29.2k

3
votes

Accepted

### Number of biquadrates mod n

As stated in the comments (1 2 3), the counting function is multiplicative, so only the prime power case needs to be addressed. Last year, I derived a somewhat concise formula for $\lvert R_k (p^m)\...

- 1,823

4
votes

### Method to solve system of exponential sums of the form $a^x+b^x=c$ given more equations than variables

I'm not sure about your method, but such equations can easily be turned into polynomial equations by introducing $u:=a^{x-1}$ and $v:=b^{x-1}$:
\begin{cases}
u+v=337 \\
au+bv=1267 \\
a^2u+b^2v=4825 \\
...

- 27.5k

Top 50 recent answers are included

#### Related Tags

algorithms × 1464graph-theory × 321

co.combinatorics × 303

computational-complexity × 218

nt.number-theory × 194

linear-algebra × 118

computer-science × 82

reference-request × 77

gr.group-theory × 72

mg.metric-geometry × 71

pr.probability × 66

computational-geometry × 61

combinatorial-optimization × 56

computational-number-theory × 54

polynomials × 53

approximation-algorithms × 53

ag.algebraic-geometry × 52

na.numerical-analysis × 48

matrices × 45

discrete-geometry × 43

oc.optimization-and-control × 41

ac.commutative-algebra × 37

prime-numbers × 37

linear-programming × 35

graph-colorings × 29