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

22nd International Conference on the Principles and Practice of Constraint Programming (CP)

作者： Manlove, David F. McBride, Iain Trimble, James Univ Glasgow Sch Comp Sci Sir Alwyn Williams Bldg Glasgow G12 8QQ Lanark Scotland

ISBN: (纸本)9783319449524

The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that a stable matching need not exist, so we consider min bp hrc, the problem of finding a matching that admits the minimum number of blocking pairs (i.e., is "as stable as possible"). We show that this problem is NP-hard and difficult to approximate even in the highly restricted case that each couple finds only one hospital pair acceptable. However if we further assume that the preference list of each single resident and hospital is of length at most 2, we give a polynomial-time algorithm for this case. We then present the first Integer Programming (IP) and Constraint Programming (CP) models for min bp hrc. Finally, we discuss an empirical evaluation of these models applied to randomly-generated instances of min bp hrc. We find that on average, the CP model is about 1.15 times faster than the IP model, and when presolving is applied to the CP model, it is on average 8.14 times faster. We further observe that the number of blocking pairs admitted by a solution is very small, i.e., usually at most 1, and never more than 2, for the (28,000) instances considered.

关键词： Most-stable matching Blocking pair polynomial-time algorithm NP-hardness Integer programming model Constraint programming model Empirical evaluation

来源：评论

学校读者我要写书评

暂无评论

Payment Scheduling in the Interval Debt Model 48th

Payment Scheduling in the Interval Debt Model

引用

48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Friedetzky, Tom Kutner, David C. Mertzios, George B. Stewart, Iain A. Trehan, Amitabh Univ Durham Dept Comp Sci Durham England

ISBN: (纸本)9783031231001;9783031231018

The networks-based study of financial systems has received considerable attention in recent years, but seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view, and we introduce the Interval Debt Model (IDM) and some scheduling problems based on it, namely: BANKRUPTCY MINIMIZATION/MAXIMIZATION, in which the aim is to produce a schedule with at most/at least k bankruptcies;PERFECT SCHEDULING, the special case of the minimization variant where k = 0;and BAILOUT MINIMIZATION, in which a financial authority must allocate a smallest possible bailout package to enable a perfect schedule. In this paper we investigate the complexity landscape of the various variants of these problems. We show that each of them is NP-complete, in many cases even on very restrictive input instances. On the positive side, we provide for PERFECT SCHEDULING a polynomial-time algorithm on (rooted) out-trees. In wide contrast, we prove that this problem is NP-complete on directed acyclic graphs (DAGs), as well as on instances with a constant number of nodes (and hence also constant treewidth). When the problem definition is relaxed to allow fractional payments, we show by a linear programming argument that BAILOUT MINIMIZATION can be solved in polynomial time.

关键词： Temporal graph Financial network Payment scheduling NP-complete polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Co-Bipartite Neighborhood Edge Elimination Orderings

引用

Electronic Notes in Discrete Mathematics 2017年 61卷 655-661页

作者： Jiamjitrak, Wanchote van Leeuwen, Erik Jan Dept. Computer Science Aalto University Espoo Finland Dept. Inform. Comput. Sciences Utrecht University Utrecht Netherlands

In SODA 2001, Raghavan and Spinrad introduced robust algorithms as a way to solve hard combinatorial graph problems in polynomial time even when the input graph falls slightly outside a graph class for which a polynomial-time algorithm exists. As a leading example, the MAXIMUM CLIQUE problem on unit disk graphs (intersection graphs of unit disks in the plane) was shown to have a robust, polynomial-time algorithm by proving that such graphs admit a co-bipartite neighborhood edge elimination ordering (CNEEO). This begs the question whether other graph classes also admit a CNEEO. In this paper, we answer this question positively, and identify many graph classes that admit a CNEEO, including several graph classes for which no polynomial-time recognition algorithm exists (unless P=NP). As a consequence, we obtain robust, polynomial-time algorithms for MAXIMUM CLIQUE on all identified graph classes. We also prove some negative results, and identify graph classes that do not admit a CNEEO. This implies an almost-perfect dichotomy for subclasses of perfect graphs. © 2017 Elsevier B.V.

关键词： edge ordering graph classes maximum clique polynomial-time algorithm robust algorithm

来源：评论

学校读者我要写书评

暂无评论

How to Play Unique Games against a Semi-Random Adversary Study of Semi-Random Models of Unique Games

How to Play Unique Games against a Semi-Random Adversary Stu...

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Kolla, Alexandra Makarychev, Konstantin Makarychev, Yury Microsoft Research United States IBM Research United States TTIC United States

ISBN: (纸本)9780769545714

In this paper, we study the average case complexity of the Unique Games problem. We propose a semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Unique Games, then she chooses an epsilon-fraction of all edges, and finally replaces ("corrupts") the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1 - epsilon)-satisfiable instance, so then the problem is as hard as in the worst case. We show however that we can find a solution satisfying a (1 - delta) fraction of all constraints in polynomial-time if at least one step is random (we require that the average degree of the graph is (Omega) over tilde (log k)). Our result holds only for epsilon less than some absolute constant. We prove that if epsilon >= 1/2, then the problem is hard in one of the models, that is, no polynomial-time algorithm can distinguish between the following two cases: (i) the instance is a (1 - epsilon)-satisfiable semi-random instance and (ii) the instance is at most delta-satisfiable (for every delta > 0);the result assumes the 2-to-2 conjecture. Finally, we study semi-random instances of Unique Games that are at most (1 - epsilon)-satisfiable. We present an algorithm that distinguishes between the case when the instance is a semi-random instance and the case when the instance is an (arbitrary) (1 -delta)-satisfiable instances if epsilon > c delta (for some absolute constant c).

关键词： Approximation algorithms Approximation methods Games Mathematical model polynomials Vectors computability computational complexity game theory graph theory graph theory polynomial-time algorithm semirandom adversary semirandom unique game models

来源：评论

学校读者我要写书评

暂无评论

Optimal Power Control in Two-Tier Networks at Low-SNR Regime 23

Optimal Power Control in Two-Tier Networks at Low-SNR Regime

引用

23nd Signal Processing and Communications Applications Conference (SIU)

作者： Demir, Uygar Toker, Cenk Inaltekin, Hazer Hacettepe Univ Elekt & Elekt Muhendisligi Bolumu Ankara Turkey Antalya Uluslararasi Univ Elekt & Elekt Muhendisligi Bolumu Dosemealti Antalya Turkey

ISBN: (纸本)9781467373869

This paper considers optimum uplink power control policy that maximizes system capacity without any interference cancellation techniques for HetNets or cognitive-radio (CR) networks at low-SNR regime. System model has two-tier to cover cognitive-radio and heterogenous networks structures. Tier 2 users cause interference on tier 1 user under spectrum sharing paradigm. In proposed scenario, this interference power on tier 1 user is limited at a certain level. The objective function of power optimization problem is changed with an upper bound function to find optimum power control policy under individual peak power constraint at Tier2s and total interference constraint at Tierl for uplink case at low-SNR regime. To this end, two optimal solutions, one of which is algoritmic and the other is analytical, have found from two different upper bound approximations. By exploiting analytical solution, a fast and low-complex algorithm is derived. At the end of paper, these two approximations and DC programming algorithm which is well-studied and given well-approximated lower bound have been compared with each other.

关键词： HetNets cognitive-radio networks power control low-SNR regime interference constraint polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Circulant graphs: Recognizing and isomorphism testing in polynomial time

引用

St. Petersburg Mathematical Journal 2004年第6期15卷 813-835页

作者： Evdokimov, S.A. Ponomarenko, I.N. St. Petersburg Institute for Informatics and Automation RAS St. Petersburg Russian Federation St. Petersburg Branch Steklov Mathematical Institute Russian Academy of Sciences St. Petersburg 191023 Fontanka 27 Russian Federation

An algorithm is constructed for recognizing the circulant graphs and finding a canonical labeling for them in polynomial time. This algorithm also yields a cycle base of an arbitrary solvable permutation group. The consistency of the algorithm is based on a new result on the structure of Schur rings over a finite cyclic group. © 2004 American Mathematical Society.

关键词： Cayley graph polynomial-time algorithm Regular cycle automorphism group

来源：评论

学校读者我要写书评

暂无评论

Characterizing Star-PCGs 24th

Characterizing Star-PCGs

引用

24th International Computing and Combinatorics Conference (COCOON)

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Sichuan Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto Japan

ISBN: (纸本)9783319947761;9783319947754

A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T, w, d(min), d(max)) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals d(min) <= d(max) such that G has an edge between two vertices u, v is an element of V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [d(min), d(max)]. The tree T is also called a witness tree of the PCG G. The problem of testing if a given graph is a PCG is not known to be NP -hard yet. To obtain a complete characterization of PCGs is a wide open problem in computational biology and graph theory. In the literature, most witness trees admitted by known PCGs are stars and caterpillars. In this paper, we give a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs.

