Zobrazeno 1 - 10
of 679
pro vyhledávání: '"Woeginger, Gerhard J."'
An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decide
Externí odkaz:
http://arxiv.org/abs/2303.00569
We solve the recognition problem (RP) for the class of Demidenko matrices. Our result closes a remarkable gap in the recognition of specially structured matrices. Indeed, the recognition of permuted Demidenko matrices is a longstanding open problem,
Externí odkaz:
http://arxiv.org/abs/2302.05191
In the bipartite travelling salesman problem (BTSP), we are given $n=2k$ cities along with an $n\times n$ distance matrix and a partition of the cities into $k$ red and $k$ blue cities. The task is to find a shortest tour which alternately visits blu
Externí odkaz:
http://arxiv.org/abs/2302.05161
Publikováno v:
In Discrete Applied Mathematics 15 September 2024 354:3-14
We investigate the so-called recoverable robust assignment problem on balanced bipartite graphs with $2n$ vertices, a mainstream problem in robust optimization: For two given linear cost functions $c_1$ and $c_2$ on the edges and a given integer $k$,
Externí odkaz:
http://arxiv.org/abs/2010.11456
In the path version of the Travelling Salesman Problem (Path-TSP), a salesman is looking for the shortest Hamiltonian path through a set of n cities. The salesman has to start his journey at a given city s, visit every city exactly once, and finally
Externí odkaz:
http://arxiv.org/abs/2009.14746
We study a simple exchange market, introduced by Gourv\'{e}s, Lesca and Wilczynski (IJCAI-17), where every agent initially holds a single object. The agents have preferences over the objects, and two agents may swap their objects if they both prefer
Externí odkaz:
http://arxiv.org/abs/1905.04219
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition
Externí odkaz:
http://arxiv.org/abs/1811.08918
The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not received much attention in the algorithms community: Given two graphs $G,
Externí odkaz:
http://arxiv.org/abs/1802.08509