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.

okateim:
2019/07/19 [6]
Makespan Minimization with OR-Precedence Constraints (https://t.co/nVcUCZgsMz)

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 8791

Unqiue Words: 1752

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
None.

okateim:
2019/07/19 [8]
Fast permutation-word multiplication and the simultaneous conjugacy problem (https://t.co/F3bP8mwXJl)

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

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.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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.

Sample Sizes : None.

Authors: 3

Total Words: 3778

Unqiue Words: 1004

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.

Sample Sizes : None.

Authors: 1

Total Words: 0

Unqiue Words: 0

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.

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible