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

FINDING MAXIMUM EDGE-DISJOINT PAthS BETWEEN MULTIPLE TERMINALS

SIAM JOURNAL ON COMPUTING 2023年第5期52卷 1230-1268页

作者： Iwata, Satoru Yokoi, Yu Univ Tokyo Dept Math Informat Tokyo 1138656 Japan Hokkaido Univ Inst Chem React Design & Discovery Sapporo 0010021 Japan Tokyo Inst Technol Sch Comp Dept Math & Comp Sci Tokyo 1528550 Japan

Let G = (V, E) be a multigraph with a set T \subseteq V of terminals. A path in G is called a T-path if its ends are distinct vertices in T and no internal vertices belong to T. In 1978, Mader showed a characterization of the maximum number of edge-disjoint T-paths. In this paper, we provide a combinatorial, deterministic algorithm for finding the maximum number of edge-disjoint T-paths. the algorithm adopts an augmenting path approach. More specifically, we utilize a new concept of short augmenting walks in auxiliary labeled graphs to capture a possible augmentation of the number of edge-disjoint T-paths. To design a search procedure for a short augmenting walk, we introduce blossoms analogously to the matching algorithm of Edmonds [Canad. J. Math., 17, 1965, pp. 449--467]. When the search procedure terminates without finding a short augmenting walk, the algorithm provides a certificate for the optimality of the current edge-disjoint T-paths. From this certificate, one can obtain the Edmonds-Gallai type decomposition introduced by SeboH \ and SzegoH \ [Proceedings of the Tenth international conference on integer programming and combinatorial optimization, LNCS 3064, Springer, Berlin, 2004, pp. 256--270]. the algorithm runs in O(1E12) time, which is much faster than the best known deterministic algorithm based on a reduction to linear matroid parity. We also present a strongly polynomial algorithm for the maximum integer free multiflow problem, which asks for a nonnegative integer combination of T-paths maximizing the sum of the coefficients subject to capacity constraints on the edges.

关键词： combinatorial optimization blossom algorithm multicommodity flow

来源：评论

学校读者我要写书评

暂无评论

Separating k-MEDIAN from the Supplier Version 25th

Separating k-MEDIAN from the Supplier Version

引用

25th international conference on integer programming and combinatorial optimization (IPCO)

作者： Anand, Aditya Lee, Euiwoong Univ Michigan Ann Arbor MI 48109 USA

ISBN: (纸本)9783031598340;9783031598357

Given a metric space (V, d) along with an integer k, the k-Median problem asks to open k centers C subset of V to minimize Sigma(v is an element of V) d(v, C), where d(v, C) := mi(n is an element of C) d(v, c). While the best-known approximation ratio 2.613 holds for the more general supplier version where an additional set F subset of V is given with the restriction C subset of F, the best known hardness for these two versions are 1+1/e approximate to 1.36 and 1+2/e approximate to 1.73 respectively, using the same reduction from Maximum k-Coverage. We prove the following two results separating them. 1. We give a 1.546-parameterized approximation algorithm that runs in time f(k)n(O(1)). Since 1+ 2/e is proved to be the optimal approximation ratio for the supplier version in the parameterized setting, this result separates the original k-Median from the supplier version. 2. We prove a 1.416-hardness for polynomial-time algorithms assuming the Unique Games Conjecture. this is achieved via a new finegrained hardness of Maximum k-Coverage for small set sizes. Our upper bound and lower bound are derived from almost the same expression, with the only difference coming from the well-known separation between the powers of LP and SDP on (hypergraph) vertex cover.

关键词： Approximation algorithms Clustering Parameterized approximation optimization Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

Adaptivity Gaps in Two-Sided Assortment optimization 25th

Adaptivity Gaps in Two-Sided Assortment Optimization

引用

25th international conference on integer programming and combinatorial optimization (IPCO)

作者： El Housni, Omar Torrico, Alfredo Hennebelle, Ulyssee Cornell Univ Cornell Tech New York NY 10021 USA Cornell Univ CDSES Ithaca NY USA Ecole Polytech Palaiseau France

