Transportation Network Companies employ dynamic pricing methods at periods of
peak travel to incentivise driver participation and balance supply and demand
for rides. Surge pricing multipliers are commonly used and are applied
following demand and estimates of customer and driver trip valuations.
Combinatorial double auctions have been identified as a suitable alternative,
as they can achieve maximum social welfare in the allocation by relying on
customers and drivers stating their valuations. A shortcoming of current
models, however, is that they fail to account for the effects of trip detours
that take place in shared trips and their impact on the accuracy of pricing
estimates. To resolve this, we formulate a new shared-ride assignment and
pricing algorithm using combinatorial double auctions. We demonstrate that this
model is reduced to a maximum weighted independent set model, which is known to
be APX-hard. A fast local search heuristic is also presented, which is capable
of producing results that lie within 1% of the exact...

more |
pdf
| html
None.

okateim:
2019/09/19 [5]
Assignment and Pricing of Shared Rides in Ride-Sourcing using Combinatorial Double Auctions (https://t.co/uYz1ZJW9ZK)

DO:
Assignment and Pricing of Shared Rides in Ride-Sourcing using Combinatorial Double Auctions. https://t.co/dtxV3buobC

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 0

Unqiue Words: 0

The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is
the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)|
\leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate
degree of the element distinctness function, the surjectivity function, and the
permutation testing problem, showing they are $\Theta(n^{2/3}
\log^{1/3}(1/\epsilon))$, $\tilde\Theta(n^{3/4} \log^{1/4}(1/\epsilon))$, and
$\Theta(n^{1/3} \log^{2/3}(1/\epsilon))$, respectively. Previously, these
bounds were known only for constant $\epsilon.$
We also derive a connection between vanishing-error approximate degree and
quantum Merlin--Arthur (QMA) query complexity. We use this connection to show
that the QMA complexity of permutation testing is $\Omega(n^{1/4})$. This
improves on the previous best lower bound of $\Omega(n^{1/6})$ due to Aaronson
(Quantum Information & Computation, 2012), and comes somewhat close to matching
a known upper bound of $O(n^{1/3})$.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

Fire Emblem (FE) is a popular turn-based tactical role-playing game (TRPG)
series on the Nintendo gaming consoles. This paper studies the computational
complexity of FE, and proves that: 1. General FE is PSPACE-complete. 2.
Poly-round FE is NP-complete, even when the map is cycle-free. Poly-round FE is
to decide whether the player can win the game in a certain number of rounds
that is polynomial to the map size. A map is called cycle-free if its
corresponding planar graph is cycle-free. These hardness results also hold for
other similar TRPG series, such as Final Fantasy Tactics, Tactics Ogre and
Disgaea.

more |
pdf
| html
okateim:
2019/09/18 [12]
The Computational Complexity of Fire Emblem Series and similar Tactical Role-Playing Games (https://t.co/B1Eu8bCtgK)

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 7983

Unqiue Words: 1895

The paper presents a polynomial time approximation schema for the
edge-weighted version of maximum k-vertex cover problem in bipartite graphs.

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 192,914 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible