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

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Hörsch, Florian Imolay, András Mizutani, Ryuhei Oki, Taihei Schwarcz, Tamás Algorithms and Complexity Group CISPA Saarbrücken Germany MTA-ELTE Matroid Optimization Research Group Department of Operations Research ELTE Eötvös Loránd University Budapest Hungary Department of Mathematical Informatics Graduate School of Information Science and Technology The University of Tokyo Japan

ISBN: (纸本)9783959773225

Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a matroid is not difficult, it turns out that the complexity of finding a non-zero common basis depends on the group. Namely, we show that the problem is hard for a fixed group if it contains an element of order two, otherwise it is polynomially solvable. As a generalization of both zero and non-zero constraints, we further study F-avoiding constraints where we seek a basis or common basis whose label is not in a given set F of forbidden labels. Using algebraic techniques, we give a randomized algorithm for finding an F-avoiding common basis of two matroids represented over the same field for finite groups given as operation tables. The study of F-avoiding bases with groups given as oracles leads to a conjecture stating that whenever an F-avoiding basis exists, an F-avoiding basis can be obtained from an arbitrary basis by exchanging at most |F| elements. We prove the conjecture for the special cases when |F| ≤ 2 or the group is ordered. By relying on structural observations on matroids representable over fixed, finite fields, we verify a relaxed version of the conjecture for these matroids. As a consequence, we obtain a polynomial-time algorithm in these special cases for finding an F-avoiding basis when |F| is fixed. © Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Resolving Infeasibility of Linear Systems: A Parameterized Approach

arXiv

引用

arXiv 2022年

作者： Bérczi, Kristóf Göke, Alexander Mendoza-Cadena, Lydia Mirabel Mnich, Matthias 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 Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany MTA-ELTE Momentum Matroid Optimization Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary

Deciding feasibility of large systems of linear equations and inequalities is one of the most fundamental algorithmic tasks. However, due to data inaccuracies or modeling errors, in practical applications one often faces linear systems that are infeasible. Extensive theoretical and practical methods have been proposed for post-infeasibility analysis of linear systems. This generally amounts to detecting a feasibility blocker of small size k, which is a set of equations and inequalities whose removal or perturbation from the large system of size m yields a feasible system. This motivates a parameterized approach towards post-infeasibility analysis, where we aim to find a feasibility blocker of size at most k in fixed-parameter time f(k) · mO(1). We establish parameterized intractability (W[1]- and NP-hardness) results already in very restricted settings for different choices of the parameters maximum size of a deletion set, number of positive/negative right-hand sides, treewidth, pathwidth and treedepth. Additionally, we rule out a polynomial compression for MinFB parameterized by the size of a deletion set and the number of negative right-hand sides. Furthermore, we develop fixed-parameter algorithms parameterized by various combinations of these parameters when every row of the system corresponds to a difference constraint. Our algorithms capture the case of Directed Feedback Arc Set, a fundamental parameterized problem whose fixed-parameter tractability was shown by Chen et al. (STOC 2008). Copyright © 2022, The Authors. All rights reserved.

关键词： Linear systems

来源：评论

学校读者我要写书评

暂无评论

2.5-connectivity: Unique components, critical graphs, and applications

arXiv

引用

arXiv 2020年

作者： Heinrich, Irene Heller, Till Schmidt, Eva Streicher, Manuel Algorithms and Complexity Group Department of Computer Science Technische Universität Kaiserslautern Kaiserslautern Germany Department of Optimization Fraunhofer ITWM Kaiserslautern Germany Optimization Research Group Department of Mathematics Technische Universität Kaiserslautern Kaiserslautern Germany

If a 2-connected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5-connected. We prove that every 2-connected graph has a canonical decomposition into 2.5-connected components. These components are arranged in a treestructure. We also discuss the connection between 2.5-connected components and triconnected components and use this to present a linear time algorithm which computes the 2.5-connected components of a graph. We show that every critical 2.5-connected graph other than K4 can be obtained from critical 2.5-connected graphs of smaller order using simple graph operations. Furthermore, we demonstrate applications of 2.5-connected components in the context of cycle decompositions and cycle *** Codes 05C40, 05C45, 05C85, 05C75 Copyright © 2020, The Authors. All rights reserved.

关键词： Clustering algorithms

来源：评论

学校读者我要写书评

暂无评论

Neural networks in day-ahead electricity price forecasting: single vs. multiple outputs

arXiv

引用

arXiv 2020年

作者： Marcjasz, Grzegorz Lago, Jesus Weron, Rafal Department of Operations Research Wroclaw University of Science and Technology Wroclaw Poland Delft Center for Systems and Control Delft University of Technology Delft Netherlands Algorithms Modeling and Optimization Energyville Genk Belgium Mol Belgium

Recent advancements in the fields of artificial intelligence and machine learning methods resulted in a significant increase of their popularity in the literature, including electricity price forecasting. Said methods cover a very broad spectrum, from decision trees, through random forests to various artificial neural network models and hybrid approaches. In electricity price forecasting, neural networks are the most popular machine learning method as they provide a non-linear counterpart for well-tested linear regression models. Their application, however, is not straightforward, with multiple implementation factors to consider. One of such factors is the network’s structure. This paper provides a comprehensive comparison of two most common structures when using the deep neural networks – one that focuses on each hour of the day separately, and one that reflects the daily auction structure and models vectors of the prices. The results show a significant accuracy advantage of using the latter, confirmed on data from five distinct power exchanges. Copyright © 2020, The Authors. All rights reserved.

关键词： Risk management

来源：评论

学校读者我要写书评

暂无评论

Forecasting day-ahead electricity prices: A review of state-of-the-art algorithms, best practices and an open-access benchmark

arXiv

引用

arXiv 2020年

作者： Lago, Jesus Marcjasz, Grzegorz De Schutter, Bart Weron, Rafal Delft Center for Systems and Control Delft University of Technology Delft Netherlands Algorithms Modeling and Optimization Energyville Genk Belgium Mol Belgium Department of Operations Research and Business Intelligence Wroclaw University of Science and Technology Wroclaw Poland

While the field of electricity price forecasting has benefited from plenty of contributions in the last two decades, it arguably lacks a rigorous approach to evaluating new predictive algorithms. The latter are often compared using unique, not publicly available datasets and across too short and limited to one market test samples. The proposed new methods are rarely benchmarked against well established and well performing simpler models, the accuracy metrics are sometimes inadequate and testing the significance of differences in predictive performance is seldom conducted. Consequently, it is not clear which methods perform well nor what are the best practices when forecasting electricity prices. In this paper, we tackle these issues by comparing state-of-the-art statistical and deep learning methods across multiple years and markets, and by putting forward a set of best practices. In addition, we make available the considered datasets, forecasts of the state-of-the-art models, and a specifically designed python toolbox, so that new algorithms can be rigorously evaluated in future studies. Copyright © 2020, The Authors. All rights reserved.

关键词： Power markets

来源：评论

学校读者我要写书评

暂无评论

Enabling research through the SCIP optimization Suite 8.0

arXiv

引用

arXiv 2023年

作者： Bestuzheva, Ksenia Besançon, Mathieu Chen, Wei-Kun Chmiela, Antonia Donkiewicz, Tim van Doornmalen, Jasper Eifler, Leon Gaul, Oliver Gamrath, Gerald Gleixner, Ambros Gottwald, Leona Graczyk, Christoph Halbig, Katrin Hoen, Alexander Hojny, Christopher van der Hulst, Rolf Koch, Thorsten Lübbecke, Marco Maher, Stephen J. Matter, Frederic Mühmer, Erik Müller, Benjamin Pfetsch, Marc E. Rehfeldt, Daniel Schlein, Steffan Schlösser, Franziska Serrano, Felipe Shinano, Yuji Sofranac, Boro Turner, Mark Vigerske, Stefan Wegscheider, Fabian Wellner, Philipp Weninger, Dieter Witzig, Jakob Zuse Institute Berlin Department AIS2T Takustr. 7 Berlin14195 Germany ZIB-AIS2T Germany School of Mathematics and Statistics Beijing Institute of Technology Beijing100081 China RWTH Aachen University Lehrstuhl für Operations Research Kackertstr. 7 Aachen52072 Germany Eindhoven University of Technology Department of Mathematics and Computer Science Netherlands ZIB-AIS2T I2DAMO GmbH Englerallee 19 Berlin14195 Germany ZIB-AIS2T HTW Berlin Germany Friedrich-Alexander Universität Erlangen-Nürnberg Department of Data Science Cauerstr. 11 Erlangen91058 Germany University of Twente Department of Discrete Mathematics and Mathematical Programming P.O. Box 217 Enschede7500 AE Netherlands Technische Universität Berlin Software and Algorithms for Discrete Optimization Straße des 17. Juni 135 Berlin10623 Germany ZIB Department A2IM Takustr. 7 Berlin14195 Germany RWTH Aachen-Lehrstuhl für OR Germany University of Exeter College of Engineering Mathematics and Physical Sciences Exeter United Kingdom Technische Universität Darmstadt Fachbereich Mathematik Dolivostr. 15 Darmstadt64293 Germany TU Darmstadt Fachbereich Mathematik Germany ZIB-A2IM Germany TU Berlin Germany ZIB-A2IM Software and Algorithms for Discrete Optimization Institute of Mathematics TU Berlin Germany GAMS Software GmbH c/o ZIB-AIS2T Germany

The SCIP optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this paper is on the role of the SCIP optimization Suite in supporting research. SCIP's main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP's application as a research tool and as a platform for further developments. Further, the paper gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon *** Codes 90C05, 90C10, 90C11, 90C30, 90C90, 65Y05 Copyright © 2023, The Authors. All rights reserved.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

Article's Scientific Prestige: Measuring the impact of individual articles in the Web of Science

arXiv

引用

arXiv 2022年

作者： Chen, Ying Koch, Thorsten Zakiyeva, Nazgul Liu, Kailiang Xu, Zhitong Chen, Chun-Houh Nakano, Junji Honda, Keisuke Department of Mathematics National University of Singapore 2 Science Drive 2 Singapore117543 Singapore Risk Management Institute National University of Singapore 21 Heng Mui Keng Terrace 04-03 Singapore119613 Singapore Technische Universität Berlin Software and Algorithms for Discrete Optimization Straße des 17. Juni 135 Berlin10623 Germany Zuse Institute Berlin Applied Algorithmic Intelligence Methods Department Takustraße 7 Berlin14195 Germany Research Institute Chongqing Internet Institute Building 5B No. 16 South Huashan Road Chongqing Liang Jiang New Area Chongqing China Department of Statistics and Data Science National University of Singapore 6 Science Drive 2 Singapore117546 Singapore The Institute of Statistical Science Academia Sinica 128 Academia Road Nankang Taipei11529 Taiwan Department of Global Management Chuo University 742-1 Higashinakano Hachioji Tokyo192-0393 Japan Institute of Statistical Mathematics 10-3 Midoricho Tachikawa Tokyo190-0014 Japan

We performed a citation analysis on the Web of Science publications consisting of more than 63 million articles and 1.45 billion citations on 254 subjects from 1981 to 2020. We proposed the Article's Scientific Prestige (ASP) metric and compared this metric to number of citations (#Cit) and journal grade in measuring the scientific impact of individual articles in the large-scale hierarchical and multi-disciplined citation network. In contrast to #Cit, ASP, that is computed based on the eigenvector centrality, considers both direct and indirect citations, and provides steady-state evaluation cross different disciplines. We found that ASP and #Cit are not aligned for most articles, with a growing mismatch amongst the less cited articles. While both metrics are reliable for evaluating the prestige of articles such as Nobel Prize winning articles, ASP tends to provide more persuasive rankings than #Cit when the articles are not highly cited. The journal grade, that is eventually determined by a few highly cited articles, is unable to properly reect the scientific impact of individual articles. The number of references and coauthors are less relevant to scientiffc impact, but subjects do make a difference. Copyright © 2022, The Authors. All rights reserved.

关键词：

来源：评论

学校读者我要写书评

暂无评论

The SCIP optimization suite 8.0

arXiv

引用

arXiv 2021年

作者： Bestuzheva, Ksenia Besançon, Mathieu Chen, Wei-Kun Chmiela, Antonia Donkiewicz, Tim Van Doornmalen, Jasper Eifler, Leon Gaul, Oliver Gamrath, Gerald Gleixner, Ambros Gottwald, Leona Graczyk, Christoph Halbig, Katrin Hoen, Alexander Hojny, Christopher Van Der Hulst, Rolf Koch, Thorsten Lübbecke, Marco Maher, Stephen J. Matter, Frederic Mühmer, Erik Müller, Benjamin Pfetsch, Marc E. Rehfeldt, Daniel Schlein, Steffan Schlösser, Franziska Serrano, Felipe Shinano, Yuji Sofranac, Boro Turner, Mark Vigerske, Stefan Wegscheider, Fabian Wellner, Philipp Weninger, Dieter Witzig, Jakob Zuse Institute Berlin Department AIS2T Takustr. 7 Berlin14195 Germany School of Mathematics and Statistics Beijing Institute of Technology Beijing100081 China RWTH Aachen University Lehrstuhl für Operations Research Kackertstr. 7 Aachen52072 Germany Technische Universiteit Eindhoven Department of Mathematics and Computer Science P.O. Box 513 Eindhoven5600 MB Netherlands I2DAMO GmbH Englerallee 19 Berlin14195 Germany Friedrich-Alexander Universität Erlangen-Nürnberg Department of Data Science Cauerstr. 11 Erlangen91058 Germany University of Twente Department of Discrete Mathematics and Mathematical Programming P.O. Box 217 Enschede7500 AE Netherlands Technische Universität Berlin Software and Algorithms for Discrete Optimization Straße des 17. Juni 135 Berlin10623 Germany Zuse Institute Berlin Department A2IM Takustr. 7 Berlin14195 Germany University of Exeter College of Engineering Mathematics and Physical Sciences Exeter United Kingdom Technische Universität Darmstadt Fachbereich Mathematik Dolivostr. 15 Darmstadt64293 Germany Technische Universität Berlin Straße des 17. Juni 135 Berlin10623 Germany Software and Algorithms for Discrete Optimization Institute of Mathematics Technische Universität Berlin Straße des 17. Juni 135 Berlin10623 Germany GAMS Software GmbH C/o Zuse Institute Berlin Department AIS2T Takustr. 7 Berlin14195 Germany

The SCIP optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in *** Codes 90C05, 90C10, 90C11, 90C30, 90C90, 65Y05 Copyright © 2021, The Authors. All rights reserved.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

Sustainable Welding Process Selection Based on Weight Space Partitions

引用

Procedia CIRP 2016年 40卷 127-132页

作者： Gunther Sproesser Sebastian Schenker Andreas Pittner Ralf Borndörfer Michael Rethmeier Ya-Ju Chang Matthias Finkbeiner Chair of Safety of Joined Components Institute of Machine Tools and Factory Management Technische Universität Berlin Pascalstr. 8-9 10587 Berlin Germany Department of Mathematical Optimization Zuse Institute Berlin Takustr. 7 14195 Berlin Germany Chair of Combinatorial Optimization and Graph algorithms TU Berlin Straße des 17. Juni 136 10623 Berlin Germany Group of Welding Technology Department of Component Safety Federal Institute for Materials Research and Testing Unter den Eichen 87 12205 Berlin Germany Chair of Sustainable Engineering Department of Environmental Technology Technische Universität Berlin Straße des 17. Juni 135 10623 Berlin Germany

Selecting a welding process for a given application is crucial with respect to the sustainability of part manufacturing. Unfortunately, since welding processes are evaluated by a number of criteria, preferences for one or the other process can be contradictory. However, the prevalent procedure of weight assignment for each criterion is subjective and does not provide information about the entire solution space. From the perspective of a decision maker it is important to be able to assess the entire set of possible weightings and answer the question which welding process is optimal for which set of weights. This issue is investigated by means of a weight space partitioning approach. Two welding processes are considered with respect to three criteria that reflect their economic and environmental performance. In order to find the most sustainable welding process the underlying weight space partition is evaluated.

关键词： Welding process selection multi-criteria decision support LCA GMAW multi-attribute decision method welding costs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：