ISBN: (纸本)9783031598340;9783031598357

We study a two-sided assortment optimization framework to address the challenge of choice congestion faced by matching platforms. the goal is to decide the assortments to offer to agents in order to maximize the expected number of matches. We identify several classes of policies that the platforms can use in their design. Our main goal is to measure the value that one class of policies have over another one. For this, we define the adaptivity gap as the worst-case ratio between the optimal value achieved by two different policy classes. First, we show that the adaptivity gap between the class of policies that statically show assortments to one-side first and the class of policies that adaptively show assortments to one-side first is exactly 1 - 1/e. Second, we show that the adaptivity gap between the latter class of policies and the fully adaptive class of policies that show assortments to agents one by one is exactly 1/2. Finally, we observe that the worst policies are those who simultaneously show assortments to all the agents, in fact, we show that the adaptivity gap with respect to one-sided policies can be arbitrarily small. these results showcase the benefit of each class of policies and, in particular, demonstrate that the optimal value of the best class of adaptive policies is a constant multiplicative factor away from those of one-sided policies.

关键词： Matching markets Assortment optimization Adaptivity gap

来源：评论

学校读者我要写书评

暂无评论

High-Dimensional State Estimation Using a combinatorial Approach: Application to Finance 10

High-Dimensional State Estimation Using a Combinatorial Appr...

引用

10th international conference on Control, Decision and Information Technologies (CoDIT)

作者： Bellina, Jeremy Georges, Didier Girerd-Potin, Isabelle Univ Grenoble Alpes CERAG Grenoble INP F-38000 Grenoble France Univ Grenoble Alpes GIPSA Lab Grenoble INP CNRS F-38000 Grenoble France

ISBN: (纸本)9798350373981;9798350373974

this paper focuses on the state estimation of a specific class of state-intermittent dynamical systems evolving in a high-dimensional state-space. As the dimension is large, a classical estimator such as a Kalman filter would require a large observation horizon to converge. To overcome this limitation, a mixed-integer formulation is proposed and solved by using a Genetic Algorithm. We also propose a reduced-order state estimation as a variant of this approach under some mild assumptions, which reduces the observation window size even more. In particular, we show, through a case study in finance, that the reduced model and its associated genetic algorithm can reduce the observation window size needed by almost 75% and that this method is faster than the non-reduced mixed integer optimization problem. We also show that the reduced-order state estimation approach can be used to discover a mutual fund portfolio composition at each date of a given period.

关键词： Mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

A First Order Method for Linear programming Parameterized by Circuit Imbalance 25th

A First Order Method for Linear Programming Parameterized by...

引用

25th international conference on integer programming and combinatorial optimization (IPCO)

作者： Cole, Richard Hertrich, Christoph Tao, Yixin Vegh, Laszlo A. NYU Courant Inst New York NY USA Univ Libre Bruxelles Brussels Belgium Shanghai Univ Finance & Econ Minist Educ Key Lab Interdisciplinary Res Computat & Econ Shanghai Peoples R China London Sch Econ London England Corvinus Univ Corvinus Inst Adv Studies Budapest Hungary

ISBN: (纸本)9783031598340;9783031598357

Various first order approaches have been proposed in the literature to solve Linear programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs. From a theoretical perspective, linear convergence rates have been established for first order LP algorithms, despite the fact that the underlying formulations are not strongly convex. However, the convergence rate typically depends on the Hoffman constant of a large matrix that contains the constraint matrix, as well as the right hand side, cost, and capacity vectors. We introduce a first order approach for LP optimization with a convergence rate depending polynomially on the circuit imbalance measure, which is a geometric parameter of the constraint matrix, and depending logarithmically on the right hand side, capacity, and cost vectors. this provides much stronger convergence guarantees. For example, if the constraint matrix is totally unimodular, we obtain polynomial-time algorithms, whereas the convergence guarantees for approaches based on primal-dual formulations may have arbitrarily slow convergence rates for this class. Our approach is based on a fast gradient method due to Necoara, Nesterov, and Glineur (Math. Prog. 2019);this algorithm is called repeatedly in a framework that gradually fixes variables to the boundary. this technique is based on a new approximate version of Tardos's method, that was used to obtain a strongly polynomial algorithm for combinatorial LPs (Oper. Res. 1986).

