New answers tagged

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 $...
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 ...
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 \\ ...

Top 50 recent answers are included