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

The Complexity of Finding Fair Many-to-One Matchings

ACM TRANSACTIONS ON algorithms 2024年第2期20卷 1-37页

作者： Boehmer, Niclas Koana, Tomohiro Tech Univ Berlin Str 17 Juni 135 D-10623 Berlin Germany

We analyze the (parameterized) computational complexity of "fair" variants of bipartite many-to-one matching, where each vertex from the "left" side is matched to exactly one vertex and each vertex from the "right" side may be matched to multiple vertices. We want to find a "fair" matching, in which each vertex from the right side is matched to a "fair" set of vertices. Assuming that each vertex from the left side has one color modeling its "attribute", we study two fairness criteria. For instance, in one of them, we deem a vertex set fair if for any two colors, the difference between the numbers of their occurrences does not exceed a given threshold. Fairness is, for instance, relevant when finding many-to-one matchings between students and colleges, voters and constituencies, and applicants and firms. Here colors may model sociodemographic attributes, party memberships, and qualifications, respectively. We show that finding a fair many-to-one matching is NP-hard even for three colors and maximum degree five. Our main contribution is the design of fixed-parameter tractable algorithms with respect to the number of vertices on the right side. Our algorithms make use of a variety of techniques including color coding. At the core lie integer linear programs encoding Hall like conditions. We establish the correctness of our integer programs, based on Frank's separation theorem [Frank, Discrete Math. 1982]. We further obtain complete complexity dichotomies regarding the number of colors and the maximum degree of each side.

关键词： Graph theory polynomial-time algorithms NP-hardness FPT ILP color coding submodular and supermodular functions algorithmic fairness

来源：评论

学校读者我要写书评

暂无评论

Default reasoning from conditional knowledge bases: Complexity and tractable cases

引用

ARTIFICIAL INTELLIGENCE 2000年第2期124卷 169-241页

作者： Eiter, T Lukasiewicz, T Vienna Univ Technol Inst & Ludwig Wittgenstein Labor Informat Syst A-1040 Vienna Austria

Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form "phi --> psi", which informally read as "generally, if phi then psi". Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their computational properties only partial results are known so far. In this paper, we fill these gaps and first draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base KB and a default phi --> psi, does KB entail phi --> psi? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment), where we consider the general propositional case as well as natural syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). As we show, the more sophisticated semantics for conditional knowledge bases are plagued with intractability in all these fragments. We thus explore cases in which these semantics are tractable, and find that most of them enjoy this property on feedback-free Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. Furthermore, we generalize previous tractability results from Horn to q-Horn conditional knowledge bases, which allow for a limited use of disjunction. Our results complement and extend previous results, and contribute in refining the tractability/intractability frontier of default reasoning from conditional knowledge bases. They provide useful insight for developing efficient implementations. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： reasoning under uncertainty conditional knowledge bases default reasoning nonmonotonic inference computational complexity polynomial-time algorithms Horn knowledge bases and variants

来源：评论

学校读者我要写书评

暂无评论

Critical (P5, bull)-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期334卷 15-25页

作者： Huang, Shenwei Li, Jiawei Xia, Wen Nankai Univ Coll Comp Sci Tianjin 300071 Peoples R China Nankai Univ Tianjin Key Lab Network & Data Secur Technol Tianjin 300071 Peoples R China

Given two graphs H1 and H2, a graph is (H1, H2)-free if it contains no induced subgraph isomorphic to H1 or H2. Let Pt be the path on t vertices. A bull is the graph obtained from a triangle with two disjoint pendant edges. In this paper, we show that there are finitely many 5-vertex-critical (P5, bull)-free graphs.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Coloring Critical graphs Forbidden induced subgraphs Strong perfect graph theorem polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

polynomial algorithms FOR LP OVER A SUBRING OF THE ALGEBRAIC-INTEGERS WITH APPLICATIONS TO LP WITH CIRCULANT MATRICES

引用

MATHEMATICAL PROGRAMMING 1992年第2期57卷 121-143页

