### Top 10 Arxiv Papers Today in Data Structures And Algorithms

##### #1. Closed form distance formula for the balanced multiple travelling salesmen
###### Wolfgang Garn
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.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 6680
Unqiue Words: 2193

##### #2. A Greedy algorithm for local heating
###### Jiří Fink, Johann L. Hurink
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.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 6325
Unqiue Words: 1445

##### #3. Approximation algorithms for scheduling a group of heat pumps
###### Jiří Fink
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.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

##### #4. Bibliography of distributed approximation on structurally sparse graph classes
###### Laurent Feuilloley
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.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

##### #5. Strongly Stable and Maximum Weakly Stable Noncrossing Matchings
###### Koki Hamada, Shuichi Miyazaki, Kazuya Okamoto
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.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

##### #6. Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks
###### Michael Dinitz, Benjamin Moseley
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.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 9634
Unqiue Words: 2059

##### #7. Sorting Permutations with Fixed Pinnacle Set
###### Irena Rusu
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.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 11532
Unqiue Words: 1741

##### #8. A Pseudopolynomial Algorithm to Minimize Maximum Lateness on Multiple Related Machines
###### Elbert Du, Stan Zhang
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.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #9. Faster and Enhanced Inclusion-Minimal Cograph Completion
###### Christophe Crespelle, Daniel Lokshtanov, Thi Ha Duong Phan, Eric Thierry
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.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

##### #10. Some General Structure for Extremal Sparsification Problems
###### Greg Bodwin
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.
###### Other stats
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.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 257,975 papers.