Top 4 Arxiv Papers Today in Computational Complexity

#1. Assignment and Pricing of Shared Rides in Ride-Sourcing using Combinatorial Double Auctions
Renos Karamanis, Eleftherios Anastasiadis, Panagiotis Angeloudis, Marc Stettler
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.
Tweets
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.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

#2. Vanishing-Error Approximate Degree and QMA Complexity
Alexander A. Sherstov, Justin Thaler
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.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

#3. The Computational Complexity of Fire Emblem Series and similar Tactical Role-Playing Games
Jiawei Gao
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
Tweets
okateim: 2019/09/18 [12] The Computational Complexity of Fire Emblem Series and similar Tactical Role-Playing Games (https://t.co/B1Eu8bCtgK)
None.
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 7983
Unqiue Words: 1895

#4. A polynomial time approximation schema for maximum k-vertex cover in bipartite graphs
Vangelis Th. Paschos
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.
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 192,914 papers.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
Stats
Tracking 192,914 papers.