作者： ADLER, I BELING, PA 1. Department of Industrial Engineering and Operations Research University of California 94720 Berkeley CA USA

We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, we prove the modified algorithm runs in time polynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. We then extend the Tardos scheme to our case, obtaining a running time which is independent of the objective and right-hand side data. As a consequence of these results, we are able to show that LPs with real circulant coefficient matrices can be solved in strongly polynomial time. Finally, we show how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.

关键词： LINEAR PROGRAMMING polynomial-time algorithms STRONGLY polynomial-time algorithms CIRCULANT MATRICES ALGEBRAIC NUMBERS

来源：评论

学校读者我要写书评

暂无评论

THE COMPLEXITY OF FINDING MINIMUM-LENGTH GENERATOR SEQUENCES

引用

THEORETICAL COMPUTER SCIENCE 1985年第2-3期36卷 265-289页

作者： JERRUM, MR Department of Computer Science University of Edinburgh Edinburgh EH9 2JZ Scotland United Kingdom

The computational complexity of the following problem is investigated: Given a permutation group specified as a set of generators, and a single target permutation which is a member of the group, what is the shortest expression for the target permutation in terms of the generators? The general problem is demonstrated to be PSppace -complete and, indeed,is shown to remain so even when the generator set is restricted to contain only two permutations. The restriction on generator set cardinality is the best possible, as the problem becomes soluble in polynomial time if the generator set cantains only one permutation. An interesting feature of this problem is that it does not fall under the headings of ‘two person games’ or ‘formal languages’ which cover the great majority of known PSpace -complete problems. Some restricted versions of the problem, in which the generator set is fixed rather than being part of the problem instance, are also investigated and shown to be computationally tractable. One result of this kind is that determining the most compact expression of a permutation in terms of ‘cyclicly adjacent transpositions’ can be achieved in polynomial time. Thus, from an initial arrangement of distinct objects on a circle, one can quickly compute the smallest number of interchanges of adjacent objects required to realise any other arrangement. Surprisingly, this problem appears substantially more difficult to solve than the related one (for which a solution has been known for some time) in which the objects are arranged on a line segment.

关键词： Computational complexity permutation groups polynomial-time algorithms PSpace -completeness

来源：评论

学校读者我要写书评

暂无评论

Finding minimal siphons in general Petri nets

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1996年第11期E79A卷 1817-1824页

作者： Tanimoto, S Yamauchi, M Watanabe, T Department of Circuits and Systems Faculty of Engineering Hiroshima University Higashi-Hiroshima-shi 739 Japan

