Episciences.org
Not a member yet
6707 research outputs found
Sort by
Minkowski's successive minima in convex and discrete geometry
No full textIn this short survey we want to present some of the impact of Minkowski'ssuccessive minima within Convex and Discrete Geometry. Originally related tothe volume of an -symmetric convex body, we point out relations of thesuccessive minima to other functionals, as e.g., the lattice point enumeratoror the intrinsic volumes and we present some old and new conjectures aboutthem. Additionally, we discuss an application of successive minima to a versionof Siegel's lemma.Comment: Accepted for publication in Communications in Mathematic
From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows
No full textAn s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow thatreaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other thans. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity n − 1, a network Nadmits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoints-branchings. Thus a classical result by Edmonds stating that a digraph contains k arc-disjoints-branchings if and only if the indegree of every set X ⊆ V (D) \ {s} is at least k also characterizesthe existence of k arc-disjoint s-branching flows in those networks, suggesting that the larger thecapacities are, the closer an s-branching flow is from simply being an s-branching. This observationis further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomialalgorithm to find the flows (if they exist) when every arc has capacity n − c, for every fixed c ≥ 1,and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper,we investigate how a property that is a natural extension of the characterization by Edmonds’ relatesto the existence of k arc-disjoint s-branching flows in networks. Although this property is alwaysnecessary for the existence of the flows, we show that it is not always sufficient and that it is hardto decide if the desired flows exist even if we know beforehand that the network satisfies it. On thepositive side, we show that it guarantees the existence of the desired flows in some particular casesdepending on the choice of the capacity function or on the structure of the underlying graph of D,for example. We remark that, in those positive cases, polynomial time algorithms to find the flowscan be extracted from the constructive proofs
Smart Choices and the Selection Monad
No full textDescribing systems in terms of choices and their resulting costs and rewardsoffers the promise of freeing algorithm designers and programmers fromspecifying how those choices should be made; in implementations, the choicescan be realized by optimization techniques and, increasingly, bymachine-learning methods. We study this approach from a programming-languageperspective. We define two small languages that support decision-makingabstractions: one with choices and rewards, and the other additionally withprobabilities. We give both operational and denotational semantics. In the case of the second language we consider three denotational semantics,with varying degrees of correlation between possible program values andexpected rewards. The operational semantics combine the usual semantics ofstandard constructs with optimization over spaces of possible executionstrategies. The denotational semantics, which are compositional, rely on theselection monad, to handle choice, augmented with an auxiliary monad to handleother effects, such as rewards or probability. We establish adequacy theorems that the two semantics coincide in all cases.We also prove full abstraction at base types, with varying notions ofobservation in the probabilistic case corresponding to the various degrees ofcorrelation. We present axioms for choice combined with rewards andprobability, establishing completeness at base types for the case of rewardswithout probability
Optimal controller synthesis for timed systems
No full textWeighted timed games are zero-sum games played by two players on a timedautomaton equipped with weights, where one player wants to minimise thecumulative weight while reaching a target. Used in a reactive synthesisperspective, this quantitative extension of timed games allows one to measurethe quality of controllers in real-time systems. Weighted timed games arenotoriously difficult and quickly undecidable, even when restricted tonon-negative weights. For non-negative weights, the largest class that can beanalysed has been introduced by Bouyer, Jaziri and Markey in 2015. Though thevalue problem is undecidable, the authors show how to approximate the value byconsidering regions with a refined granularity. In this work, we extend thisclass to incorporate negative weights, allowing one to model energy forinstance, and prove that the value can still be approximated, with the samecomplexity. A small restriction also allows us to obtain a class of decidableweighted timed games with negative weights and an arbitrary number of clocks.In addition, we show that a symbolic algorithm, relying on the paradigm ofvalue iteration, can be used as an approximation/computation schema over theseclasses. We also consider the special case of untimed weighted games, where thesame fragments are solvable in polynomial time: this contrasts with thepseudo-polynomial complexity, known so far, for weighted games withoutrestrictions.Comment: arXiv admin note: text overlap with arXiv:1812.0106
New Results on Directed Edge Dominating Set
No full textWe study a family of generalizations of Edge Dominating Set on directedgraphs called Directed -Edge Dominating Set. In this problem an arc is said to dominate itself, as well as all arcs which are at distanceat most from , or at distance at most to . First, we give significantly improved FPT algorithms for the two mostimportant cases of the problem, -dEDS and -dEDS (that correspondto versions of Dominating Set on line graphs), as well as polynomial kernels.We also improve the best-known approximation for these cases from logarithmicto constant. In addition, we show that -dEDS is FPT parameterized by, but W-hard parameterized by (even if the size of the optimal isadded as a second parameter), where is the treewidth of the underlyinggraph of the input. We then go on to focus on the complexity of the problem on tournaments. Here,we provide a complete classification for every possible fixed value of ,which shows that the problem exhibits a surprising behavior, including caseswhich are in P; cases which are solvable in quasi-polynomial time but not in P;and a single case which is NP-hard (under randomized reductions) andcannot be solved in sub-exponential time, under standard assumptions
Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs
No full textWe study countably infinite Markov decision processes (MDPs) with real-valuedtransition rewards. Every infinite run induces the following sequences ofpayoffs: 1. Point payoff (the sequence of directly seen transition rewards), 2.Mean payoff (the sequence of the sums of all rewards so far, divided by thenumber of steps), and 3. Total payoff (the sequence of the sums of all rewardsso far). For each payoff type, the objective is to maximize the probabilitythat the is non-negative. We establish the complete picture of thestrategy complexity of these objectives, i.e., how much memory is necessary andsufficient for -optimal (resp. optimal) strategies. Some cases canbe won with memoryless deterministic strategies, while others require a stepcounter, a reward counter, or both.Comment: arXiv admin note: substantial text overlap with arXiv:2107.0328
Destroying Multicolored Paths and Cycles in Edge-Colored Graphs
No full textWe study the computational complexity of -Colored Deletion and-Colored Deletion. In these problems, one is given a-edge-colored graph and wants to destroy all induced -colored paths orcycles, respectively, on vertices by deleting at most edges. Herein,a path or cycle is -colored if it contains edges of distinct colors. Weshow that -Colored Deletion and -Colored Deletion areNP-hard for each non-trivial combination of and . We then analyze theparameterized complexity of these problems. We extend the notion ofneighborhood diversity to edge-colored graphs and show that both problems arefixed-parameter tractable with respect to the colored neighborhood diversity ofthe input graph. We also provide hardness results to outline the limits ofparameterization by the standard parameter solution size . Finally, weconsider bicolored input graphs and show a special case of -Colored Deletion that can be solved in polynomial time.Comment: 31 page
On the motive of O'Grady's six dimensional hyper-K\"{a}hler varieties
No full textWe prove that the rational Chow motive of a six dimensional hyper-K\"{a}hlervariety obtained as symplectic resolution of O'Grady type of a singular modulispace of semistable sheaves on an abelian surface belongs to the tensorcategory of motives generated by the motive of . We in fact give a formulafor the rational Chow motive of such a variety in terms of that of the surface.As a consequence, the conjectures of Hodge and Tate hold for manyhyper-K\"{a}hler varieties of OG6-type.Comment: 10 pages; final version, published in EPIG
Quartic surfaces, their bitangents and rational points
No full textLet X be a smooth quartic surface not containing lines, defined over a numberfield K. We prove that there are only finitely many bitangents to X which aredefined over K. This result can be interpreted as saying that a certainsurface, having vanishing irregularity, contains only finitely many rationalpoints. In our proof, we use the geometry of lines of the quartic double solidassociated to X. In a somewhat opposite direction, we show that on any quarticsurface X over a number field K, the set of algebraic points in X(\overeline K)which are quadratic over a suitable finite extension K' of K is Zariski-dense.Comment: This is the final version of the pape
A modular relation involving a generalized digamma function and asymptotics of some integrals containing Ξ(t)
No full textA modular relation of the form , where and , is obtained. It involves the generalized digamma function which was recently studied by the authors in their work on developing the theory of the generalized Hurwitz zeta function . The limiting case of this modular relation is a famous result of Ramanujan on page of the Lost Notebook. We also obtain asymptotic estimate of a general integral involving the Riemann function as . Not only does it give the asymptotic estimate of the integral occurring in our modular relation as a corollary but also some known results