Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
From MaRDI portal
Publication:2304553
DOI10.1016/j.tcs.2020.01.017zbMath1435.90087arXiv1709.02850OpenAlexW3003291422MaRDI QIDQ2304553
Robert Bredereck, Nimrod Talmon, Piotr Faliszewski, Piotr Skowron, Rolf Niedermeier
Publication date: 12 March 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1709.02850
Mixed integer programming (90C11) Nonlinear programming (90C30) Voting theory (91B12) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (3)
On the complexity of quasiconvex integer minimization problem ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ On improved interval cover mechanisms for crowdsourcing markets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Economics and computation. An introduction to algorithmic game theory, computational social choice, and fair division
- The complexity of priced control in elections
- Prices matter for the parameterized complexity of shift bribery
- Fundamentals of parameterized complexity
- Campaign management under approval-driven voting rules
- Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks
- \(N\)-fold integer programming
- Anyone but him: the complexity of precluding an alternative
- An application of simultaneous diophantine approximation in combinatorial optimization
- How hard is it to control an election?
- Approximation algorithms for combinatorial problems
- Approximating covering integer programs with multiplicity constraints
- FPT approximation schemes for maximizing submodular functions
- Multivariate complexity analysis of Swap Bribery
- Integer convex minimization by mixed integer linear optimization
- A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
- \(n\)-fold integer programming in cubic time
- Integer optimization on convex semialgebraic sets
- Scheduling meets \(n\)-fold integer programming
- Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives
- Approximation algorithms for covering/packing integer programs
- Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems
- The Design of Approximation Algorithms
- Integer Programming with a Fixed Number of Variables
- Multimode Control Attacks on Elections
- A threshold of ln n for approximating set cover
- Elections with Few Candidates: Prices, Weights, and Covering Problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- When are elections with few candidates hard to manipulate?
- Swap Bribery
- How Hard Is Bribery in Elections?
- Exact Algorithms for Set Multicover and Multiset Multicover Problems
- Minkowski's Convex Body Theorem and Integer Programming
- On the existence of optimal solutions to integer and mixed-integer programming problems
- Chamberlin--Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time
- Reducibility among Combinatorial Problems
- Faster Algorithms for Integer Programs with Block Structure
- A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- Integer Programming in Parameterized Complexity: Three Miniatures.
- Control and Bribery in Voting
- Handbook of Computational Social Choice
- Weighted Electoral Control
- Analytical approach to parallel repetition
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
This page was built for publication: Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
