Skip to main content

Questions tagged [mathematical-programming]

Using a computer to implement mathematics. For questions about (mathematical) optimization, (also) use the optimization tag.

Filter by
Sorted by
Tagged with
2 votes
1 answer
72 views

Proof of NP-hardness: Is the problem of finding the minimum edge-weighted subgraph with at least M pairwise connectivity NP-hard?

Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and a positive integer $M$, the problem asks to determine the minimum-weight set of edges $S\subseteq ...
HonestSJ's user avatar
-1 votes
0 answers
43 views

How to formulate Leetcode 1296 problem as optimization problem

I am reviewing how to design greedy algorithms and specifically I have the following problem that it is suggested to be solved using a greedy approach: Given an array of integers nums and a positive ...
user8469759's user avatar
0 votes
1 answer
49 views

How do computer scientists finds a minimum of a tuple?

In multiobjective optimization, what does it mean to minimize a function of the form $F(a)=(O_1,-O_2,...,O_n)$? I mean, in mathematics, we can order every set by Zorn's lemma but I think we need some ...
guest's user avatar
  • 11
-2 votes
1 answer
49 views

The Hydra Game runs forever

I saw this question here: The Hydra Game algorithm I am also running into troubles with the same problem. I also learned of the problem in this Numberphile video, and also tried to compute it myself. ...
Lee's user avatar
  • 1
1 vote
4 answers
207 views

The Hydra Game algorithm

