NSTL国家科技图书文献中心

1. On the pure fixed charge transportation problem NSTL国家科技图书文献中心

Zhu, Pengfei | Chen, Guangting ... - 《Discrete optimization》 - 2025,55 - 共7页

摘要：The pure fixed charge transportation problem | is a well-known variant of the classic | transportation problem where the cost of sending goods from a | source to a destination only equals a fixed charge | , regardless of the flow quantity. The objective is to

关键词： Transportation problem | Fixed charge | NP-hard | Approximation algorithm | Worst case ratio

2. Linear time algorithm for the vertex-edge domination problem in convex bipartite graphs NSTL国家科技图书文献中心

Buyukcolak, Yasemin - 《Discrete optimization》 - 2025,55 - 共8页

摘要：Given a graph G = ( V , E ) , a vertex u E V | ve-dominates all edges incident to any vertex in | the closed neighborhood N[u]. A subset D c V is a | vertex-edge dominating set if, for each edge e E E | , there exists a vertex u E D such that u ve-dominates e

关键词： Vertex-edge domination | Independent vertex-edge domination | Linear time algorithm | Convex bipartite graphs | Chain decomposition

3. Integer points in the degree-sequence polytope NSTL国家科技图书文献中心

Bach, Eleonore | Eisenbrand, Friedric...... - 《Discrete optimization》 - 2025,55 - 共10页

摘要：An integer vector is an element of Z is a | degree sequence if there exists a hypergraph with | vertices {1, ... , } such that each is the number of | hyperedges containing . The degree-sequence polytope od is | the convex hull of all degree sequences. We show

关键词： Integer programming | Hypergraphic degree sequences | Degree-sequence polytope

4. Uniform capacitated facility location with outliers/penalties NSTL国家科技图书文献中心

Dabas, Rajni | Gupta, Neelima - 《Discrete optimization》 - 2025,55 - 共15页

摘要：In this paper, we present a framework to | design approximation algorithms for capacitated | facility location problems with penalties/outliers. We | apply our framework to obtain first approximations for | capacitated k-facility location problem with penalties

关键词： Approximation | Facility location | k-median | Outliers | Penalties

5. A polynomial-time algorithm for conformable coloring on regular bipartite and subcubic graphs NSTL国家科技图书文献中心

Faria, Luerbio | Nigro, Mauro ... - 《Discrete optimization》 - 2025,55 - 共14页

摘要：In 1988, Chetwynd and Hilton observed that a | ( d + 1)- total coloring induces a vertex coloring | in the graph, they called it conformable. A ( d + 1 | )- vertex coloring of a graph G = ( V , E) is called | conformable if the number of color classes of parity

关键词： Vertex coloring | Conformable coloring | Total coloring

6. Generalized min-up/min-down polytopes NSTL国家科技图书文献中心

Rottner, Cecile - 《Discrete optimization》 - 2025,55 - 共17页

摘要：Consider a time horizon and a set of N | possible states for a given system. The system must be in | exactly one state at a time. In this paper, we | generalize classical results on min-up/mindown constraints | for a 2-state system to an N-state system with N

关键词： Min-up/min-down | Minimum dwell time | Unit commitment | Polytope | Linear description

7. Solving hard bi-objective knapsack problems using deep reinforcement learning NSTL国家科技图书文献中心

Charkhgard, Hadi | Moghaddam, Hanieh Ra...... - 《Discrete optimization》 - 2025,55 - 共18页

摘要：We study a class of bi-objective integer | programs known as bi-objective knapsack problems (BOKPs | ). Our research focuses on the development of | innovative exact and approximate solution methods for BOKPs | by synergizing algorithmic concepts from two

关键词： Multi-objective optimization | Bi-objective knapsack problem | Deep reinforcement learning | Q-learning

8. Approximation schemes for Min-Sum k -Clustering NSTL国家科技图书文献中心

Naderi, Ismail | Rezapour, Mohsen ... - 《Discrete optimization》 - 2024,54 - 共15页

摘要：We consider the Min-Sum k-Clustering (k k-MSC | ) problem. Given a set of points in a metric which is | represented by an edge-weighted graph G = ( V, E ) and a | parameter k , the goal is to partition the points V into k | clusters such that the sum of distances between all pairs

关键词： Approximation algorithms | Clustering | Dynamic programming

9. On non-superperfection of edge intersection graphs of paths NSTL国家科技图书文献中心