关键词： Linear programming First Order Methods Hoffman Proximity Circuit Imbalances

来源：评论

学校读者我要写书评

暂无评论

Exploiting the Polyhedral Geometry of Stochastic Linear Bilevel programming 24th

Exploiting the Polyhedral Geometry of Stochastic Linear Bile...

引用

24th international conference on integer programming and combinatorial optimization (IPCO)

作者： Munoz, Gonzalo Salas, David Svensson, Anton Univ OHiggins Inst Ciencias Ingenierfa Rancagua Chile

ISBN: (纸本)9783031327254;9783031327261

We study linear bilevel programming problems whose lower-level objective is given by a random cost vector with known distribution. We consider the case where this distribution is nonatomic, allowing to pose the problem of the leader using vertex-supported beliefs in the sense of [29]. We prove that, under suitable assumptions, this formulation turns out to be piecewise affine over the so-called chamber complex of the feasible set of the high point relaxation. We propose two algorithmic approaches to solve general problems enjoying this last property. the first one is based on enumerating the vertices of the chamber complex. the second one is a Monte-Carlo approximation scheme based on the fact that randomly drawn points of the domain lie, with probability 1, in the interior of full-dimensional chambers, where the problem (restricted to this chamber) can be reduced to a linear program.

关键词： Bilevel programming Bayesian Approach Chamber complex Enumeration algorithm Monte-Carlo algorithm

来源：评论

学校读者我要写书评

暂无评论

8th international Symposium on combinatorial optimization, ISCO 2024

8th International Symposium on Combinatorial Optimization, I...

引用

8th international Symposium on combinatorial optimization, ISCO 2024

ISBN: (纸本)9783031609237

the proceedings contain 30 papers. the special focus in this conference is on combinatorial optimization. the topics include: Quadratically Constrained Reformulation, Strong Semidefinite programming Bounds, and Algorithms for the Chordless Cycle Problem;a Family of Spanning-Tree Formulations for the Maximum Cut Problem;optimal Cycle Selections: An Experimental Assessment of integer programming Formulations;1-Persistency of the Clique Relaxation of the Stable Set Polytope;alternating Direction Method and Deep Learning for Discrete Control with Storage;branch and Cut for Partitioning a Graph into a Cycle of Clusters;computing the Edge Expansion of a Graph Using Semidefinite programming;minimizing External Vertices in Hypergraph Orientations;open-Separating Dominating Codes in Graphs;on the Complexity of the Minimum Chromatic Violation Problem;crystal Trees;Reducing Treewidth for SAT-Related Problems Using Simple Liftings;total Matching and Subdeterminants;a New Structural Parameter on Single Machine Scheduling with Release Dates and Deadlines;fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs;sequencing Stochastic Jobs with a Single Sample;the thief Orienteering Problem on Series-Parallel Graphs;approximation Algorithm for Job Scheduling with Reconfigurable Resources;network Design on Undirected Series-Parallel Graphs;online Graph Coloring with Predictions;neuron Pairs in Binarized Neural Networks Robustness Verification via integer Linear programming;optimal Counterfactual Explanations for k-Nearest Neighbors Using Mathematical optimization and Constraint programming;surrogate Constraints for Synchronized Energy Production/Consumption;a Robust Two-Stage Model for the Urban Air Mobility Flight Scheduling Problem;optimal Charging Station Location in a Linear Cycle Path with Deviations;an Efficient Timing Algorithm for Drivers with Rest Periods;fair Energy Allocation for Collective Self-consumption;day-Ahead Lot-Sizing Un

关键词：

来源：评论

学校读者我要写书评

暂无评论

Research on Ship Crew Scheduling Algorithm Based on Improved Grey Wolf optimization 4

Research on Ship Crew Scheduling Algorithm Based on Improved...

引用

4th IEEE international conference on Information Technology, Big Data and Artificial Intelligence, ICIBA 2024