关键词： Pairwise compatibility graph polynomial-time algorithm Graph algorithm Graph theory

来源：评论

学校读者我要写书评

暂无评论

A stable and Pareto efficient update of matching in school choice

引用

ECONOMICS LETTERS 2016年 143卷 111-113页

作者： Okumura, Yasunori TUMSAT Tokyo Japan

We consider a situation where a student-school matching has already been temporarily decided, but unexpectedly the quotas of some schools are increased and/or some new schools enter. Furthermore, the school priority orders are allowed to be weak. We provide a polynomial-time algorithm to derive a student optimal stable matching under the profile of increased quotas that Pareto dominates the stable matching under that of initial quotas. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Matching Market design School choice polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

LOCATION OF ALTERNATIVE-FUEL REFUELING STATIONS ON TRANSPORTATION NETWORKS CONSIDERING VEHICLE DEVIATIONS AND GREENHOUSE GAS EMISSIONS

LOCATION OF ALTERNATIVE-FUEL REFUELING STATIONS ON TRANSPORT...

引用

作者： Kweon, Sang Jin PennState University Libraries

学位级别：Doctor of Philosophy

Burning conventional fossil fuels including gasoline and diesel mainly results in over 90% of greenhouse gas emissions from transportation. To reduce these emissions from the ground transportation sector, the use of alternative-fuel vehicles is being spotlighted. As a result, refueling station location problems for alternative-fuel vehicles have received attention as well. These refueling station location problems can be classified into two types depending on the set of candidate sites: when a preliminary (finite) set of candidate sites is given, this problem is called discrete; when the stations can be located anywhere along the network, the problem is called continuous. This dissertation considers one discrete and two continuous location problems for alternative-fuel refueling stations on transportation networks. First, the discrete location problem is addressed with two conflicting objectives of maximizing the total vehicle-miles traveled per time unit covered by the stations and minimizing the capital cost for constructing the refueling infrastructure. Two versions of bi-criteria binary linear programming models are proposed and validated with an application to the Pennsylvania Turnpike System regarding the location of liquefied natural gas refueling stations on existing service plazas. Next, assuming that a vehicle cannot deviate from the preplanned path, the continuous location problem for a single refueling station is addressed on a tree network with the objective of maximizing the traffic flow (in round trips per time unit) covered by the station. Two reduction properties regarding the problem size and some optimality conditions are derived. Then, an exact polynomial algorithm is developed to determine the set of optimal locations for the refueling station. Lastly, the continuous location problem introduced above is extended to a version where a given portion of drivers are willing to deviate to be able to refuel if the station is not located along their pre

关键词： Alternative-fuel vehicles bi-criteria optimization GHG emission reduction Facility location Refueling station Tree network Deviation-flow polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Community Detection in Censored Hypergraph

Community Detection in Censored Hypergraph

引用

作者： Zhao, Bin North Dakota State University

学位级别：Ph.D., Doctor of Philosophy

Network, or graph, represent relationships between entities in various applications, such as social networks, biological systems, and communication networks. A common feature in network data is the presence of community structures, where groups of nodes exhibit higher connectivity within themselves than with other groups. Identifying these community structures, a task known as community detection, is essential for gaining valuable insights in diverse applications, including uncovering hidden relationships in social networks, detecting functional modules in biological systems, and identifying vulnerabilities in communication networks. However, real-world network data may have missing values, significantly impacting the network’s structural properties. Existing community detection methods primarily focus on networks without missing values, leaving a gap in the analysis of censored networks. This study addresses the community detection problem in censored m-uniform hypergraphs. Firstly, utilizing an information-theoretic approach, we obtain a threshold that enables the exact recovery of the community structure. Then, we proposed a two-stage polynomial-time algorithm, which encompasses a spectral algorithm complemented by a refinement step, aiming to achieve exact recovery. Moreover, we introduce a semi-definite relaxation algorithm, studying its operational performance as a standalone community detection algorithm, without the integration of a refinement step. Lastly, in consideration of the effect of imputation methods on censored hypergraphs, we propose several methods grounded in network properties. We subsequently employ simulation to assess the performance of these methods. Finally, we apply the proposed algorithm to real-world data, showcasing its practical utility in various settings.

关键词： Communication networks Social networks Hypergraphs polynomial-time algorithm Censored networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：