检索结果-内蒙古大学图书馆

arXiv 2024年

作者： Cembrano, Javier Correa, José Díaz, Gonzalo Verdugo, Victor Department of Algorithms and Complexity Max Planck Institute for Informatics Germany Department of Industrial Engineering Universidad de Chile Chile SC Johnson Graduate School of Management Cornell University United States Institute for Mathematical and Computational Engineering PUC Chile Chile Department of Industrial and Systems Engineering School of Engineering PUC Chile Chile

How to elect the representatives in legislative bodies is a question that every modern democracy has to answer. This design task has to consider various elements so as to fulfill the citizens’ expectations and contribute to the maintenance of a healthy democracy. The notion of proportionality, in that the support of a given idea in the house should be nearly proportional to its support in the general public, lies at the core of this design task. In the last decades, demographic aspects beyond political support have been incorporated by requiring that they are also fairly represented in the body, giving rise to a multidimensional version of the apportionment problem. In this work, we provide an axiomatic justification for a recently proposed notion of multidimensional proportionality and extend it to encompass two relevant constraints often used in electoral systems: a threshold on the number of votes that a list needs in order to be eligible and the election of the most-voted candidate in each district. We then build upon these results to design methods based on multidimensional proportionality. We use the Chilean Constitutional Convention election (May 15-16, 2021) results as a testing ground—where the dimensions are given by political lists, districts, and genders—and compare the apportionment obtained under each method according to three criteria: proportionality, representativeness, and voting power. While local and global methods exhibit a natural trade-off between local and global proportionality, including the election of most-voted candidates on top of methods based on 3-dimensional proportionality allows us to incorporate both notions while ensuring higher levels of representativeness and a balanced voting power. Copyright © 2024, The Authors. All rights reserved.

关键词： Design

来源：评论

学校读者我要写书评

暂无评论

A best possible result for the square of a 2-block to be hamiltonian

arXiv

引用

arXiv 2019年

作者： Ekstein, Jan Fleischner, Herbert Department of Mathematics and European Centre of Excellence NTIS - New Technologies for the Information Society Faculty of Applied Sciences University of West Bohemia Pilsen Technická 8 Plzeň306 14 Institute of Logic and Computation Algorithms and Complexity Group Technical University of Vienna Favoritenstrasse 9-11 Wien1040 Austria

It is shown that for any choice of four different vertices x1,...,x4 in a 2-block G of order p > 3, there is a hamiltonian cycle in G2 containing four different edges xiyi of E(G) for certain vertices yi, i = 1,2,3... 详细信息

关键词： Hamiltonians

来源：评论

学校读者我要写书评

暂无评论

Graphs with at most two moplexes

arXiv

引用

arXiv 2021年

作者： Dallard, Clément Ganian, Robert Hatzel, Meike Krnc, Matjaž Milanič, Martin Lifo Ea 4022 Insa Centre Val de Loire Université d'Orléans Orléans France Algorithms and Complexity Group Tu Wien Vienna Austria National Institute of Informatics Tokyo Japan Famnit University of Primorska Koper Slovenia Famnit Iam University of Primorska Koper Slovenia

A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes such as interval graphs, claw-free, and diamond-free graphs. However, while every non-complete graph has at least two moplexes, little is known about structural properties of graphs with a bounded number of moplexes. The study of these graphs is, in part, motivated by the parallel between moplexes in general graphs and simplicial modules in chordal graphs: unlike in the moplex setting, properties of chordal graphs with a bounded number of simplicial modules are well understood. For instance, chordal graphs having at most two simplicial modules are interval. In this work we initiate an investigation of k-moplex graphs, which are defined as graphs containing at most k moplexes. Of particular interest is the smallest nontrivial case k = 2, which forms a counterpart to the class of interval graphs. As our main structural result, we show that, when restricted to connected graphs, the class of 2-moplex graphs is sandwiched between the classes of proper interval graphs and cocomparability graphs;moreover, both inclusions are tight for hereditary classes. From a complexity theoretic viewpoint, this leads to the natural question of whether the presence of at most two moplexes guarantees a sufficient amount of structure to efficiently solve problems that are known to be intractable on cocomparability graphs, but not on proper interval graphs. We develop new reductions that answer this question negatively for two prominent problems fitting this profile, namely Graph Isomorphism and Max-Cut. On the other hand, we prove that every connected 2-moplex graph contains a Hamiltonian path, generalising the same property of connected proper interval graphs. Furthermore, for graphs wi

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

