### Top 6 Arxiv Papers Today in Discrete Mathematics

##### #1. Makespan Minimization with OR-Precedence Constraints
###### Felix Happach
We consider a variant of the NP-hard problem of assigning jobs to machines to minimize the completion time of the last job. Usually, precedence constraints are given by a partial order on the set of jobs, and each job requires all its predecessors to be completed before it can start. In his seminal paper, Graham (1966) presented a simple 2-approximation algorithm, and, more than 40 years later, Svensson (2010) proved that 2 is essentially the best approximation ratio one can hope for in general. In this paper, we consider a different type of precedence relation that has not been discussed as extensively and is called OR-precedence. In order for a job to start, we require that at least one of its predecessors is completed - in contrast to all its predecessors. Additionally, we assume that each job has a release date before which it must not start. We prove that Graham's algorithm has an approximation guarantee of 2 also in this setting, and present a polynomial-time algorithm that solves the problem to optimality, if preemptions...
more | pdf | html
None.
###### Tweets
okateim: 2019/07/19 [6] Makespan Minimization with OR-Precedence Constraints (https://t.co/nVcUCZgsMz)
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 8791
Unqiue Words: 1752

##### #2. Fast permutation-word multiplication and the simultaneous conjugacy problem
Given a finite sequence $a_1, a_2,\ldots, a_d$ of $d$ permutations in the symmetric group $S_n$, and a permutation word $k_1k_2\cdots k_{m}$ over the alphabet $\{1,2,\ldots, d\}$, computation of the product $a_{k_1}a_{k_2}\cdots a_{k_{m}}$ in a straightforward manner takes $O(n m)$ time. However, it appears that this multiplication is such an elementary operation that, surprisingly enough, it went on unquestioned. We show that the above product can be computed in time $O(\min{\{ n m, n m \log d / \log m\}})$ using $O(m + n m^{\epsilon})$ space, where $0 < \epsilon < 1$. Consequently, this computation takes $o(n m)$ time whenever $\log d = o(\log m)$, which is a reasonable assumption in practice. The above result is used to solve the transitive simultaneous conjugacy problem in $O(n^2 \log d / \log n + dn\log n)$ time and $O(n^{1+ \epsilon} + dn)$ space, where $0 < \epsilon <1$. This problem asks whether there exists a permutation $\tau \in S_n$ such that $b_j = \tau^{-1} a_j \tau$ holds for all $j = 1,2, \ldots, d$, where $a_1,... more | pdf | html ###### Figures None. ###### Tweets okateim: 2019/07/19 [8] Fast permutation-word multiplication and the simultaneous conjugacy problem (https://t.co/F3bP8mwXJl) ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 3 Total Words: 0 Unqiue Words: 0 ###### 1.996 Mikeys ##### #3. Containment Graphs, Posets, and Related Classes of Graphs ###### Martin Charles Golumbic, Edward R. Scheinerman In this paper, we introduce the notion of the containment graph of a family of sets and containment classes of graphs and posets. Let$Z$be a family of nonempty sets. We call a (simple, finite) graph G = (V, E) a$Z$-containment graph provided one can assign to each vertex$v_i \in V $a set$S_i \in Z$such that$v_i v_j \in E$if and only if$S_i \subset S_j$or$S_j \subset S_i$. Similarly, we call a (strict) partially ordered set$P = (V, <)$a$Z$-containment poset if to each$v_i \in V $we can assign a set$S_i \in Z$such that$v_i < v_j$if and only if$S_i \subset S_j$. Obviously,$G$is the comparability graph of$P$. We give some basic results on containment graphs and investigate the containment graphs of iso-oriented boxes in$d\$-space. We present a characterization of those classes of posets and graphs that have containment representations by sets of a specific type, and we extend our results to injective'' containment classes. After that we discuss similar characterizations for intersection, overlap, and...
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #4. Online Firefighting on Grids
###### Marc Demange, David Ellison, Raffaella Gentilini
The Firefighter Problem (FP) is a graph problem originally introduced in 1995 to model the spread of a fire in a graph, which has attracted considerable attention in the literature. The goal is to devise a strategy to employ a given sequence of firefighters on strategic points in the graph in order to contain efficiently the fire (which spreads from each unprotected vertex to all of it neighbours on successive time steps). Recently, an online version of FP---where the number of firefighters available at each turn are revealed in real-time--- has been introduced in the literature and studied on trees. In this paper, we consider the online containment of fire on square grids. In particular, we provide a set of sufficient conditions that allow to solve the online version of the firefighting problem on infinite square grids, illustrating the corresponding fire containment strategies.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 3778
Unqiue Words: 1004

##### #5. Solving Systems of Linear Inequalities
###### Jean-Louis Lassez
Dantzig and Eaves claimed that fundamental duality theorems of linear programming were a trivial consequence of Fourier elimination. Another property of Fourier elimination is considered here, regarding the existence of implicit equalities rather than solvability. This leads to a different interpretation of duality theory and to a simple algorithm to determine if a system is solvable, in the bounded case or in the full dimensional case.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

##### #6. Linear-semiorders and their incomparability graphs
###### Asahi Takaoka
A linear-interval order is the intersection of a linear order and an interval order. For this class of orders, several structural results have been shown. In this paper, we study a natural subclass of linear-interval orders. We call a partial order a \emph{linear-semiorder} if it is the intersection of a linear order and a semiorder. We show a characterization of linear-semiorders in terms of linear extensions. This gives a vertex ordering characterization of their incomparability graphs. We also show that being a linear-semiorder is a comparability invariant.
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 160,428 papers.

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