A siphon (or alternatively a structural deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal class of mutually disjoint minimal siphons of a general Petri net is proposed.

关键词： general Petri nets minimal siphons polynomial-time algorithms strongly connectedness NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration models and algorithms for stateful interactive processes

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1999年第3期25卷 401-415页

作者： Varvarigou, TA Anagnostou, ME Ahuja, SR Natl Tech Univ Athens Dept Elect Engn & Comp Sci GR-15773 Athens Greece AT&T Bell Labs Lucent Technol Murray Hill NJ 07974 USA

In this paper, we present new results in the area of reconfiguration of stateful interactive processes in the presence of faults. More precisely, we consider a set of servers/processes that have the same functionality, i.e., are able to perform the same tasks and provide the same set of services to their clients. In the case when several of them turn out to be faulty, we want to reconfigure the system so that the clients of the faulty servers/processes are served by some other, fault-free, servers of the system in a way that is transparent to all the system clients. We propose a new method for reconfiguring in the presence of faults: compensation paths. Compensation paths are an efficient way of shifting spare resources from where they are available to where they are needed. We also present optimal and suboptimal simple reconfiguration algorithms of low polynomial time complexity O(nmlog(n(2)/m)) for the optimal and O(m) for the suboptimal algorithms, where M is the number of processes and m is the number of primary-backup relationships. The optimal algorithms compute the way to reconfigure the system whenever the reconfiguration is possible. The suboptimal algorithms may sometimes fail to reconfigure the system, although reconfiguration would be possible by using the optimal centralized algorithms. However, suboptimal algorithms have other competitive advantages over the centralized optimal algorithms with regard to time complexity and communication overhead.

关键词： reconfiguration of stateful processes compensation paths polynomial-time algorithms optimal centralized algorithms suboptimal distributed and hybrid algorithms

来源：评论

学校读者我要写书评

暂无评论

Computation of the Highest Coefficients of Weighted Ehrhart Quasi-polynomials of Rational Polyhedra

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2012年第4期12卷 435-469页

作者： Baldoni, V. Berline, N. De Loera, J. A. Koeppe, M. Vergne, M. Univ Calif Davis Dept Math Davis CA 95616 USA Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy Ecole Polytech Ctr Math Laurent Schwartz F-91128 Palaiseau France Inst Math Jussieu Theorie Grp F-75251 Paris 05 France

This article concerns the computational problem of counting the lattice points inside convex polytopes, when each point must be counted with a weight associated to it. We describe an efficient algorithm for computing the highest degree coefficients of the weighted Ehrhart quasi-polynomial for a rational simple polytope in varying dimension, when the weights of the lattice points are given by a polynomial function h. Our technique is based on a refinement of an algorithm of A. Barvinok in the unweighted case (i.e., ha parts per thousand 1). In contrast to Barvinok's method, our method is local, obtains an approximation on the level of generating functions, handles the general weighted case, and provides the coefficients in closed form as step polynomials of the dilation. To demonstrate the practicality of our approach, we report on computational experiments which show that even our simple implementation can compete with state-of-the-art software.

关键词： Ehrhart functions Exponential sums and integrals Intermediate sums polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Complexity of single machine scheduling subject to nonnegative inventory constraints

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期207卷 605-619页

作者： Briskorn, Dirk Choi, Byung-Cheon Lee, Kangbok Leung, Joseph Pinedo, Michael Univ Cologne Wirtschafts & Sozialwissensch Fak D-50923 Cologne Germany Chungnam Natl Univ Dept Business Adm Taejon 305704 South Korea NYU Stern Sch Business New York NY 10012 USA New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

This paper focuses on single machine scheduling subject to inventory constraints. Jobs either add items to an inventory or remove items from that inventory. Jobs that have to remove items cannot be processed if the required number of items is not available. We consider scheduling problems on a single machine with the minimization of the total weighted completion time, the maximum lateness, and the number of tardy jobs, respectively, as objective and determine their computational complexity. Since the general versions of our problems turn out to be strongly NP-hard, we consider special cases by assuming that different jobs have certain parameter values in common. We determine the computational complexity for all special cases when the objective is either to minimize total completion time or to minimize maximum lateness and for several special cases when the objective is either to minimize total weighted completion time or to minimize the number of tardy jobs. (C) 2010 Elsevier BM. All rights reserved.

关键词： Machine scheduling Inventory constraints Computational complexity Strong NP-hardness polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Extracting minimal siphon-traps of Petri nets and its application to computing nonnegative integer-invariants

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2002年第11期E85A卷 2436-2446页

作者： Taoka, S Takano, K Watanabe, T Hiroshima Univ Grad Sch Engn Higashihiroshima 7398527 Japan Hitachi Software Engn Co Yokohama Kanagawa Japan

A siphon-trap of a Petri net N is defined as a place set S with S-. = S-., where S-.={u\ N has an edge from u to a vertex of S} and S-. = {v\ N has an edge from a vertex of S to v}. A minimal siphon-trap is a siphon-trap such that any proper subset is not a siphon-trap. The following polynomial-time algorithms are proposed: 1. FDST for finding, if any, a minimal siphon-trap or even a maximal class of mutually disjoint minimal siphon-traps of a given Petri net;2. FDSTi that repeats FDST i times in order to extract more minimal siphon-traps than FDST. 3. STFM-T (STFM-T-i, respectively) which is a combination of the Fourier-Motzkin method and FDST (FDSTi) and which has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.

关键词： Petri nets minimal siphon-traps Fourier-Motzkin method invariant computation polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：