As a first contribution the mTSP is solved using an exact method and two
heuristics, where the number of nodes per route is balanced. The first
heuristic uses a nearest node approach and the second assigns the closest
vehicle (salesman). A comparison of heuristics with test-instances being in the
Euclidean plane showed similar solution quality and runtime. On average, the
nearest node solutions are approximately one percent better. The closest
vehicle heuristic is especially important when the nodes (customers) are not
known in advance, e.g. for online routing. Whilst the nearest node is
preferable when one vehicle has to be used multiple times to service all
customers. The second contribution is a closed form formula that describes the
mTSP distance dependent on the number of vehicles and customers. Increasing the
number of salesman results in an approximately linear distance growth for
uniformly distributed nodes in a Euclidean grid plane. The distance growth is
almost proportional to the square root of number of customers...

more |
pdf
| html
None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 6680

Unqiue Words: 2193

This paper studies a planning problem for supplying hot water in domestic
environment. Hereby, boilers (e.g. gas or electric boilers, heat pumps or
microCHPs) are used to heat water and store it for domestic demands. We
consider a simple boiler which is either turned on or turned off and is
connected to a buffer of limited capacity. The energy needed to run the boiler
has to be bought e.g. on a day-ahead market, so we are interested in a planning
which minimizes the cost to supply the boiler with energy in order to fulfill
the given heat demand. We present a greedy algorithm for this heating problem
whose time complexity is O(T {\alpha}(T )) where T is the number of time
intervals and {\alpha} is the inverse of Ackermann function.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 6325

Unqiue Words: 1445

This paper studies planning problems for a group of heating systems which
supply the hot water demand for domestic use in houses. These systems (e.g. gas
or electric boilers, heat pumps or microCHPs) use an external energy source to
heat up water and store this hot water for supplying the domestic demands. The
latter allows to some extent a decoupling of the heat production from the heat
demand. We focus on the situation where each heating system has its own demand
and buffer and the supply of the heating systems is coming from a common
source. In practice, the common source may lead to a coupling of the planning
for the group of heating systems. The bottleneck to supply the energy may be
the capacity of the distribution system (e.g. the electricity networks or the
gas network). As this has to be dimensioned for the maximal consumption, it is
important to minimize the maximal peak. This planning problem is known to be
\NP-hard. We present polynomial-time approximation algorithms for four variants
of peak minimization problems, and...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 0

Unqiue Words: 0

This document is an informal bibliography of the papers dealing with
distributed approximation algorithms on graphs classes that are sparse, but not
in the classic setting of bounded degree. We call these classes
\emph{structurally sparse} which means that they are sparse because of their
geometric nature (planar, bounded genus and unit-disk graphs) and/or because
they have bounded parameters (arboricity, expansion, growth, independence) or
forbidden structures (forbidden minors).

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 0

Unqiue Words: 0

In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings,
where participants of each side are aligned on each of two parallel lines, and
no two matching edges are allowed to cross each other. They defined two
stability notions, strongly stable noncrossing matching (SSNM) and weakly
stable noncrossing matching (WSNM), depending on the strength of blocking
pairs. They proved that a WSNM always exists and presented an O(n^{2})-time
algorithm to find one for an instance with n men and n women. They also posed
open questions of the complexities of determining existence of an SSNM and
finding a largest WSNM. In this paper, we show that both problems are solvable
in polynomial time. Our algorithms are applicable to extensions where
preference lists may include ties, except for one case which we show to be
NP-complete.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

New optical technologies offer the ability to reconfigure network topologies
dynamically, rather than setting them once and for all. This is true in both
optical wide area networks (optical WANs) and in datacenters, despite the many
differences between these two settings. Because of these new technologies,
there has been a surge of both practical and theoretical research on algorithms
to take advantage of them. In particular, Jia et al. [INFOCOM '17] designed
online scheduling algorithms for dynamically reconfigurable topologies for both
the makespan and sum of completion times objectives. In this paper, we work in
the same setting but study an objective that is more meaningful in an online
setting: the sum of flow times. The flow time of a job is the total amount of
time that it spends in the system, which may be considerably smaller than its
completion time if it is released late. We provide competitive algorithms for
the online setting with speed augmentation, and also give a lower bound proving
that speed augmentation is in...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 9634

Unqiue Words: 2059

We give a positive answer to a question raised by Davis et al. ({\em Discrete
Mathematics} 341, 2018), concerning permutations with the same pinnacle set.
Given $\pi\in S_n$, a {\em pinnacle} of $\pi$ is an element $\pi_i$ ($i\neq
1,n$) such that $\pi_{i-1}<\pi_i>\pi_{i+1}$. The question is: given
$\pi,\pi'\in S_n$ with the same pinnacle set $S$, is there a sequence of
operations that transforms $\pi$ into $\pi'$ such that all the intermediate
permutations have pinnacle set $S$? We introduce {\em balanced reversals},
defined as reversals that do not modify the pinnacle set of the permutation to
which they are applied. Then we show that $\pi$ may be sorted by balanced
reversals (i.e. transformed into a standard permutation $\Id_S$), implying that
$\pi$ may be transformed into $\pi'$ using at most $4n-2\min\{p,3\}$ balanced
reversals, where $p=|S|\geq 1$. In case $p=0$, at most $2n-1$ balanced
reversals are needed.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 11532

Unqiue Words: 1741

In this paper, we will find a pseudopolynomial algorithm to solve $Qm \mid
\mid L_{\max}$ and then we will prove that it is impossible to get any
constant-factor approximation in polynomial time, and thus also impossible to
have a PTAS for this problem. We will also show that the the problem when we
don't assume a fixed number of machines, $P \mid \mid L_{\max}$, is strongly
NP-hard.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

We design two incremental algorithms for computing an inclusion-minimal
completion of an arbitrary graph into a cograph. The first one is able to do so
while providing an additional property which is crucial in practice to obtain
inclusion-minimal completions using as few edges as possible : it is able to
compute a minimum-cardinality completion of the neighbourhood of the new vertex
introduced at each incremental step. It runs in $O(n+m')$ time, where $m'$ is
the number of edges in the completed graph. This matches the complexity of the
algorithm in [Lokshtanov, Mancini and Papadopoulos 2010] and positively answers
one of their open questions. Our second algorithm improves the complexity of
inclusion-minimal completion to $O(n+m\log^2 n)$ when the additional property
above is not required. Moreover, we prove that many very sparse graphs, having
only $O(n)$ edges, require $\Omega(n^2)$ edges in any of their cograph
completions. For these graphs, which include many of those encountered in
applications, the improvement we obtain on...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 0

Unqiue Words: 0

This paper is about a branch of theoretical computer science that studies how
much graphs can be sparsified while faithfully preserving their properties.
Examples include spanners, distance preservers, reachability preservers, etc.
We introduce an abstraction that captures all of the above, and then we prove a
couple simple structural lemmas about this abstraction. These imply unified
proofs of some state-of-the-art results in the area, and they improve the size
of Chechik's $+4$ additive spanner [SODA '13] from $\widetilde{O}(n^{7/5})$ to
$O(n^{7/5})$.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 0

Unqiue Words: 0

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 257,975 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible