Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
3
votes
0answers
41 views

Find the largest interior rectangle composed of partitioning rectangles

Suppose a rectangle $R$ is partitioned into more than one smaller rectangles of positive area. What is the fastest algorithm to find the largest rectangle strictly within the all-enclosing rectangle $...
3
votes
1answer
121 views

Finding the dichotomy that maximizes information gain for a classifier?

Suppose that $\Omega$ is a finite probability space,with measure $P$ (we can take $P$ uniform). Let $C \in \{\pm 1 \}$ be a random variable on $\Omega$, the classifier. Let $$H(C) = H(C, \Omega, P) = ...
2
votes
1answer
93 views

Complexity of special instance of Knapsack

Consider the following algorithmic task: Given: primes $p_1,\dots,p_k$, and positive integers $e_1,\dots,e_k$, and a positive integer $M$ Find: integers $d_1,\dots,d_k$ that maximize $\prod_i p_i^{...
2
votes
1answer
164 views

Grokking pseudo-code for solution to gas station problem

I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
2
votes
1answer
305 views

efficient algorithm for min cut with specified number of vertices

Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to ...
2
votes
2answers
187 views

The optimal way to reverse engineer a binary classification problem

I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it. In a scenario very similar to popular binary classification ...
2
votes
2answers
86 views

Optimal Partition of Book Chapters

Suppose you want to read a book with $n$ chapters, and chapter $i$ has $a_i$ pages. Now you want to read the entire book in $d$ days. But there are two restrictions: by the end of each day, you ...
2
votes
1answer
44 views

Graph partition that maximize the number of triangles within its parts

Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal? This ...
2
votes
1answer
73 views

What do we call a greedy algorithm that tracks the best $n > 1$ solutions?

A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima. To avoid this problem, we may keep track of the best $n > 1$ ...
2
votes
2answers
151 views

Distribution Optimization Algorithm

I'm trying to classify and come up with a reasonable solution for the following problem (abstracted from a real world problem). Problem Imagine StackOverflow started offering a subscription where ...
2
votes
1answer
255 views

How to reduce MaxUNSAT to MaxSAT?

Is it possible to reduce MaxUNSAT to MaxSAT in a polynomial way ? When considering the MaxSAT problem, one often considers also the MinUNSAT problem, which is ...
1
vote
0answers
117 views

MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

A paper was published recently in Science where the authors minimized the following function: $$E_{\text{Ising}}(s) = -\dfrac{1}{2} \Sigma_{i=1}^{N} \Sigma_{j=1}^{N} J_{i,j} s_i s_j,$$ where $s_i$ ...
1
vote
1answer
168 views

What's the meaning of “Front” in “Pareto-Optimal Front”?

I'm reading a paper about Multi-Objective Optimization Problem. I understand Optimal in Pareto sense, and I even know what is Pareto-Optimal Front somehow. But I can't find a relationship between the ...
1
vote
0answers
61 views

Given a tree find path that maximizes the median of the costs of edges

We have given tree with $N$ nodes and $N-1$ edges, such that each edges is assigned positive weight. We need to find path of length between $L$ and $R$ inclusively, with maximum cost. Cost of a path ...
1
vote
1answer
69 views

Reframing decision, counting, enumeration, and search as optimization

The top accepted answers to the questions below allude to two complexity classes of optimization problems: NPO and PO (in relation to NP and P for decision problems): Decision problems vs "real" ...
1
vote
0answers
252 views

Time Complexity of Binary Linear Programming

As far as I know, Integer Linear Programming(ILP) problem is NP-complete. According to the following paper, Binary Linear Programming problem(BLP) can be solved in Polynomial time. http://dx.doi.org/...
1
vote
0answers
579 views

Exact algorithm for the partition problem

The partition problem is: given a set of numbers, find a partition to two subsets in which the difference between the sums in each subset is minimized. This optimization problem is NP-hard. The simple ...
1
vote
0answers
405 views

When does Branch and Bound exactly stop giving solutions for the bin packing problem

I wrote a branch and bound algorithm for the bin packing problem and now I would like to know when exactly it stops giving solutions in a polynomial time. I have N items (each item i has a volume Vi)...
1
vote
1answer
270 views

Black-box combinatorial optimization problem over permutations

I am solving general black-box optimization problems like: x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is ...
1
vote
1answer
3k views

Interval Scheduling Problem with more than One Resource

Consider the interval scheduling problem, see also here. In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest ...
0
votes
1answer
107 views

How to reformulate my problem as a mixed-integer quadratic problem

I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the $...
0
votes
1answer
411 views

Using AI / Machine learning to find the most time and space efficient solutions to an algorithm [duplicate]

As programmers, we are always trying to find the most efficient space and time complexity solutions to algorithms. Is it forseeable in the future that we have languages or techniques such as AI/...
0
votes
0answers
86 views

Hessian in reinforcement learning

The Hessian of multi-layered network exhibits known behaviour at critical points as shown in [1]. The tools of random matrix theory allow [2] to deduce the asymptotic distribution of the eigenvalues ...
0
votes
2answers
146 views

How to partition disagreeable people into compatible groups

We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is ...
0
votes
1answer
120 views

How to exclude all points adjacent to a given point from the feasible region of IP

Consider a basic integer program such as: $$\begin{align} \min_x & \quad c^Tx \\ \text{s.t.} & \quad Ax \leq b \\ &\quad x_i \in \{-100,\ldots,100\} \end{align} $$ where $x \in \mathbb{...
0
votes
1answer
121 views

taking school courses efficiently

I want design algorithm that allows a student to take important courses quickly up until graduation. no time, room number, professors needed here. just my selected courses I know will allow me to ...
0
votes
1answer
129 views

Optimization problem in a social network

I would appreciate anybody's help with a problem I am trying to solve. A little background: given is a social network consisting of people represented as a directed graph, with edge from person A to ...
0
votes
2answers
3k views

Longest path in DAG or finding DAG diameter

A directed acyclic graph (DAG), is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way ...
0
votes
2answers
88 views

Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case

Lets say I have a list of many (10s of thousands - millions) objects, and each of these objects has a given number of 3-D vertices (my current implementation uses 8 vertices each, but this number can ...
0
votes
1answer
96 views

Array covering problem

Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational). Suppose that we chose some $Y = \{ y_1, ......
-1
votes
1answer
242 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 c() {...

1 2
3