I was recently introduced to the Hydra Game by the youtube channel Numberphile (https://www.youtube.com/watch?v=prURA1i8Qj4). In this video, they discuss many variants of the Hydra Game - cut off one ...
SomeCallMeTim's user avatar
2 votes
1 answer
358 views

Potential of Artificial Intelligence to improve algorithm for PI

Recently AI (alphazero) was used to improve practical matrix multiplications by around 10 to 20 percent. Alphageometry and ramanujan machines all came into existence in the recent years as well. Seems ...
siminsimin's user avatar
0 votes
0 answers
23 views

Decreasing quantity elements in quantities array to get it to be in same ratio as array of ratios

Problem Statement: We want to update(only decrease allowed) elements of array to obtain a new array which is in same ratio as ratio array. Example lets say you have quantity vector as [20, 50, 20] and ...
decentstudent's user avatar
2 votes
1 answer
69 views

Efficient algorithm for finding a vector to maximize the number of positive dot products with a given set (finding the maximum overlap of half-spaces)

I have a large set $\mathbf{V}$ of vectors in $\mathbb{R}^d\setminus\{\mathbf{0}\}$ and need to find a vector $\mathbf{u}$ that maximizes $\sum_{\mathbf{v}\in\mathbf{V}}\mathbf{1}_{\mathbf{u}\cdot\...
multiplywithadot's user avatar
0 votes
0 answers
24 views

better ways to integer interpolation?

I made some code about "integer interpolation" for running approximate alpha blending at FPGA which have low quantities of logic gate. Let's refer to "II" as integer interpolation. ...
박성재's user avatar
0 votes
3 answers
51 views

Which algorithms could be suitable for solving my disjunctive programming problem?

Following a previous post on the cs stack exchange (link to question), I have been searching to no avail for an implementation of a disjunctive programming solver in C# (or wrapped in C#). In this ...
Ed_Silver's user avatar
0 votes
0 answers
48 views

Bundle diameter calculation algorithm with different wire sizes accounting for twisted pairs?

Based on the same question asked here: Bundle diameter calculation algorithm with different wire sizes? Best answer was this: https://scipython.com/blog/packing-circles-in-a-circle/ However, there are ...
Helpme Guest's user avatar
0 votes
0 answers
29 views

How to calculate transition areas of biomes in an image

I'm generating biomes for my game and I would like to store them in a single RGB image like the one below. A color hue can then be mapped to an ID through a table lookup. The problem I face is that I ...
nights's user avatar
  • 101
1 vote
1 answer
56 views

Approximate euclidean graph from distance matrix?

In a personal project of mine, I have been faced with the following problem. I have an $n \times n$ matrix $T$ where an entry $t_{ij} \geq 0$ denotes an arbitrary metric between two points $i$ and $j$ ...
mathyws's user avatar
  • 11
0 votes
0 answers
93 views

What is the fastest algorithm for division of crazy large integers?

I need to divide numbers represented as digits in byte arrays with non standard amount of bytes. It maybe 5 bytes or 1 GB or more. Division should be done with numbers represented as byte arrays, ...
Eljesa Mehmeti's user avatar
0 votes
1 answer
242 views

how to get the high 32-bit of the answer of two 32-bit integer multiple?

Recently, I study the instruction set of riscv32 and face a order as "mulh" which tends to multiply two 32-bits signed integers and store the high 32 value into the register. And here comes ...
Ecthelion's user avatar
2 votes
1 answer
114 views

Efficiently remove intersections among a set of spheres

I have a 3D space where N spheres of identical size, identified by the location of their centers, are continually inserted. When a new sphere is inserted, I have the ability to efficiently query the ...
anirudhc1229's user avatar
1 vote
3 answers
121 views

Find the largest possible number not larger than some integer N and is the product of K consecutive primes

Source: Hanoi student competition of unknown year (Kì thi học sinh giỏi thành phố) Additional conditions: N is a positive integer in range [1, 2^64 - 1] K is a positive integer in range [3, 10] ...
ducbadatchem's user avatar
0 votes
1 answer
182 views

Finding Sum(F(i)) where F(i) = min(⌈ Ai / B1 ⌉ * C1, ⌈ Ai / B2 ⌉ * C2, ⌈ Ai / B3 ⌉ * C3, .... ,⌈ Ai / Bm ⌉ * Cm)

Given three arrays A, B, and C of size n, m, and m respectively (1-based indexed). A function F(i) is defined as - F(i) = minimum_of(⌈ Ai / B1 ⌉ * C1 , ⌈ Ai / B2 ⌉ * C2 , ⌈ Ai / B3 ⌉ * C3 , .... , ⌈ ...
Nachiket Kanore's user avatar
1 vote
1 answer
1k views

If greater than or equal to zero then binary variable equals 1: integer linear program

I have a variable $d_{i} \in \mathbb{Z}$ with an upper and lower bound. I also have a binary variable $v_{i}$ which I want to $=1$ if $d_{i} \geq 0$; else $v_{i} = 0$. How do I enforce this as a ...
Alex Pharaon's user avatar
1 vote
1 answer
39 views

Beginning Algorithm Design and Proving

I know this is a general question, so you can address this by giving some examples that are specific to your field. I want to start learning algorithm design and consequently prove its convergence. ...
cgo's user avatar
  • 273
0 votes
0 answers
40 views

When do I use inversions in an array?

In problems like the 15 Tile Problem or Larry's Array problem, we use inversions in the array as a method to solve. But what's the principle behind this method and how do I know when to use inversions?...
Yuv's user avatar
  • 139
1 vote
1 answer
25 views

Number of operands to take when evaluating postfix notation?

All sources I have seen list taking two operands from the stack once we encounter an operator. Why? What if not all of my operators are binary (taking two arguments)? What if I have custom unary and ...
A.L. Verminburger's user avatar
2 votes
0 answers
25 views

Is computing subgradients an open research area in Authomatic Differentiation

Large portions of the possible research areas in Automatic Differentiation have broadly defined known solutions; most of which were derived in the 80s and 90s. Compute vector jacobian products: use ...
Frames Catherine White's user avatar
2 votes
0 answers
162 views

Algorithm to find largest intersection of sets

This is a cross-posting from here, on the mathematics Stack Exchange. I thought this might be a more appropriate venue. The problem is this: I have a list of sets $$S_1, S_2,... S_N$$ where each set ...
Dan Goldwater's user avatar
0 votes
1 answer
1k views

How does Wolfram Alpha solve functional equations?

Wolfram Alpha is able to solve a few basic functional equations. For example, it knows how to solve equations like this. My question is: how does it do this? I am planning on creating a program to ...
TheBestMagician's user avatar
1 vote
2 answers
359 views

Understanding Time Complexity

I am sorry if these are such stupid noob questions. I am just getting into CS. I read a passage in a book that says: Time complexity is written T(n). It gives the number of operations the algorithm ...
JamesG's user avatar
  • 111
1 vote
2 answers
350 views

What algorithm is prefered to do a x b mod P with big numbers (256 bits)

I'm trying to implement multiple precision arithmetic operations modulo P, with P < 2^256. More specifically, ...
Ervadac's user avatar
  • 113
4 votes
2 answers
221 views

Precise algorithm for finding higher order derivatives

I'm trying to make an algorithm that finds the first 10 or so terms of a function's Taylor series, which requires finding the nth derivative of the function for the nth term. It's easy to implement ...
Natrium's user avatar
  • 75
0 votes
0 answers
356 views

Count of different ways to express N as the sum of given numbers

I'm working on a case and I need some help :) I need to find number of ways and solutions itself to express N as the sum of given numbers. So, Sum (N) = 600 and the numbers from which I need to get ...
David Ambokadze's user avatar
-1 votes
1 answer
317 views

Proof of Correctness : Arranging the sheep

I've come across a question in Codeforces contest 719(Div - 3). The problem goes like this : I was able to solve the problem by using another approach but had to use 4*n auxiliary space, where n is ...
Tejesh Avadanam's user avatar
1 vote
0 answers
35 views

How to create algebraic structures in code

I've been searching around google and this site and I haven't been able to find the answer to this. How are algebraic structures (like a set and its elements, groups, rings, etc.) defined in code (in ...
Aaron's user avatar
  • 111
1 vote
1 answer
53 views

EM algorithm - What happens with the standard deviation?

What have you tried? So I watched this video. According to the video, we've to calculate the variance $\sigma^2$ as follows: $$ \sigma_{k}^{2} = \frac { p_{1} \left(x_{1} -...
TornaxO7's user avatar
  • 121
0 votes
1 answer
479 views

Four functions problem

This is not from online contest Hi guys, a friend of mine recently give me this problem that I couldn't figure out an effective way to solve it. Four functions You are given four functions $$ \begin{...
Loc Truong's user avatar
0 votes
1 answer
175 views

How to get the calculate the binary logarithm of a fixed-point number with 18 decimals?

Suppose that: You're using a programming language that doesn't support fixed-point or floating-point numbers. The said programming language rounds down divisions, e.g. ...
Paul Razvan Berg's user avatar
1 vote
1 answer
298 views

Number of substrings with exactly k distinct characters

Given a string s and an int k, return an int representing the number of substrings (not unique) of s with exactly k distinct characters. If the given string doesn't have k distinct characters, return ...
Hikari's user avatar
  • 13
1 vote
1 answer
15 views

Is this adjustment to an rms calculation valid?

I want to calculate the RMS AC value of a signal made up of several thousand readings every second. The processor that I am using doesn't have enough memory to store a whole second of data, so I want ...
JavaLatte's user avatar
  • 211
0 votes
0 answers
109 views

Competitive programming: Good Subsets problem

An array of length K is called good if for each subarray of the array, the sum of the subarray is not divisible by K+1. You are given an array A of length N. Find the number of subsequences of length ...
Anurag chaudhary's user avatar
-1 votes
1 answer
34 views

Random numbers with condition in matlab

I need ’n’ random numbers that: each one is bigger than ‘a’ their sum is smaller than ‘b’ How can I have that in Matlab?
Navide's user avatar
  • 59
0 votes
1 answer
444 views

Adapt a one-tape turing machine's algorithm that find the center of a string in O(nlog(n)) to find the first third

I have found this answer that finds the center of an input string in nlog(n) complexity. I have tried to use it as a starting point to find an algorithm that finds the character(s) that separate the ...
Patrick_S's user avatar
-1 votes
3 answers
54 views

Which topics of mathematics should I need to learn to be a good app developer?

I'm 29 years old. I couldn't continue my studies after grade 10 due to some financial issues and I didn't have time to practice mathematics. It's been more than 11 years since I left studies. Now I ...
Ansar Ali Akash's user avatar
0 votes
0 answers
42 views

Optimal partitioning of n-arrays

You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays. The goal is to partition those arrays into K ...
giulioandreolli's user avatar
0 votes
1 answer
42 views

Is there a way to map a multi-variable structure onto a single range?

I want to categorise variants of a structure made up of some number of variable components by mapping it to a unique range. Assume that the individual components all fall within the same base range. I'...
OPKD's user avatar
  • 3
0 votes
1 answer
141 views

Is there a way to combine linear equation and inequalities into same equation in order to optimise software calculations?

I’m programming web application which has some tricky calculations and I would need some help with mathematical calculations. What I'm trying to calculate: I have number of items. Lets call items a1, ...
Mikko Korhonen's user avatar
0 votes
0 answers
24 views

How to cluster a dataset in which each data point is composed of a set of 2-dimensional coordinates

I have a dataset with totally $1000$ scenarios, each of which is composed of $5$ users' coordinates $(x_i,y_i), \forall i \in \{1,\dots,5\}$. Now, based on users' coordinates, I want to cluster these $...
Good to learn everything's user avatar
1 vote
1 answer
1k views

What is the difference between a fraction and a float?

I understand any fraction to be a quotient of integers which isn't 0, but after coming across the term "float" in various programming languages (such as JavaScript) I misunderstand why it is ...
guest's user avatar
  • 1
-1 votes
3 answers
2k views

Divide first n square numbers 1^2, 2^2, ....... n^2 into two groups such that absolute difference of the sum of the two groups is minimum [closed]

lets say Given input is n = 6 (n is as large as 100000) My task is to divide {1, 4, 9, 16, 25, 36} into two groups and PRINT these two groups Possible Solution 1: dividing groups as {1, 9, 36} and {4, ...
starboy's user avatar
5 votes
3 answers
762 views

Usefulness of Differential Geometry

I recently came across these books: Differential Geometry and Lie Groups: A Computational Perspective Differential Geometry and Lie Groups: A Second Course Their subject matter really intrigues me, ...
user37344's user avatar
  • 125
0 votes
1 answer
27 views

Convert ((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4) to MathJax? [closed]

I need help coverting these two question to Math Jax ((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4) and (((50^A)(50^B)(50^C))/(4^2)) + (((50^A)(50^B))/(4^2))+((50^A)/(4))+(1/4) I don't know how to ...
djdogs422's user avatar
0 votes
0 answers
44 views

Stable matching with dynamic preference lists

I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
Farah Mind's user avatar
1 vote
0 answers
45 views

Accessible CS Math Job [closed]

I am a CS undergrad and a huge enthusiast of pure math. I have been doing competitive programming and proofs for a while. My ambition is to become an academic in theoretical computer science. The ...
Mostafa Touny's user avatar