Zobrazeno 1 - 10
of 69
pro vyhledávání: '"Georg Schnitger"'
Publikováno v:
SIAM Journal on Computing. 46:1029-1061
We give a simple, randomized greedy algorithm for the maximum satisfiability problem (MAX SAT) that obtains a $\frac{3}{4}$-approximation in expectation. In contrast to previously known $\frac{3}{4}$-approximation algorithms, our algorithm does not u
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5382f9fc82dfcae83cd08a2a9d30ab3f
https://doi.org/10.1137/15m1053369
https://doi.org/10.1137/15m1053369
Autor:
Stasys Jukna, Georg Schnitger
Publikováno v:
Theoretical Computer Science. 628:101-109
We prove a general lower bound on the size of switching-and-rectifier networks over any semiring of zero characteristic, including the ( min ? , + ) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::73922ee31c1492ab57e92d07649f2976
https://doi.org/10.1016/j.tcs.2016.03.014
https://doi.org/10.1016/j.tcs.2016.03.014
Autor:
Georg Schnitger
Publikováno v:
Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications ISBN: 9783319125671
Adventures Between Lower Bounds and Higher Altitudes
Adventures Between Lower Bounds and Higher Altitudes
We compare the number of states required for one-way probabilistic finite automata with a positive gap (1P\(_2\)FAs) and the number of states required for one-way alternating automata (1AFAs). We show that a 1P\(_2\)FA P can be simulated by 1AFA with
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bdc7dc28ea0b53d385d91817eee7d3b9
https://doi.org/10.1007/978-3-319-98355-4_8
https://doi.org/10.1007/978-3-319-98355-4_8
Autor:
Georg Schnitger, Stasys Jukna
Publikováno v:
Operations Research Letters. 40:272-275
For every positive integer l, we consider a zero-one linear program describing the following optimization problem: maximize the number of nodes in a clique of an n-vertex graph whose chromatic number does not exceed l. Although l is a trivial solutio
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2b6b514f7dfe485f6d1a7ab2cc5d5318
https://doi.org/10.1016/j.orl.2012.03.008
https://doi.org/10.1016/j.orl.2012.03.008
Publikováno v:
Information Processing Letters. 112:341-345
The paper describes a simple and fast randomized test for equality of grammar-compressed strings. The thorough running time analysis is done by applying a logarithmic cost measure.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::835aa38ab999ec636f440d245aa3fd3e
https://doi.org/10.1016/j.ipl.2012.01.008
https://doi.org/10.1016/j.ipl.2012.01.008
Autor:
Stasys Jukna, Georg Schnitger
Publikováno v:
Journal of Computer and System Sciences. 77(6):1023-1038
A completion of an m-by-n matrix A with entries in {0,1,*} is obtained by setting all *-entries to constants 0 or 1. A system of semi-linear equations over GF(2) has the form Mx=f(x), where M is a completion of A and f:{0,1}^n --> {0,1}^m is an opera
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::74b714a6c4119eb3d6879cf5a35bdb1a
Autor:
Georg Schnitger, Juraj Hromkovič
Publikováno v:
Information and Computation. 208:982-995
We study the most important probabilistic computation modes for pushdown automata. First we show that deterministic pushdown automata (pda) are weaker than Las Vegas pda, which in turn are weaker than one-sided-error pda. Next one-sided-error pda are
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5a65d11a3322737346f4f736dc8a7a65
https://doi.org/10.1016/j.ic.2009.11.001
https://doi.org/10.1016/j.ic.2009.11.001
Autor:
Georg Schnitger, Gregor Gramlich
Publikováno v:
Journal of Computer and System Sciences. 73(6):908-923
We show inapproximability results concerning minimization of nondeterministic finite automata (nfa's) as well as of regular expressions relative to given nfa's, regular expressions or deterministic finite automata (dfa's).We show that it is impossibl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::75c904a03e94599d88271fec1be3f97e
Autor:
Juraj Hromkovi, Georg Schnitger
Publikováno v:
Theoretical Computer Science. 380:100-114
The construction of an @e-free nondeterministic finite automaton (NFA) from a given NFA is a basic step in the development of compilers and computer systems. The standard conversion may produce an @e-free NFA with up to @W(n^[email protected]?|@S|) t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3115301d9128d47e920cbd2aa44fc30a
https://doi.org/10.1016/j.tcs.2007.02.063
https://doi.org/10.1016/j.tcs.2007.02.063
Autor:
Maik Weinard, Georg Schnitger
Publikováno v:
SIAM Journal on Discrete Mathematics. 20:502-522
We investigate the greedy algorithm for the shortest common superstring problem. We show that the length of the greedy superstring is upper-bounded by the sum of the lengths of an optimal superstring and an optimal cycle cover, provided the greedy al
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2f2addb8bc60b1483c7b27a23420b95d
https://doi.org/10.1137/040619144
https://doi.org/10.1137/040619144