Kaial, Victoria | Kerivin, Herve ... - 《Discrete optimization》 - 2024,54 - 共18页

摘要：The routing and spectrum assignment problem in | modern flexgrid elastic optical networks asks for | assigning to given demands a route in an optical network | and a channel within an optical frequency spectrum | so that the channels of two demands are disjoint

关键词： Routing and spectrum assignment problem | Edge intersection graph of paths | Interval coloring | Superperfection

10. Corrigendum to “Bilevel time minimizing transportation problem” [Discrete Optim.] 5 (4) (2008) 714–723 (Bilevel time minimizing transportation problem (2008) 5(4) (714–723), (S1572528608000364), (10.1016/j.disopt.2008.04.004)) NSTL国家科技图书文献中心

Sonia | Khandelwal A. - 《Discrete optimization》 - 2024,54 - 共4页

摘要：© 2024 Elsevier B.V.This is a corrigendum to | our research paper titled “Bilevel time minimizing | transportation problem” published in 2008. We deeply regret a | minor error in the formulation of an intermediate | problem solved as part of the algorithm. The

摘要：The pure fixed charge transportation problem | is a well-known variant of the classic | transportation problem where the cost of sending goods from a | source to a destination only equals a fixed charge | , regardless of the flow quantity. The objective is to

关键词： Transportation problem | Fixed charge | NP-hard | Approximation algorithm | Worst case ratio

摘要：Given a graph G = ( V , E ) , a vertex u E V | ve-dominates all edges incident to any vertex in | the closed neighborhood N[u]. A subset D c V is a | vertex-edge dominating set if, for each edge e E E | , there exists a vertex u E D such that u ve-dominates e

关键词： Vertex-edge domination | Independent vertex-edge domination | Linear time algorithm | Convex bipartite graphs | Chain decomposition

摘要：An integer vector is an element of Z is a | degree sequence if there exists a hypergraph with | vertices {1, ... , } such that each is the number of | hyperedges containing . The degree-sequence polytope od is | the convex hull of all degree sequences. We show

关键词： Integer programming | Hypergraphic degree sequences | Degree-sequence polytope

摘要：In this paper, we present a framework to | design approximation algorithms for capacitated | facility location problems with penalties/outliers. We | apply our framework to obtain first approximations for | capacitated k-facility location problem with penalties

关键词： Approximation | Facility location | k-median | Outliers | Penalties

摘要：In 1988, Chetwynd and Hilton observed that a | ( d + 1)- total coloring induces a vertex coloring | in the graph, they called it conformable. A ( d + 1 | )- vertex coloring of a graph G = ( V , E) is called | conformable if the number of color classes of parity

关键词： Vertex coloring | Conformable coloring | Total coloring

摘要：Consider a time horizon and a set of N | possible states for a given system. The system must be in | exactly one state at a time. In this paper, we | generalize classical results on min-up/mindown constraints | for a 2-state system to an N-state system with N

关键词： Min-up/min-down | Minimum dwell time | Unit commitment | Polytope | Linear description

摘要：We study a class of bi-objective integer | programs known as bi-objective knapsack problems (BOKPs | ). Our research focuses on the development of | innovative exact and approximate solution methods for BOKPs | by synergizing algorithmic concepts from two

关键词： Multi-objective optimization | Bi-objective knapsack problem | Deep reinforcement learning | Q-learning

摘要：We consider the Min-Sum k-Clustering (k k-MSC | ) problem. Given a set of points in a metric which is | represented by an edge-weighted graph G = ( V, E ) and a | parameter k , the goal is to partition the points V into k | clusters such that the sum of distances between all pairs

关键词： Approximation algorithms | Clustering | Dynamic programming

摘要：The routing and spectrum assignment problem in | modern flexgrid elastic optical networks asks for | assigning to given demands a route in an optical network | and a channel within an optical frequency spectrum | so that the channels of two demands are disjoint

关键词： Routing and spectrum assignment problem | Edge intersection graph of paths | Interval coloring | Superperfection

摘要：© 2024 Elsevier B.V.This is a corrigendum to | our research paper titled “Bilevel time minimizing | transportation problem” published in 2008. We deeply regret a | minor error in the formulation of an intermediate | problem solved as part of the algorithm. The

关键词： Bilevel TMTP | Corrigendum

4008-161-200 800-990-8900

国家科技图书文献中心