作者： Tang, Lin Ying, Wenwei Huang, Meng Zou, Yu Unit 91977 of the Pla Beijing China

ISBN: (纸本)9798350363586

Crew scheduling in civilian ships is a combinatorial optimization problem with various constraints. Traditional methods struggle with large-scale scheduling, while classic algorithms often fail to balance performance and practicality. this paper presents an Improved Grey Wolf optimization (IGWO) algorithm. We establish a mixed-integer programming model that considers hard and soft constraints to maximize crew-position matching. the IGWO algorithm enhances the standard Grey Wolf optimization (GWO) framework by integrating strategies like heuristic initialization, adaptive encirclement search, elite leader selection, and constraint violation repair. Simulation on random and real-world datasets show that IGWO outperforms manual methods, rule-based heuristics, and the standard GWO algorithm in objective function value, constraint satisfaction, and employee satisfaction. this research advances heuristic optimization in combinatorial problems. © 2024 IEEE.

关键词： Scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

Backward Dynamic programming Approach to Solve the Unit Commitment Problem Based on a Day Load Curve 9th

Backward Dynamic Programming Approach to Solve the Unit Comm...

引用

9th international conference on Advances in Energy Research, ICAER 2023

作者： Sahu, Dibya Ranjan Mohanty, Sanjeeb Department of Electrical Engineering National Institute of Technology Odisha Sundergarh Rourkela India

ISBN: (纸本)9789819754144

Unit commitment is generally used to schedule the units so as to minimize the cost of the production for the total system across the scheduled time horizon under generator operational constraints. the unit commitment problem is non-linear and a mixed-integer type combinatorial optimization problem. We can obtain the global optimal solution by complete listing which cannot be possible for large power systems due to its requirements for excessive computational time. Unit commitment presents a methodology to reduce cost and improve the system reliability. Unit commitment is a dynamic process, and power production planning changes as per loads and topologies of the network. the problem is solved by backward dynamic programming approach which solves the dynamic problem in 12 stages. this paper deals with a unit commitment problem that is solved using backward dynamic programming without time constraints, and outcomes show minimum cumulative total cost for operating 4 units in 12 stages for a 24-h horizon based on a load curve of a day. © the Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.

关键词： integer linear programming

来源：评论

学校读者我要写书评

暂无评论

From Approximate to Exact integer programming 1

引用

24th international conference on integer programming and combinatorial optimization (IPCO)

作者： Dadush, Daniel Eisenbrand, Friedrich Rothvoss, thomas CWI Amsterdam Netherlands Ecole Polytech Fed Lausanne Lausanne Switzerland Univ Washington Seattle WA 98195 USA

ISBN: (数字)9783031327261

ISBN: (纸本)9783031327254;9783031327261

Approximate integer programming is the following: For a given convex body K subset of R-n, either determine whether K boolean AND Z(n) is empty, or find an integer point in the convex body 2 center dot (K - c) + c which is K, scaled by 2 from its center of gravity c. Approximate integer programming can be solved in time 2(O(n)) while the fastest known methods for exact integer programming run in time 2(O(n)) center dot n(n). So far, there are no efficientmethods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we showthat an integer point x * is an element of (K boolean AND Z(n)) can be found in time 2(O(n)), provided that the remainders of each component x(i)* mod l for some arbitrarily fixed l >= 5(n + 1) of x * are given. the algorithm is based on a cutting-plane technique, iteratively halving the volume of the feasible set. the cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a 2(O(n))n(n) algorithm for general integer programming. this matches the current best bound of an algorithm by Dadush (2012) that is considerably more involved. Our algorithm also relies on a new asymmetric approximate Caratheodory theorem that might be of interest on its own. Our second method concerns integer programming problems in standard equation form Ax = b, 0 <= x <= u, x is an element of Z(n). Such a problem can be reduced to the solution of Pi(i) O(logu(i) + 1) approximate integer programming problems. this implies, for example that knapsack or subset-sum problems with polynomial variable range 0 <= x(i) <= p(n) can be solved in time (logn)(O(n)). For these problems, the best running time so far was n(n) center dot 2(O(n)).

关键词： integer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：