262 research outputs found
An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs
Get PDFIn 1982 Papadimitriou and Yannakakis introduced the Exact Matching problem, in which given a red and blue edge-colored graph G and an integer k one has to decide whether there exists a perfect matching in G with exactly k red edges. Even though a randomized polynomial-time algorithm for this problem was quickly found a few years later, it is still unknown today whether a deterministic polynomial-time algorithm exists. This makes the Exact Matching problem an important candidate to test the RP=P hypothesis.
In this paper we focus on approximating Exact Matching. While there exists a simple algorithm that computes in deterministic polynomial-time an almost perfect matching with exactly k red edges, not a lot of work focuses on computing perfect matchings with almost k red edges. In fact such an algorithm for bipartite graphs running in deterministic polynomial-time was published only recently (STACS'23). It outputs a perfect matching with k' red edges with the guarantee that 0.5k ≤ k' ≤ 1.5k. In the present paper we aim at approximating the number of red edges without exceeding the limit of k red edges. We construct a deterministic polynomial-time algorithm, which on bipartite graphs computes a perfect matching with k' red edges such that k/3 ≤ k' ≤ k
On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
No full textRecoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consider recoverable robust optimization in combination with discrete budgeted uncertainty. In this setting, it seems plausible that many problems become -complete and therefore it is impossible to find compact IP formulations of them (unless the unlikely conjecture NP holds). Even though this seems plausible, few concrete results of this kind are known. In this paper, we fill that gap of knowledge. We consider recoverable robust optimization for the nominal problems of Sat, 3Sat, vertex cover, dominating set, set cover, hitting set, feedback vertex set, feedback arc set, uncapacitated facility location, -center, -median, independent set, clique, subset sum, knapsack, partition, scheduling, Hamiltonian path/cycle (directed/undirected), TSP, -disjoint path (), and Steiner tree. We show that for each of these problems, and for each of three widely used distance measures, the recoverable robust problem becomes -complete. Concretely, we show that all these problems share a certain abstract property and prove that this property implies that their robust recoverable counterpart is -complete. This reveals the insight that all the above problems are -complete \u27for the same reason\u27. Our result extends a recent framework by Grüne and Wulf
ERP software system comparison between Odoo and Microsoft Dynamics NAV
Get PDFThe purpose of the thesis was to compare the two ERP software systems Odoo and Microsoft Dynamics NAV. The thesis sought to find out if Odoo can replace the existing Microsoft Dynamics core functionalities.
The commissioner is Lasse Seppänen, a principal lecturer at HAMK (Häme University of Applied Sciences) in Finland. The university currently uses Microsoft Dynamics NAV to teach students about business information systems.
The thesis explores the Microsoft Dynamics NAV system’s current features and asks how Odoo meets these requirements. The objective is also to determine which ERP system serves the university best.
First, the thesis explains central concepts related to ERP systems. In order to compare the two ERP systems evaluation criteria investigated through literary research. The thesis proceeds by discussing the current ERP requirements. Based on this data Odoo and Microsoft Dynamics were analyzed.
The research compares the two ERP solutions. The outcome of the analysis shows that Odoo is an alternative in comparison to Microsoft Dynamics NAV. The author recommends that the university implement Odoo through the Odoo Education platform
Fictionality and Literature: Core Concepts Revisited
No full textAuthor / Henrik Zetterberg-Nielsen -- Narrator / Sylvie Patron -- Plot / Wendy Veronica Xin -- Character / H. Porter Abbott -- Consciousness / Maria Mäkelä -- Metaphor / Greta Olson -- Paratext / Louise Brix Jacobsen -- Intertextuality / Rikke Andersen Kraglund -- Metafiction and metalepsis / Richard Walsh -- The novel / Catherine Gallagher and Simona Zetterberg-Nielsen -- Poetry / Lasse R. Gammelgaard -- Literary nonfiction / James Phelan -- Ethics / Jakob Lothe -- Social justice / Susan S. Lanser.Item embargoed for five year
The Rating Game: Sentiment Rating Reproducibility from Text
No full textSentiment analysis models often use rat-ings as labels, assuming that these rat-ings reflect the sentiment of the accom-panying text. We investigate (i) whether human readers can infer ratings from re-view text, (ii) how human performance compares to a regression model, and (iii) whether model performance is affected by the rating “source ” (i.e. original author vs. annotator). We collect IMDb movie reviews with author-provided ratings, and have them re-annotated by crowdsourced and trained annotators. Annotators re-produce the original ratings better than a model, but are still far off in more than 5 % of the cases. Models trained on annotator-labels outperform those trained on author-labels, questioning the useful-ness of author-rated reviews as training data for sentiment analysis.
Optimal high-dimensional and nonparametric distributed testing under communication constraints
Get PDFWe derive minimax testing errors in a distributed framework where the data is
split over multiple machines and their communication to a central machine is
limited to bits. We investigate both the - and infinite-dimensional
signal detection problem under Gaussian white noise. We also derive distributed
testing algorithms reaching the theoretical lower bounds.
Our results show that distributed testing is subject to fundamentally
different phenomena that are not observed in distributed estimation. Among our
findings, we show that testing protocols that have access to shared randomness
can perform strictly better in some regimes than those that do not. We also
observe that consistent nonparametric distributed testing is always possible,
even with as little as -bit of communication and the corresponding test
outperforms the best local test using only the information available at a
single local machine. Furthermore, we also derive adaptive nonparametric
distributed testing strategies and the corresponding theoretical lower bounds.Comment: 53 page
Finn Søeborg - a forgotten welfare voice
No full textThis thesis examines popular Danish author Finn Søeborg’s relation to the public literary andhistorical debate surrounding the idea and consequences of the Danish welfare state during itsfoundation and heyday around 1950 to 1970. Through a thematic reading of all nine Søeborgnovelsthe thesis aims to clarify his specific contribution if any and present an educated guessas to why he has largely been passed over by previous research – has this been warranted?The broad themes chosen for the readings are materialism, conformism and bureaucracy, sochosen because they are believed to be concurrent and important within the debateindependently of the author himself. Any contribution is worth considering since currentresearch into Søeborg is scarce. The thematic readings are then cross-referenced with literaryhistoricalresearch by Lasse Horne Kjældgaard and Søren Schou among others, as well asprominent welfare state-commentary and fiction from that period. The studies find thatSøeborg did in fact write fully within the welfare-fiction framework and used the themesoutlined above and related welfare-tropes to weigh in.He writes fiction to further a moralistic anti-conformity and anti-state agenda where thosewho resist the onslaught of historicist conformity are elevated. Apart from these few themasses are an unfree, sorry lot and the future looks gloomy. Søeborg shares existentialistattitudes with Hans Jørgen Lembourn and anarchist attitudes with Johan Fjord Jensen –prominent welfare-commentators. He is different from them both however, in that he refusesall power-structures making literary alliances, recognition and categorization very difficult.The thesis concludes that Søeborg was a forerunner in terms of exploring in fiction some ofthe negative lifestyle effects resulting from the welfare state’s materialistic and bureaucraticexcesses, and should be held in higher regard historically for that reason; but his obstinatemoralism, mostly copying subject matter from the 1930s literature and not being able to fullyexpress his insights before they were displayed in a better way by others, is to his historicaland literary detriment
Optimal Distributed Composite Testing in High-Dimensional Gaussian Models With 1-Bit Communication
Get PDFIn this paper we study the problem of signal detection in Gaussian noise in a distributed setting where the local machines in the star topology can communicate a single bit of information. We derive a lower bound on the Euclidian norm that the signal needs to have in order to be detectable. Moreover, we exhibit optimal distributed testing strategies that attain the lower bound. </p
- …