The most general structure of graphs with hamiltonian or hamiltonian connected square

arXiv

引用

arXiv 2022年

作者： Ekstein, Jan Fleischner, Herbert Department of Mathematics European Centre of Excellence Ntis - New Technologies for the Information Society Faculty of Applied Sciences University of West Bohemia Pilsen Technická 8 Plzeň306 14 Czech Republic Institute of Logic and Computation Algorithms and Complexity Group Technical University of Vienna Favoritenstrasse 9 - 11 Wien1040 Austria

On the basis of recent results on hamiltonicity, [4], and hamiltonian connectedness, [8], in the square of a 2-block, we determine the most general block-cutvertex structure a graph G may have in order to guarantee that G2 is hamiltonian, hamiltonian connected, respectively. Such an approach was already developed in [9] for hamiltonian total *** Codes 05C38, 05C45 © 2022, CC BY.

关键词： Hamiltonians

来源：评论

学校读者我要写书评

暂无评论

Untangling Circular Drawings: algorithms and complexity

arXiv

引用

arXiv 2021年

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Rutter, Ignaz Wu, Hsiang-Yun Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Vienna Austria University of Passau Passau Germany Research Unit of Computer Graphics TU Wien Vienna Austria St. Pölten University of Applied Sciences St. Pölten Austria

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G = (V, E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift◦(δG) as the minimum number of vertices that are required to be shifted in order to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift◦(δG) ≤ K for a given integer K, is NP-complete. For n-vertex outerplanar graphs, we obtain a tight upper bound of shift◦(δG) ≤ n − ⌊√n − 2⌋ − 2. Moreover, we study the Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. For this problem, we provide a tight upper bound shift◦(δG) ≤ ⌊n/2⌋ − 1 and present a constructive polynomial-time algorithm to compute the circular shifting number of almost-planar drawings. © 2021, CC BY.

关键词： Drawing (graphics)

来源：评论

学校读者我要写书评

暂无评论

Integer programming and incidence treedepth

arXiv

引用

arXiv 2020年

作者： Eiben, Eduard Ganian, Robert Knop, Dušan Ordyniak, Sebastian Pilipczuk, Michal Wrochna, Marcin Department of Computer Science Royal Holloway University of London United Kingdom Algorithms and Complexity Group Vienna University of Technology Austria Department of Theoretical Computer Science Czech Technical University in Prague Czech Republic School of Computing University of Leeds United Kingdom Institute of Informatics University of Warsaw Poland University of Oxford United Kingdom

Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that end, integer linear programming is fixed-parameter tractable with respect to the primal (or dual) treedepth of the Gaifman graph of its constraint matrix and the largest coefficient (in absolute value). Motivated by this, Koutecký, Levin, and Onn [ICALP 2018] asked whether it is possible to extend these result to a more broader class of integer linear programs. More formally, is integer linear programming fixed-parameter tractable with respect to the incidence treedepth of its constraint matrix and the largest coefficient (in absolute value)? We answer this question in negative. In particular, we prove that deciding the feasibility of a system in the standard form, Ax = b, l 6 x 6 u, is NP-hard even when the absolute value of any coefficient in A is 1 and the incidence treedepth of A is 5. Consequently, it is not possible to decide feasibility in polynomial time even if both the assumed parameters are constant, unless P = NP. Moreover, we complement this intractability result by showing tractability for natural and only slightly more restrictive settings, namely: (1) treedepth with an additional bound on either the maximum arity of constraints or the maximum number of occurrences of variables and (2) the vertex cover number. Copyright © 2020, The Authors. All rights reserved.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

Revisiting the hamiltonian theme in the square of a block: The general case

arXiv

引用

arXiv 2018年

作者： Fleischner, Herbert Chia, Gek L. Institute of Logic and Computation Algorithms and Complexity Group Technical University of Vienna Austria Department of Mathematical and Actuarial Sciences Lee Kong Chian Faculty of Engineering and Science Universiti Tunku Abdul Rahman Sungai Long Campus Jalan Sungai Long Bandar Sungai Long Cheras KajangSelangor43000 Malaysia Institute of Mathematical Sciences University of Malaya Kuala Lumpur50603 Malaysia

This is the second part of joint research in which we show that every 2-connected graph G has the F4 property. That is, given distinct xi ∈ V (G), 1 ≤ i ≤ 4, there is an x1x2-hamiltonian path in G2 containing different edges x3y3, x4y4 ∈ E(G) for some y3, y4 ∈ V (G). However, it was shown already in [3, Theorem 2] that 2-connected DT-graphs have the F4 property;based on this result we generalize it to arbitrary 2-connected graphs. We also show that these results are best possible. Copyright © 2018, The Authors. All rights reserved.

关键词： Hamiltonians

来源：评论

学校读者我要写书评

暂无评论

Geometric systems of unbiased representatives

arXiv

引用

arXiv 2020年

作者： Banik, Aritra Bhattacharya, Bhaswar B. Bhore, Sujoy Martínez-Sandoval, Leonardo School of Computer Sciences National Institute of Science Education and Research HBNI Bhubaneswar India Department of Statistics University of Pennsylvania Philadelphia United States Algorithms and Complexity Group Technische Universität Wien Austria Institut de Mathématiques de Jussieu-Paris Rive Gauche UMR 7586 Sorbonne Université France

Let P be a set of points in Rd, B a bicoloring of P and O a family of geometric objects (that is, intervals, boxes, balls, etc). An object from O is called balanced with respect to B if it contains the same number of points from each color of B. For a collection B of bicolorings of P, a geometric system of unbiased representatives (G-SUR) is a subset O0 ⊆ O such that for any bicoloring B of B there is an object in O0 that is balanced with respect to B. We study the problem of finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, size-restricted intervals, axis-parallel boxes and Euclidean balls. We show that the G-SUR problem is NP-hard even in the simple case of points on a line and interval ranges. Furthermore, we study a related problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring. Our results are a natural extension to a geometric context of the work initiated by Balachandran et al. on arbitrary systems of unbiased representatives. Copyright © 2020, The Authors. All rights reserved.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Envy-free dynamic pricing schemes

arXiv

引用

arXiv 2023年

作者： Bérczi, Kristóf Codazzi, Laura Golak, Julian Grigoriev, Alexander MTA-ELTE Momentum Matroid Optimization Research Group MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary Institute of Algorithms and Complexity Hamburg University of Technology Hamburg Germany Department of Data Analytics and Digitalisation Maastricht University Maastricht Netherlands

A combinatorial market consists of a set of indivisible items and a set of agents, where each agent has a valuation function that specifies for each subset of items its value for the given agent. From an optimization point of view, the goal is usually to determine a pair of pricing and allocation of the items that provides an efficient distribution of the resources, i.e., maximizes the social welfare, or is as profitable as possible for the seller, i.e., maximizes the revenue. To overcome the weaknesses of mechanisms operating with static prices, a recent line of research has concentrated on dynamic pricing schemes. In this model, agents arrive in an unspecified sequential order, and the prices can be updated between two agent-arrivals. Though the dynamic setting is capable of maximizing social welfare in various scenarios, the assumption that the agents arrive one after the other eliminates the standard concept of fairness. In this paper, we study the existence of optimal dynamic prices under fairness constraints in unit-demand markets. We propose four possible notions of envy-freeness of different strength depending on the time period over which agents compare themselves to others: the entire time horizon, only the past, only the future, or only the present. For social welfare maximization, while the first definition leads to Walrasian equilibria, we give polynomial-time algorithms that always find envy-free optimal dynamic prices in the remaining three cases. In contrast, for revenue maximization, we show that the corresponding problems are APX-hard if the ordering of the agents is fixed. On the positive side, we give polynomial-time algorithms for the setting when the seller can choose the order in which agents arrive. © 2023, CC BY.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

A unifying framework for characterizing and computing width measures

arXiv

引用

arXiv 2021年

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Jaffke, Lars Kwon, O-Joung Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Vienna Austria Department of Informatics University of Bergen Bergen Norway Department of Mathematics Incheon National University Incheon Korea Republic of Discrete Mathematics Group Institute for Basic Science Daejeon Korea Republic of

algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify F-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of F-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can compute every possible F-branchwidth, providing a unifying framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width *** Codes 68Q27 Copyright © 2021, The Authors. All rights reserved.

关键词： Parameter estimation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：