Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

learn more… | top users | synonyms

1
vote
1answer
18 views

Combinatorial optimization - is there a formal name for this problem?

I am looking for a formal name and an algorithmic approach to the following problem. Given is a set of services each coming with a price: {s1, 300} {s2, 400} {s3, 800} Additionally there is a ...
2
votes
1answer
31 views

Find the subset of k element between n that maximize the total distance

Given a set $Q\subset \mathbb{N}^m $ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm. ...
-2
votes
0answers
8 views

ASP.Net MVC JavaScript error [on hold]

I attached the pictures regarding mistakes, View and Controller. When I select the country in the field of ‘Country’, JavaScript code which is supposed to bring the city names does not work (p.s. ...
-2
votes
0answers
14 views

Help. Excel Macro to group data [on hold]

I have the following data, which I would like to break down into 3 groups. Essentially, I have a list of data elements (IDEs), which are referred to by a code (ixxxxx) that are used in certain ...
-3
votes
0answers
26 views

How can I express lengths of idle periods in LP constraints?

My final project is about permutation flow shop scheduling problem with buffer limits and energy considerations. Parameters n: Number of jobs m: Number of machines i: Machine index, (i=1,..,m) ...
-1
votes
0answers
27 views

Optimality conditions of an Artificial intelligence method [on hold]

In classical optimization methods, Karush-Kuhn-Tucker (KKT) conditions are considered as the optimality conditions to check whether the obtained solution is local optima or global optima. Is there any ...
7
votes
3answers
74 views

Algorithms for minimizing Moore automata

Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ...
1
vote
1answer
20 views

How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
0
votes
0answers
23 views

How can I determine whether a problem is NP-Hard [duplicate]

So I have a problem, I'm highly confident that it's NP-Hard, though I'm not really sure how I can convince my self this is the case? Suppose I have different groups of people m in a list M= {m1, m2} ...
-2
votes
0answers
124 views

Find out maximum number of K’s possible for given number of keystrokes [closed]

Imagine you have four operations. ‘K’ (types k on screen), ‘select all’, ‘copy’, ‘paste’. Find out maximum number of K’s possible for given number of keystrokes. e.g ...
3
votes
1answer
29 views

Algorithm(s) for creating balanced 5-a-side teams?

I play 5-a-side soccer twice a week. 10 people play each game out of a pool of about 30 people who are giving the opportunity to play as it's first come first serve. Some people play more often than ...
6
votes
1answer
51 views

Is weighted XOR-SAT NP-hard?

Given $n$ boolean variables $x_1,\ldots,x_n$ each of which is assigned a positive cost $c_1,\ldots,c_n\in\mathbb{Z}_{>0}$ and a boolean function $f$ on these variables given in the form ...
2
votes
1answer
24 views

Selecting k “special” nodes in a graph such that the min distance is maximized?

Lets say we have a graph $G$ with $|V|$ nodes. We wish to select $k$ such nodes while optimizing the following attribute: maximize: for each $i$ and $j$, where $i \neq j$, $min(distance(v_i, v_j))$ ...
0
votes
0answers
63 views

Looking for an algorithm to solve this optimization problem

I have a set of constants $C = \{c_1, c_2, \ldots, c_n\}$ and a set of variables $V = \{v_1, v_2, \ldots, v_n\}$, each element in $V$ is somewhere between $0$ and some maximum limit $U$. Let $S = c_1 ...
-2
votes
0answers
70 views

Find the city that is farthest away from its nearest police station

It is given an undirected graph $G = (V, E)$ and a weight function $w : E \rightarrow\mathbb{Z} ^{+}$, which we interpret as distance between vertices. The vertices of the graph are cities, and in ...
1
vote
1answer
56 views

Why does Kadane's algorithm solve the maximum sub-array problem?

I've tried to solve a exercise 4.1-5 in algorithm book "Introduction to algorithms". it is about Maximum sub-array problem, which is an algorithm that determines the greatest sum of sub-array A[i], ...
4
votes
3answers
104 views

Does Thompson's algorithm produce optimal NFAs?

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ...
-1
votes
0answers
28 views

Acm question solution approach

For the 2002 ACM-ICPC world finals competition, the last question from the set of problems, question L solution was a greedy approach, as we can see in the official ICPC video. Takeover Wars ...
3
votes
1answer
39 views

Algorithm for automatic/optimal database joins?

I'm curious if there is existing literature or well known algorithms out there for a problem I am working on. Given a normalized relational database with valid foreign key constraints and a list of ...
9
votes
0answers
101 views

size of maximum matching in a bipartite graph

I've been wondering if there's a way to determine the size of a maximum matching in a non weighted bipartite graph without paying the full price of actually computing the matching itself. It's a long ...
2
votes
1answer
32 views

Algorithms that are using John's ellipsoid

The Lowner–John ellipsoid is a minimum volume enclosing ellipsoid of some convex body $K$. This ellipsoid is unique (as is the maximum volume ellipsoid contained in $K$). I'm looking for ...
0
votes
2answers
62 views

Minimal length of a string that contains two strings

We have two strings $a,b$. I want to find string $c$ that includes $a$ as a subsequence and includes $b$ as a subsequence and the length of $c$ is minimal. Is there an efficient algorithm for this ...
0
votes
1answer
16 views

How to make the standard DP algorithm for 0/1 Knapsack make larger steps?

The standard knapsack problem solution is O(nW) where we will increment the weight +1 at a time to get to the solution. Is there any approach to the knapsack problem that does not require ...
4
votes
2answers
155 views

Data structure for sparse matrices for an online problem

I need to compute a large linear optimization problem very often after recieving updates to my optimization problem. That is I have a linear problem to find an x such that $x_1 * c_1 + ... + x_n * ...
0
votes
0answers
23 views

Computing optimal assignments using little memory

I have two lists where each item in the first list has a rating for each item in the second. I need to determine an optimal matching (or the best x scenarios) where items are matched, but each item ...
3
votes
0answers
38 views

Why are decision problems easier than the equivallent optimization problems?

Suppose that we have an optimization problem defined as follows: $OPT$ = Given an input string defining a set of feasible solutions $F$ and an objective function $f$, find $x\in F$ maximizing $f(x)$ ...
1
vote
0answers
11 views

optimising buffer allocation in a shared buffer (with total max capacity)

my intention is to optimise buffer allocation in a shared buffer (with total max capacity) where each incoming and outgoing packet belongs to a category(we have a finite number of categories < ...
1
vote
0answers
34 views

Why does the firefly algorithm need an intensity function?

I am studying the firefly algorithm and I would like to ask about the Intensity function that is defined at the beginning of the algorithm. What is it for? Some literature give different functions ...
1
vote
1answer
137 views

If the decision problem can be solved in poly time, show the optimization problem also can [duplicate]

Here is a problem I am trying to solve: The bin packing decision problem is defined as follows: given an unlimited number of bins, each of capacity equal to $1$, and $n$ objects with sizes ...
2
votes
0answers
23 views

Can smart recursive search find all optimal solutions for Closest String?

Consider the Closest String problem: Input: Strings $s_1, \dots, s_m \in \Sigma^n$ and $k \in \mathbb{N}$. Question: Is there $s \in \Sigma^n$ for which $d_H(s, s_i) \leq k$ for all $i ...
0
votes
0answers
23 views

Algorithms for keeping number of backups constant

The problem is quite simple: backups are done at regular time intervals (with possible but rare exceptions). The storage however is not unlimited, and only a certain number of backups can be stored, ...
1
vote
1answer
80 views

Is this problem NP-hard?

Good day. Subset sum selection problem is NP-hard. I trying to solve following problem: Input: a grid NxN and subset size K and radius R. Every entry in grid contains a value. Solution: subset of ...
1
vote
1answer
25 views

Ordered knapsack problem?

I'm trying to find the name of this problem, and with it a reasonable algorithmic solution. Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights ...
1
vote
1answer
28 views

Optimizing iteration over all permutations of a bit array

edited for clarity: I have two functions–$f(x)$ which returns an integer and $T(x)$ which returns a boolean–that operate on a bit array of length $n$. I am trying to maximize $f(x)$ over all $x$ ...
3
votes
1answer
62 views

Maximum Flow with Binary Capacities

Consider the problem of finding a maximum flow from node $s$ to node $t$ in a directed graph where each link has capacity either $0$ or $1$. What is the state of the art regarding how fast this flow ...
1
vote
0answers
32 views

TSP heuristics for limited distance information [closed]

this is my first question on ComputerScience beta. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for ...
0
votes
1answer
29 views

What makes an MILP problem solvable?

Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic ...
2
votes
1answer
38 views

Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization

I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any inaccuracies. Happy to clarify any part of the question which is unclear. Given the following ...
2
votes
1answer
92 views

Inventory Routing - Subtour Elimination [closed]

I'm trying to implement a Inventory Routing Problem with Branch-and-Cut. But I'm facing with an issue regarding subtour elimination. (http://www.danflash.com/files/irp.pdf) The paper describes the ...
6
votes
2answers
104 views

Real world applications for Steiner Tree Problem?

Are there real-world applications of the Steiner Tree Problem (STP)? I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that ...
1
vote
1answer
41 views

Combinatorial optimization problem - What would you call this?

I'm trying to solve an optimization problem which can be described as follows. There are four sets objects. For simplicity, let's call them : Apples Oranges Pears Lemons The sets can contain ...
2
votes
1answer
88 views

Which optimization algorithm would you recommend for this small multidimensional problem?

Which algorithm would be suitable for finding or estimating the vector $$\mathbf{s}_{opt}=\begin{bmatrix} s_1 & \cdots & s_N \end{bmatrix}=\arg\max_{\mathbf{s}}\sum_{n=1}^{N}p_{s_n,n}$$ ...
0
votes
0answers
25 views

Weighted Interval Scheduling with constraint

How do we solve the weighted interval scheduling problem if given a maximum weight? I understand the solution for the problem when we are simply interested in the maximum weight possible, but how do ...
0
votes
0answers
12 views

How do I model exploration and exploitation in an Ant Colony type algorithm?

A lot has been said about the process of exploration and exploitation in Ant Colony type systems. I am trying to write a program to better understand the dynamics of one such type of system. However, ...
1
vote
1answer
50 views

Standard problem sets for metaheuristics

I'm wanting to dabble with metaheuristics and am interested to know what the "hello world" problem sets are. In other words, what are the common problems (e.g Traveling Salesman, Vehicle Routing ...
-1
votes
1answer
28 views

Where to learn about Short-circuit evaluation? [closed]

I would like to implement short circuit evaluation logic in my code. And I want to know about the full details how it works? Ex: function a() {return true;} function b() {return false;} function ...
3
votes
1answer
84 views

Weighted interval scheduling with m-machines

I am looking for some advice and direction on solving the weighted interval scheduling problem with $m$-machines to plan some experimental "wet lab" procedures. The problem is very similar to the ...
2
votes
2answers
436 views

What are the k characters which make the most complete words?

Given a word list of $N$ words formed from a language of $M$ characters, where each word is composed of $n \geq 1$ not necessarily distinct characters, how can I find the best set of $k<M$ ...
3
votes
0answers
48 views

smallest satisfiability-equivalent formulas (generalized Tseitin transform)?

What is known about the following optimization problem for formulas in propositional logic: input: formula $F$ output: formula $G$ in CNF with $\mathrm{Var}(G) \supseteq \mathrm{Var}(F)$ such that ...
2
votes
1answer
60 views

How to choose between several constraints for a SAT task using quality metric?

I'm trying to solve a constraint programming problem using a SAT solver. I have set of constraints in the form of propositional logic statements, which are converted to CNF using Tseitin ...